CODEWITHSUNDEEP
haskelldictionaryfunctional-programmingfold
user22709
user22709

Reputation: 11

Define functions with foldl foldr

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!

Upvotes: 1

Views: 1826

Answers (1)

chi
chi

Reputation: 116174

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

Upvotes: 2

Related Questions