List concatenation using foldl', foldr

4
votes

I'm learning Haskell now and I'm facing the following problem:

I want to rewrite the ++ function using foldl' and foldr. I've done it with foldr:

myConcat xs ys = foldr (:) ys xs

I can't do it using foldl'. I've read in RealWorldHaskell that foldr is useful for doing this kind of thing. Ok, but can't I also write an equivalant to ++ using foldl? Can someone show me how I can do this (if it can be done... The book doesn't mention anything about it)...

Does Haskell's type mechanism prevent me from doing this? Every time I tried I got a type error...

5
ghchaskell

5 Answers

10
votes

I'm guessing the error which you get is from trying to simply switch foldr to foldl':

myConcat xs ys = foldl' (:) ys xs

which produces the error (using my Hugs REPL):

ERROR - Type error in application
*** Expression     : foldl' (:) xs ys
*** Term           : (:)
*** Type           : a -> [a] -> [a]
*** Does not match : [a] -> a -> [a]

Notice in the last two lines (the provided type and the expected type) that the positions of [a] and a are in the opposite positions. This means we need a function which is sort of like (:), but which takes its arguments in the opposite order.

Haskell has a function which does this for us: the flip function. Basically, flip is equivalent to

flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x y

That is, flip takes a binary function as an argument, and returns another binary function whose arguments are reversed ("flipped") from the original. So while (:) has the type a -> [a] -> [a], we see that flip (:) has the type [a] -> a -> [a], making it a perfect candidate as a parameter to foldl'.

Using flip, we now have this code:

myConcat xs ys = foldl' (flip (:)) ys xs

This result from the fact that foldl' has the type (a -> b -> c) -> a -> [b] -> c

Running this with arguments [1..5] and [6..10], we get a result of [5,4,3,2,1,6,7,8,9,10], which is almost what we want. The only problem is that the first list turns out backwards in the result. Adding a simple call to reverse gives us our final definition of myConcat:

myConcat xs ys = foldl' (flip (:)) ys (reverse xs)

Looking over this process shows one of the nice things that often comes up when writing Haskell code: when you run into a problem, you can solve it one (small) step at a time. This is especially true when you already have one working implementation, and you are simply trying to write another. The big thing to notice is that if you change one part of the implementation (in this case, changing foldr to foldl'), then many of the other needed changes simply fall out of the type definitions. The few that remain are correctedness problems which can readily be found, either by running test cases, or by looking at the exact nature of the functions used.

PS: any Haskell guys who can freshen up that last line of code, feel free to do so. While it's not horrible, I don't find it to be very pretty. Unfortunately, I'm not that good with Haskell yet.

9
votes

The : operator concatenates a single element, its left argument, to a list, its right argument.

The parameters to foldl are,

  • The folding function
  • The initial value
  • A list of values to step through.

Recall in particular that the folding function takes, as its left argument, the current value, which starts out as the initial value. Hence, the folding function's left argument is a list, and its right argument is a single value. If you play around with it, you can get things like [by just switching arguments to make the types match up],

> foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6]
[6,5,4,1,2,3]

But, this isn't what you want. You'll have to solve it yourself; I was able to build a reverse function using foldl and call this as a subroutine -- but feel free to solve it differently if you can.

4
votes

It is not always possible, as foldr (as well as ++) works on infinite lists, but foldl does not. However, foldl can be written in terms of foldr: http://www.haskell.org/haskellwiki/Foldl_as_foldr

Update: for finite lists, foldr can also be written in terms of foldl:

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a bs =
  foldl (\g b x -> g (f b x)) id bs a

So from that you can implement (++) in terms of foldl

3
votes
data [] a = ... | a : [a]
(:) :: a -> [a] -> [a]

the (:) op treat left and right operand differently.

a :: Char
b :: Char
c :: [Char]

a:[b] is ok

a:b is not ok

a:c is ok.

look for the type-signature of foldr (:) and foldl (:) you will find the different of them.

2
votes

You can do it using foldl but that wont be efficient as compared to foldr based implementation

Example using foldl:

show $ (\xs ys -> foldl­ (\s e -> e:s ) ys (reve­rse xs)) [1,2]­ [3,4]