haskell - 使用折叠实现 takeWhile

Question

如何使用折叠在 Haskell 中实现 takeWhile 函数？

takeWhile :: (a -> Bool) -> [a] -> [a]

我尝试了一种类似于实现这样的过滤器的策略

filter :: (a -> Bool) -> [a] -> [a]
filter f = foldr (\x acc -> if f x then x : acc else acc) []

但是当 f x 为假时我怎么能停止呢？

Answer 1

刚换acc至 []在 else分支:

takeWhile f = foldr (\x acc -> if f x then x : acc else []) []

这个想法是，当您从输入列表中使用元素时，您正在懒惰地构建结果列表，因此您返回 []当您想终止结果列表时。

takeWhile (< 3) [0..]
=
0 : takeWhile (< 3) [1..]
=
0 : 1 : takeWhile (< 3) [2..]
=
0 : 1 : 2 : takeWhile (< 3) [3..]
=
0 : 1 : 2 : []
=
[0, 1, 2]

这也说明了 Haskell 列表是如何真正成为值流的。右折叠是​​小的状态机，它通过输入流逐步移动以生成输出流。