haskell - 使用 foldr 实现 take

Question

这是我take使用的版本foldr：

myTake n list = foldr step [] list
                where step x y | (length y) < n = x : y
                               | otherwise = y

main = do print $ myTake 2 [1,2,3,4]

输出不是我所期望的：

[3,4]

然后我尝试通过将长度y插入自身来进行调试，结果是：

[3,2,1,0]

我不明白为什么长度按降序插入。也许我错过了一些明显的东西？

Answer 1

如果你想实现takeusingfoldr你需要模拟从左到右遍历列表。关键是使折叠函数依赖于一个额外的参数，该参数编码你想要的逻辑，而不仅仅是依赖于列表的折叠尾部。

take :: Int -> [a] -> [a]
take n xs = foldr step (const []) xs n
  where
    step x g 0 = []
    step x g n = x:g (n-1)

在这里，foldr返回一个函数，该函数接受一个数字参数并从左到右遍历列表，从中获取所需的数量。由于懒惰，这也适用于无限列表。一旦额外的参数达到零，foldr就会短路并返回一个空列表。

Answer 2

foldrstep将从*最后一个元素**开始应用函数。那是，

foldr step [] [1,2,3,4] == 1 `step` (2 `step` (3 `step` (4 `step` [])))
                        == 1 `step` (2 `step` (3 `step` (4:[])))
                        == 1 `step` (2 `step (3:4:[]))   -- length y == 2 here
                        == 1 `step` (3:4:[])
                        == 3:4:[]
                        == [3, 4]

长度按降序“插入”，因为:是前置操作。较长的长度被添加到列表的开头。

_{（图片取自http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29）}

*：为简单起见，我们假设每个操作都是严格的，这在 OP 的step实现中是正确的。

Answer 3

到目前为止，其他答案让它变得过于复杂，因为它们似乎过于拘泥于foldr“从右到左”起作用的概念。从某种意义上说，它确实如此，但 Haskell 是一种惰性语言，因此使用惰性折叠步骤的“从右到左”计算实际上会从左到右执行，因为结果会被消耗掉。

研究这段代码：

take :: Int -> [a] -> [a]
take n xs = foldr step [] (tagFrom 1 xs)
    where step (a, i) rest
               | i > n     = []
               | otherwise = a:rest

tagFrom :: Enum i => i -> [a] -> [(a, i)]
tagFrom i xs = zip xs [i..]