Define functions with foldl foldr

1
votes

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!

1
haskelldictionaryfunctional-programmingfold
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]) - Random Dev
Note that foldr f z [x1, x2, x3] = f x1 (f x2 (f x3 z)) so the xs was already mapped by f. - Bakuriu
for the second: just note that foldl will loop through xs from the left (again look at the definition) - Random Dev
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! - Random Dev

1 Answers

2
votes

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