Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
+1 , this also helped me, and I will attempt your suggestion, thanks –  lwm Nov 4 '12 at 17:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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