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

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

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将短路并返回一个空列表。