3

我对编程和练习编写函数还很陌生，我试图扭转 Prelude 下降的影响；

drop :: Int -> [a] -> [a]
drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] = []
drop n (x:xs) = drop (n-1) xs

进入我最初命名为dropR的东西。

dropR :: Int -> [a] -> [a] -- drops from the right of the list
dropR 0 [] = []
dropR 0 (x:xs) = x:xs
dropR n [] = []
dropR n (x:xs) = reverse (drop (n-1) (reverse xs ++ [x]))

不幸的是，这不起作用，因为输入dropR 2 [1,2,3,4,5]返回[1,2,3,4]而不是[1,2,3]我希望的那样。使用 drop 2，我会在列表中得到 3 个值而不是 4 个。我将函数更改为；

dropR :: Int -> [a] -> [a] -- drops from the right of the list
dropR 0 [] = []
dropR 0 (x:xs) = x:xs
dropR n [] = []
dropR n (x:xs) = reverse (drop n (reverse xs ++ [x]))

它以我想要的方式工作，但我不明白为什么第一个不起作用。我认为它只会反转列表并获取与常规 drop 相同数量的值，之后我可以反转它。

为什么 drop 需要drop (n-1)而我的 dropR 只需要drop n？它是因为 drop 中的递归而不是 dropR 中的递归而发生的吗？

4

2 回答 2

5

让我们看一个例子：

dropR 2 [1, 2, 3, 4]

在您的第一次尝试中，最后一行匹配，并且其中：

  • n = 2
  • x = 1
  • xs = [2, 3, 4]

所以：

  • reverse xs = [4, 3, 2]
  • reverse xs ++ [x] = [4, 3, 2, 1]
  • drop (n-1) (reverse xs ++ [x]) = drop 1 [4, 3, 2, 1] = [3, 2, 1]
  • reverse (drop (n-1) (reverse xs ++ [x])) = [1, 2, 3]
  • 量子点

另一方面，在您的第二次尝试中：

  • reverse xs = [4, 3, 2]
  • reverse xs ++ [x] = [4, 3, 2, 1]
  • drop n (reverse xs ++ [x]) = drop 2 [4, 3, 2, 1] = [2, 1]
  • reverse (drop (n-1) (reverse xs ++ [x])) = [1, 2]
  • 量子点

但有更深入的了解。

观察这reverse xs ++ [x]实际上是一样的reverse (x:xs)：你正在反转尾巴，然后把头贴到它的末端。这与首先​​反转整个列表相同。

所以你真正在那里做的是：

  • 反转整个列表
  • n从那里掉下来
  • 再次扭转它

因此，您不妨删除那里的所有案例，然后执行以下操作：

dropR n xs = reverse (drop n (reverse xs))

或者更短一点：

dropR n = reverse . drop n . reverse

我认为这个变体稍微好一点，因为它更清楚地表达了这个想法：reverse，然后 drop n，然后再 reverse。

于 2021-09-23T02:34:42.987 回答
2

@FyodorSoikin解释了为什么n-1是必要的（因为您与 匹配(x:xs)，因此xs是列表的尾部，而不是整个列表）。

但是使用reverseand++ [x]并不是一个好主意。reverse要求列表具有有限数量的项目，并将++ [x]算法转换为O(n 2 ) 1。删除n最后一项的更好主意可能是使用两个迭代器在列表上运行：第一个迭代器比第二个迭代器向右开始n步。在这种情况下，如果第一个迭代器到达列表的末尾，我们知道第二个枚举器应该停止。

因此，我们可以通过以下方式实现：

dropR :: Int -> [a] -> [a]
dropR n xs = go (drop n xs) xs
  where go [] _ = []
        go (x:xs) ~(y:ys) = y : go xs ys

这个实现是懒惰的，并且可以处理无限的列表（在这种情况下它永远不会丢弃任何东西）。

于 2021-09-23T09:42:55.077 回答