CODEWITHSUNDEEP
haskell
A. Lindberg
A. Lindberg

Reputation: 316

Implement takeWhile with fold

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?

Upvotes: 7

Views: 3867

Answers (1)

Jon Purdy
Jon Purdy

Reputation: 55059

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.

Upvotes: 15

Related Questions