haskell - 使用折叠实现 takeWhile

如何使用折叠在 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 为假时我怎么能停止呢？

最佳答案

只需将 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 列表是如何真正成为值流的。右折叠是​​小的状态机，它通过输入流逐步移动以生成输出流。

关于haskell - 使用折叠实现 takeWhile，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40992091/