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
                              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 :: [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]

protected by gnat Aug 4 '16 at 21:48

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.