Реализовать takeWhile со сгибом

Question

Как реализовать функцию takeWhile в Haskell с помощью сгиба?

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

Я попробовал стратегию похожий на реализующий фильтр, как этот

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

Но как я могу остановить, когда е х ложно?

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 действительно потоки значений. Правые складки - это небольшие государственные машины, которые шаг за шагом перемещаются по входному потоку для создания выходного потока.