Implement takeWhile with fold

Question

How can I implement the takeWhile function in Haskell using fold?

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

I tried a strategy similiar to implementing filter like this

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

But how can I stop when f x is false?

Answer 1

Just change acc to [] in the else branch:

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

The idea is that you’re lazily building the result list as you consume elements from the input list, so you return [] when you want to terminate the result list.

takeWhile (< 3) [0..]
=
0 : takeWhile (< 3) [1..]
=
0 : 1 : takeWhile (< 3) [2..]
=
0 : 1 : 2 : takeWhile (< 3) [3..]
=
0 : 1 : 2 : []
=
[0, 1, 2]

This also illustrates how Haskell lists are really streams of values. Right folds are little state machines that move step-by-step through an input stream to generate an output stream.