为什么我的函数 dropR（Prelude drop 的反面）看起来像它的样子？

Question

我还是编程和练习编写函数的新手，我试图扭转 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 (n-1)而我的dropR只需要drop n？它发生是因为递归在 drop 中而不是在 dropR 中吗？

Answer 1

我们来看一个例子：

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]
Q.E.D.

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

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]
Q.E.D.

但要深入了解一下。

注意reverse xs ++ [x]其实和reverse (x:xs)是一样的：你是把尾巴倒过来，然后把头贴到尾巴上。这与首先反转整个列表是一样的。

所以你真正做的是：

反转整个列表
从中删除 n
再次反转

因此，您不妨取消现有的所有情况，然后执行以下操作：

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

或者更短一点：

dropR n = reverse . drop n . reverse

我觉得这个变体稍微好一点，因为它更清楚地表达了这个想法：反转，然后下降 n，然后再反转。

Answer 2

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

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

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

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

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

为什么我的函数 dropR（Prelude drop 的反面）看起来像它的样子？

Why does my function dropR (reverse of Prelude drop) look the way it does?

function

haskell

haskell-prelude