使用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

Run Code Online (Sandbox Code Playgroud)

长度按递减顺序"插入",因为它:是一个前置操作.较长的长度将添加到列表的开头.

_{(图片来自http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)}

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

Answer 2

如果要实现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将短路并返回空列表.

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..]