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