使用foldr实现take

Question

这是我使用foldr的take版本

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

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

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

到目前为止，其他的答案使问题变得过于复杂，因为他们似乎过于执着于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..]