# Using foldr to append two lists together (Haskell)

I have been given the following question as part of a college assignment. Due to the module being very short, we are using only a subset of Haskell, without any of the syntactic sugar or idiomatic shortcuts....I must write:

append xs ys : The list formed by joining the lists `xs` and `ys`, in that order

``````append (5:8:3:[]) (4:7:[]) => 5:8:3:4:7:[]
``````

I understand the concept of how foldr works, but I am only starting off in Functional programming. I managed to write the following working solution (hidden for the benefit of others in my class...) :

append = \xs -> \ys -> foldr (\x -> \y -> x:y) ys xs

However, I just can't for the life of me, explain what the hell is going on!? I wrote it by just fiddling around in the interpreter, for example, the following line :

``````foldr (\x -> \y -> x:y) [] (2:3:4:[])
``````

which returned `[2:3:4]` , which led me to try,

``````foldr (\x -> \y -> x:y) (2:3:4:[]) (5:6:7:[])
``````

which returned `[5,6,7,2,3,4]`

so I worked it out from there. I came to the correct solution through guess work and a bit of luck...

I am working from the following definition of foldr:

``````foldr = \f -> \s -> \xs -> if null xs then
s
else
f (head xs) (foldr f s (tail xs) )
``````

Can someone baby step me through my correct solution? I can't seem to get it....I already have scoured the web, and also read a bunch of SE threads, such as How foldr works

-

Folds over lists consist of three elements - the list to fold over, some accumulator function `f` and an initial value.

They transform the list `a:b:c:[]` into `(a f (b f (c f init)))` where `init` is the initial element i.e. they replace the cons constructor `:` with your accumulator function and the empty list `[]` with your supplied initial value.

You can think of your append function as transforming the list `x1:x2:..:xn` into the list `x1:x2:..:xn:ys` for some given list `ys`. This can be done by simply using `ys` as the replacement for the empty list `[]` which terminates your `xs` list.

Your code can be written as

``````append xs ys = foldr (\x y -> x:y) ys xs
``````

Your accumulator function `f` has the type `a -> [a] -> [a]` and is the same as the `(:)` function, so you could write it as

``````append xs ys = foldr (:) ys xs
``````

If the first argument xs is the list x1:x2:...:xn then the result of `append` is the list `x1:x2:...xn:ys` as required.

-

First let's simplify your solution a bit to standard Haskell to make it easier to comprehend:

``````append = \xs -> \ys -> foldr (\x -> \y -> x:y) ys xs
``````

can be written as

``````append xs ys = foldr (:) ys xs
``````

because `\x -> \y -> x : y` is equivalent to `\x -> y -> (:) x y` which is equivalent to `(:)` (this is called η-reduction, here we applied it twice).

I assume you know how `foldr` works so let's have a look at this special case: Here `foldr` is specialized to type `(a -> [a] -> [a]) -> [a] -> [a] -> [a]`. The value that is accumulated during folding is of type `[a]`, the same type as the list we're consuming. (This is probably what makes this a bit confusing.) We start with `ys` as the accumulated value. Then `foldr` processes elements of `xs` right-to-left, and at each step it prepends (using `:`) the currently inspected element to the currently accumulated value. So it starts by prepending the last element of `xs` in front of `ys`, then the second-to-last element of `xs` to that etc., finally building the whole `xs` prepended to `ys`.

(As another exercise for understanding folds, I suggest you to try to implement `foldl` just using `foldr`. Hover mouse over the following area for a hint.)

The accumulated/returned value produced by foldr needs to be a function.

-
+1 , this also helped me, and I will attempt your suggestion, thanks – lwm Nov 4 '12 at 17:57

`append xs ys = concat [xs,ys]`

Might not pass your course validator but works just fine.

Just for the pragmatists newbs here. Hoogling for [[a]] -> [a] yields the same answer.

-
this code dump doesn't even attempt to answer the question asked, "Can someone baby step me through my correct solution?" – gnat Jun 7 '14 at 18:51

append :: [a] -> [a] -> [a]

append = flip(foldr (:))

I try to explain foldr:

When we use foldr (:) [1,2,3] [4,5,6] without the flip

we take the second argument which is [4,5,6] the last element of the argument is 6, which we apply with the (:) to our first argument [1,2,3] which will then give us [6,1,2,3].

Next last element is 5, which we will do the same operation on, that gives us [5,6,1,2,3].

Lastly we end up with [4,5,6,1,2,3], which isn't the right order only if we swap position of arguments [1,2,3] with [4,5,6] this we do by using flip(foldr (:)), which will give us the right order of arguments

and results in [1,2,3,4,5,6]

-