1

I understand the definitions of foldl, foldr, but I have problems with functions defined by them.

For example map with foldr:

map f []       = []
map f l   = foldr (\x xs -> f x : xs) [] l

I don't understand the (\x xs -> f x : xs). It is the map function, which foldr takes? But shouldn't it be (\x xs -> f x : f xs), because map f (x:xs) = f x : map f xs?

Example with foldl:

concat (x:xs) = x ++ concat xs

concat' xs = foldl (++) [] xs
concat'' xs = foldl (\ys y -> ys ++ y) [] xs

Of course I understand (++), but what's the logic behind (\ys y -> ys ++ y)? Is it ys = [] and y = xs? So the function takes [] as ys and y is the first element of xs and concates the [] with the y? Concrete example:

concat'' [1,2,3] = foldl (\ys y -> ys ++ y) [] [1,2,3]
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [] [1]) [2,3]
=> foldl (\ys y -> ys ++ y) [1] [2,3]
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1] [2]) [3]
=> foldl (\ys y -> ys ++ y) [1,2] [3]
=> foldl (\ys y -> ys ++ y) ((\ys y -> ys ++ y) [1,2] [3]) []
=> foldl (\ys y -> ys ++ y) [1,2,3] []
=> [1,2,3]

Another thing: concat only takes 1 list xs, so if I want to concat 2 lists?

concat (x:xs) ys = x ++ concat xs ys
concat [1,2,3] [4,5,6] with foldl?

Reverse:

reverse (x:xs) = reverse xs ++ [x]

reverse'  l = foldl (\xs x -> [x] : xs) [] l
reverse'' l = foldr (\x xs -> xs ++ [x]) [] l

The foldr is intuitive clear (with the questions from above), but what's behind the reverse order in foldl (\xs x -> [x] : xs)? This foldl (\x xs -> xs ++ [x]) [] l would be wrong, wouldn't it?

Thanks a lot!

Improve this question
4
  • 1
    that's a couple of questions - for the first observe that the xs there already was mapped by f (look at the definition of foldr to see why) (also f xs would not be well-typed as you had f :: a -> b and at the same time f :: [a] -> b' so you would need to identify a ~ [a]) Commented Jul 3, 2016 at 10:57
  • Note that foldr f z [x1, x2, x3] = f x1 (f x2 (f x3 z)) so the xs was already mapped by f. Commented Jul 3, 2016 at 10:58
  • for the second: just note that foldl will loop through xs from the left (again look at the definition) Commented Jul 3, 2016 at 11:00
  • for the very last: it's just the difference between folding from left vs folding from right - just try your different implementation and have a look for yourself! Commented Jul 3, 2016 at 11:01

1 Answer 1

Reset to default
2

The code

foldr (\x xs -> ...) end list

could be read, roughly, as follows

  • scan the whole list
  • if it's empty, just return end end
  • otherwise:
    • let x be the element at hand
    • let xs be the rest of the list, after having been processed
    • apply the ... operation

The emphasized part is crucial. xs is not the rest of the list, but the result of the "recursive call" on it.

Indeed, xs is a bad name for that. In thee general case, it's not even a list! E.g. one would never write (silly example)

foldr (\x xs -> x + xs) 0 [1..100]  -- sum 1..100

but rather prefer something like

foldr (\x partialSum -> x + partialSum) 0 [1..100]  -- sum 1..100

(Actually, one would not sum using foldr, but let's leave that aside.)

So, just read it like this:

map f l   = foldr (\x mappedTail -> f x : mappedTail) [] l
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks! I think I understand foldr. map with foldl would be like this? map f l = foldl (\x xs -> x : f xs) [] l So x is the mapped part and xs is mapped on?
@user22709 Morally yes, but note that in that case x is a (mapped) list, and xs is an element so it should be foldl (\x xs -> x ++ [f xs]) [] list
Thank you! Do you have a suggestion for a more elegant way to write that, because xs is normally the rest of the list, which isn't the case here...
@user22709 Actually, I would avoid foldl since appending at the end as in .. ++ [..] is known to be inefficient. If you still want, simply choose some reasonable names for x,xs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.