Using foldr to append two lists together (Haskell)

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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]