CODEWITHSUNDEEP
haskell
SilentDev
SilentDev

Reputation: 22777

Constructing foldl using foldr

I am trying to create foldl using foldr (a good exercise to learn haskell, and the other SO answers seem to complex).

My solutions is this:

myFoldl :: (b -> a -> b) -> [a] -> (b -> b)
myFoldl f = foldr op z
  where
    z = []
    op x xs b = myFoldl f xs (f b x)

but it does not work. I get an error saying:

• Couldn't match type ‘a -> b’ with ‘[a]’
  Expected type: b -> (a -> b) -> a -> b
    Actual type: b -> [a] -> a -> b
• In the first argument of ‘foldr’, namely ‘op’
  In the expression: foldr op z
  In an equation for ‘myFoldl’:
      myFoldl f
        = foldr op z
        where
            z = []
            op x xs b = myFoldl f xs (f x b)

but it looks good to me. myFoldl takes a function, a list, and something to work with. Why is this not working? (New to haskell, still trying to figure it all out).

Upvotes: 2

Views: 183

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 51119

Since you have:

myFoldl f = foldr op z

you must also have:

myFoldl f xs = foldr op z xs                  -- (**)

From the type of myFoldl, the LHS must have type b -> b. On the other hand, from the type of foldr, the RHS has the same type as z, which you defined as z = [] which has a list type, [c]. So, this expression has type b -> b but also the list type [c], and these two types cannot be reconciled.

The larger problem is that your op shouldn't be defined recursively in terms of myFoldl. The point of the fold (whether left or right) is to replace the explicit recursion, abstracting away the recursion pattern as the fold definition, expressing it with the one-step recombination operation op x r = ... where r is the result for our problem's recursive sub-problem, already calculated for us by the fold itself. A correct definition of the one-step recombination operation thus shouldn't involve any recursive definitions.

Sooooo, let me try to set you on the right track. I think you've recognized that the defining recursive relationship for your myFoldl is:

myFoldl f (x:xs) b = myFoldl f xs (f b x)     -- (1a)
myFoldl f []     b = b                        -- (1b)

Using the definition (**) above, you want to reconcile it with the defining recursive relationship for foldr:

foldr op z (x:xs) = op x (foldr op z xs)
foldr op z []     = z

which we could eta abstract over b like so:

foldr op z (x:xs) b = op x (foldr op z xs) b  -- (2a)
foldr op z []     b = z b                     -- (2b)

Note that the only way (1b) and (2b) are going to give the same result is if b and z b are equal for all b. Note that z is a function here, not a list! Hopefully, you can immediately identify what function z needs to be here.

For reconciling (1a) and (2a), your solution was to write op x xs b = myFoldl f xs (f b x), but that's not the right equation. The correct equation, matching up the RHSs of (1a) and (2a) above is:

op x (foldr op z xs) b = myFoldl f xs (f b x)

and rewriting the foldr on the left in terms of our myFoldl using (**) up above, we get:

op x (myFoldl f xs) b = myFoldl f xs (f b x)

Now, can you see what non-recursive definition of the one-step recombination operation op would satisfy this equation? (Hint: it's a very simple definition.)

op x r              b = ....

Upvotes: 4

Related Questions