實施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) [] 

但我怎麼能停在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的列表是如何真正流值。右邊的摺疊是一些小型的狀態機，它們通過輸入流逐步移動以生成輸出流。