折りたたみで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

だけelseブランチに[]へaccを変更します。

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のリストはは値のストリーム実際にある方法を示しています。右折は、入力ストリームを段階的に移動して出力ストリームを生成する小さなステートマシンです。