CODEWITHSUNDEEP
listhaskellfold
Piyush Divyankar
Piyush Divyankar

Reputation: 169

How do I write takeWhile using foldl?

So I am doing exercises from real world haskell book and I wrote following code for takeWhile function using foldl. 

myTakeWhile' :: (a->Bool) -> [a] -> [a]
myTakeWhile' f xs = foldl step [] xs
    where step x xs | f x       = x:(myTakeWhile' f xs)
                    | otherwise = []

This gives the following error, which I am unable to understand. 

Couldn't match type ‘a’ with ‘[a]’
      ‘a’ is a rigid type variable bound by
          the type signature for myTakeWhile' :: (a -> Bool) -> [a] -> [a]
          at p1.hs:17:17
    Expected type: [a] -> [a] -> [a]
      Actual type: a -> [a] -> [a]
    Relevant bindings include
      step :: a -> [a] -> [a] (bound at p1.hs:19:11)
      xs :: [a] (bound at p1.hs:18:16)
      f :: a -> Bool (bound at p1.hs:18:14)
      myTakeWhile' :: (a -> Bool) -> [a] -> [a] (bound at p1.hs:18:1)
    In the first argument of ‘foldl’, namely ‘step’
    In the expression: foldl step [] xs

Upvotes: 4

Views: 759

Answers (1)

developer_hatch
developer_hatch

Reputation: 16214

Edit

1) Your main error, is that you are not understanding that fold does the recursion for you, you don't have to self reference the function myTakeWhile', also, fold has another type: 

foldl: (b -> a -> b) -> b -> [a] -> b

your type error in the step function on where clause is because of it.

2) Your second error, because of the definition of foldl, your takeWhile will be created from the end to the beginning, so, you should have to reverse the list (all this only because you are asking how to do it with foldl)

You can do this by using a simple lambda and an if else, is a little more readable:

myTakeWhile' f xs = foldl (\rs x -> if f x then x:rs else []) [] (reverse xs)

example:

myTakeWhile' (<10) [1..20]

[1,2,3,4,5,6,7,8,9]

However, with this, you just can't go over infinite list, like this:

myTakeWhile' (<10) [1..]

It will hangs trying to create all the unevaluated expression.

Anyway, if you want to use guards and where, you should do it like this:

myTakeWhile f xs = foldl step [] (reverse xs)
  where step rs x | f x = x : rs
                  | otherwise = []

3) Most important of all:

As @amalloy says, takeWhile is much more suitable if you implement it by using foldr :). Understand the differences between the two is crucial in some cases one using one or another can cause you performance issues, for that, you can read this question:

foldl versus foldr behavior with infinite lists

4) Finally, the correct alternative using foldr:

myTakeWhile'' f xs = foldr (\x rs -> if f x then x:rs else []) [] xs

with this, you can use infinite list:

myTakeWhile' (<10) [1..]

You can see the difference of how it makes the folds like this:

Prelude> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"

Prelude> foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"

This sources from https://wiki.haskell.org/Fold

Upvotes: 4

Related Questions