用折叠实现takeWhile

Question

如何使用fold在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) []

但是当fx是假的时候我怎么能停下来？

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列表是如何真正的值流.右侧折叠是小型状态机,它们逐步移动输入流以生成输出流.