Why you can change the list with foldl but not with foldr in Haskell

Question

Why can you change the list with foldl?

reverse' :: [a] -> [a] reverse' xs = foldl (\acc x-> x : acc) [] xs 

But it gives me a compilation error.

 reverse' :: [a] -> [a] reverse' xs = foldr (\acc x-> x : acc) [] xs 

Error

 Couldn't match expected type `a' with actual type `[a]' `a' is a rigid type variable bound by the type signature for reverse' :: [a] -> [a] at foldl.hs:33:13 Relevant bindings include x :: [a] (bound at foldl.hs:34:27) acc :: [a] (bound at foldl.hs:34:23) xs :: [a] (bound at foldl.hs:34:10) reverse' :: [a] -> [a] (bound at foldl.hs:34:1) In the first argument of `(:)', namely `x' In the expression: x : acc 

Answer 1

For starters, type signatures do not line up:

 foldl :: (o -> i -> o) -> o -> [i] -> o foldr :: (i -> o -> o) -> o -> [i] -> o 

So, if you change the argument names:

 reverse' xs = foldr (\ x acc -> x : acc) [] xs 

Now it compiles. It will not work, but now it compiles.

The fact is that foldl works from left to right (i.e. back), while foldr works from right to left (i.e. forward). And that's why foldl allows you to change the list; he transfers things to you in the reverse order.

Having said all this, you can do

 reverse' xs = foldr (\ x acc -> acc ++ [x]) [] xs 

However, it will be very slow. (Quadratic complexity, not linear complexity.)

Answer 2

Each foldl is a foldr .

Recall the definitions.

 foldr :: (a -> s -> s) -> s -> [a] -> s foldr fs [] = s foldr fs (a : as) = fa (foldr fs as) 

This is the standard release of a one-step iterator for lists. I used to make my students beat tables and say, "What are you doing with an empty list? What are you doing with a : as "? And how do you find out that s and f , respectively.

If you think about what happens, you see that foldr efficiently computes a large composition of the functions fa , then applies this composition to s .

 foldr fs [1, 2, 3] = f 1 . f 2 . f 3 . id $ s 

Now let's see foldl

 foldl :: (t -> a -> t) -> t -> [a] -> t foldl gt [] = t foldl gt (a : as) = foldl g (gta) as 

This is also a one-step iteration through the list, but with a battery that changes as we go. Let move it last so that everything to the left of the list argument remains the same.

 flip . foldl :: (t -> a -> t) -> [a] -> t -> t flip (foldl g) [] t = t flip (foldl g) (a : as) t = flip (foldl g) as (gta) 

Now we can see the one-step iteration if we move = one place to the left.

 flip . foldl :: (t -> a -> t) -> [a] -> t -> t flip (foldl g) [] = \ t -> t flip (foldl g) (a : as) = \ t -> flip (foldl g) as (gta) 

In each case, we calculate what we will do if we knew a battery abstracted with \ t -> . For [] we return t . For a : as we treat the tail with gta as a battery.

But now we can convert flip (foldl g) to foldr . Issue a recursive call.

 flip . foldl :: (t -> a -> t) -> [a] -> t -> t flip (foldl g) [] = \ t -> t flip (foldl g) (a : as) = \ t -> s (gta) where s = flip (foldl g) as 

And now we can turn it into foldr , where type s is created using t -> t .

 flip . foldl :: (t -> a -> t) -> [a] -> t -> t flip (foldl g) = foldr (\ as -> \ t -> s (gta)) (\ t -> t) 

So, s says, "what as will do with the battery," and we return \ t -> s (gta) that "what a : as does with the battery." Lean back.

 foldl :: (t -> a -> t) -> t -> [a] -> t foldl g = flip (foldr (\ as -> \ t -> s (gta)) (\ t -> t)) 

Eta extensions.

 foldl :: (t -> a -> t) -> t -> [a] -> t foldl gt as = flip (foldr (\ as -> \ t -> s (gta)) (\ t -> t)) t as 

Reduce flip .

 foldl :: (t -> a -> t) -> t -> [a] -> t foldl gt as = foldr (\ as -> \ t -> s (gta)) (\ t -> t) as t 

So, we calculate “what would we do if we knew the battery”, and then we will feed it with the original battery.

This is moderately instructive in golf, which is a bit. We can get rid of \ t -> .

 foldl :: (t -> a -> t) -> t -> [a] -> t foldl gt as = foldr (\ as -> s . (`g` a)) id as t 

Now let me cancel this composition using >>> from Control.Arrow .

 foldl :: (t -> a -> t) -> t -> [a] -> t foldl gt as = foldr (\ as -> (`g` a) >>> s) id as t 

That is, foldl computes a large inverse composition. So, for example, given [1,2,3] , we get

 foldr (\ as -> (`g` a) >>> s) id [1,2,3] t = ((`g` 1) >>> (`g` 2) >>> (`g` 3) >>> id) t 

where the "pipeline" feeds its argument to the left, so we get

 ((`g` 1) >>> (`g` 2) >>> (`g` 3) >>> id) t = ((`g` 2) >>> (`g` 3) >>> id) (gt 1) = ((`g` 3) >>> id) (g (gt 1) 2) = id (g (g (gt 1) 2) 3) = g (g (gt 1) 2) 3 

and if you take g = flip (:) and t = [] , you get

 flip (:) (flip (:) (flip (:) [] 1) 2) 3 = flip (:) (flip (:) (1 : []) 2) 3 = flip (:) (2 : 1 : []) 3 = 3 : 2 : 1 : [] = [3, 2, 1] 

I.e

 reverse as = foldr (\ as -> (a :) >>> s) id as [] 

by instantiating the general transform foldl to foldr .

Only for matechists. Make cabal install newtype and import Data.Monoid , Data.Foldable and Control.Newtype . Add a tragically missing instance:

 instance Newtype (Dual o) o where pack = Dual unpack = getDual 

Note that, on the one hand, we can implement foldMap on foldr

 foldMap :: Monoid x => (a -> x) -> [a] -> x foldMap f = foldr (mappend . f) mempty 

but vice versa

 foldr :: (a -> b -> b) -> b -> [a] -> b foldr f = flip (ala' Endo foldMap f) 

so the foldr accumulates in the monoid of composing endofunctions, but now, to get the foldl , we will tell foldMap to work in the monoid Dual .

 foldl :: (b -> a -> b) -> b -> [a] -> b foldl g = flip (ala' Endo (ala' Dual foldMap) (flip g)) 

What is mappend for Dual (Endo b) ? Modulo wrap is exactly the reverse composition, >>> .

Answer 3

You can use foldr to efficiently reverse the list (well, most of the time in GHC 7.9 - it relies on some compiler optimizations), but this is a bit strange:

 reverse xs = foldr (\xk -> \acc -> k (x:acc)) id xs [] 

I wrote an explanation of how this works in the Haskell Wiki .

Answer 4

foldr basically deconstructs the list in a canonical way: foldr f initial matches the function with templates: ^{(this is basically the definition of foldr)}

  ff [] = initial ff (x:xs) = fx $ ff xs 

i.e. he un-conses the elements one by one and passes them to f . Well, if all f does it back, then you get the list that you originally were! (Another way of saying that: foldr (:) [] ≡ id .

foldl "deconstructs" the list in reverse order, so if you cancel the items, you will get a reverse list. To achieve the same result with foldr , you need to add to the "wrong" end - either, as shown in the "Math Instrument", inefficiently with ++ , or using a list of differences:

 reverse'' :: [a] -> [a] reverse'' l = dl2list $ foldr (\x accDL -> accDL ++. (x:)) empty l type DList a = [a]->[a] (++.) :: DList a -> DList a -> DList a (++.) = (.) emptyDL :: DList a emptyDL = id dl2list :: DLList a -> [a] dl2list = ($[]) 

Who can be compactly written as

 reverse''' l = foldr (flip(.) . (:)) id l [] 

Answer 5

This is what foldl op acc does with a list, for example with 6 elements:

 (((((acc `op` x1) `op` x2) `op` x3) `op` x4) `op` x5 ) `op` x6 

while foldr op acc does the following:

 x1 `op` (x2 `op` (x3 `op` (x4 `op` (x5 `op` (x6 `op` acc))))) 

When you look at this, it becomes clear that if you want foldl cancel the list, op must be "stick to the correct operand at the beginning of the left operand." It is simple (:) with modified arguments, i.e.

 reverse' = foldl (flip (:)) [] 

(this is the same as your version, but using the built-in functions).

If you want foldr cancel the list, you need to use the "stick to left operand at the end of the correct operand" operator. I do not know about the built-in function that does this; if you want, you can write it as flip (++) . return flip (++) . return

 reverse'' = foldr (flip (++) . return) [] 

or if you prefer to write it yourself

 reverse'' = foldr (\x acc -> acc ++ [x]) [] 

It will be slow though.

Answer 6

A small but significant generalization of several of these answers is that you can implement foldl with foldr , which I think is a clearer way to explain what happens in them:

 myMap :: (a -> b) -> [a] -> [b] myMap f = foldr step [] where step a bs = fa : bs -- To fold from the left, we: -- -- 1. Map each list element to an *endomorphism* (a function from one -- type to itself; in this case, the type is `b`); -- -- 2. Take the "flipped" (left-to-right) composition of these -- functions; -- -- 3. Apply the resulting function to the `z` argument. -- myfoldl :: (b -> a -> b) -> b -> [a] -> b myfoldl fz as = foldr (flip (.)) id (toEndos f as) z where toEndos :: (b -> a -> b) -> [a] -> [b -> b] toEndos f = myMap (flip f) myReverse :: [a] -> [a] myReverse = myfoldl (flip (:)) [] 

For a more detailed explanation of the ideas here, I would recommend reading Tom Ellis "What is foldr from?" and Brent Yorgey " foldr made of monoids . "