2

Having a hard time understanding fold... Is the expansion correct ? Also would appreciate any links, or analogies that would make fold more digestible.

foldMap :: (a -> b) -> [a] -> [b]
foldMap f [] = []
foldMap f xs = foldr (\x ys -> (f x) : ys) [] xs


b =  (\x ys -> (f x):ys)
foldMap (*2) [1,2,3]
= b 1 (b 2 (foldr b [] 3))
= b 1 (b 2 (b 3 ( b [] [])))
= b 1 (b 2 ((*2 3) : []))
= b 1 ((*2 2) : (6 :[]))
= (* 2 1) : (4 : (6 : []))
= 2 : (4 : (6 : []))
Jung
  • 139
  • 6

2 Answers2

6

First, let's not use the name foldMap since that's already a standard function different from map. If you want to re-implement an existing function with the same or similar semantics, convention is to give it the same name but either in a separate module, or with a prime ' appended to the name. Also, we can omit the empty-list case, since you can just pass that to the fold just as well:

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x ys -> f x : ys) [] xs

Now if you want to evaluate this function by hand, first just use the definition without inserting anything more:

map' (*2) [1,2,3,4]
 ≡ let f = (*2)
       xs = [1,2,3,4]
   in foldr (\x ys -> (f x) : ys) [] xs
 ≡ foldr (\x ys -> (*2) x : ys) [] [1,2,3,4]

Now just prettify a bit:

 ≡ foldr (\x ys -> x*2 : ys) [] [1,2,3,4]

Now to evaluate this through, you also need the definition of foldr. It's actually a bit different in GHC, but effectively

foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

So with your example

  ...
 ≡ foldr (\x ys -> x*2 : ys) [] (1:[2,3,4])
 ≡ (\x ys -> x*2 : ys) 1 (foldr (\x ys -> x*2 : ys) [] [2,3,4])

Now we can perform a β-reduction:

 ≡ 1*2 : foldr (\x ys -> x*2 : ys) [] [2,3,4]
 ≡ 2 : foldr (\x ys -> x*2 : ys) [] [2,3,4]

...and repeat for the recursion.

leftaroundabout
  • 117,950
  • 5
  • 174
  • 319
5

foldr defines a family of equations,

foldr g n [] = n
foldr g n [x] = g x (foldr g n []) = g x n
foldr g n [x,y] = g x (foldr g n [y]) = g x (g y n)
foldr g n [x,y,z] = g x (foldr g n [y,z]) = g x (g y (g z n))
                        ----- r ---------

and so on. g is a reducer function,

                    g x r = ....

accepting as x an element of the input list, and as r the result of recursively processing the rest of the input list (as can be seen in the equations).

map, on the other hand, defines a family of equations

map f [] = []
map f [x] = [f x] = (:) (f x) [] = ((:) . f) x []
map f [x,y] = [f x, f y] = ((:) . f) x (((:) . f) y [])
map f [x,y,z] = [f x, f y, f z] = ((:) . f) x (((:) . f) y (((:) . f) z []))
                                =  (:)  (f x) ( (:)  (f y) ( (:)  (f z) []))

The two families simply exactly match with 

g = ((:) . f) = (\x -> (:) (f x)) = (\x r -> f x : r)

and n = [], and thus

foldr ((:) . f) [] xs  ==  map f xs

We can prove this rigorously by mathematical induction on the input list's length, following the defining laws of foldr,

foldr g n [] = []
foldr g n (x:xs) = g x (foldr g n xs)

which are the basis for the equations at the top of this post.

Modern Haskell has Fodable type class with its basic fold following the laws of

fold(<>,n) [] = n
fold(<>,n) (xs ++ ys) = fold(<>,n) xs <> fold(<>,n) ys

and the map is naturally defined in its terms as

map f xs  =  foldMap (\x -> [f x]) xs

turning [x, y, z, ...] into [f x] ++ [f y] ++ [f z] ++ ..., since for lists (<>) == (++). This follows from the equivalence

    f x : ys  ==  [f x] ++ ys

This also lets us define filter along the same lines easily, as

filter p xs  =  foldMap (\x -> [x | p x]) xs

To your specific question, the expansion is correct, except that (*2 x) should be written as ((*2) x), which is the same as (x * 2). (* 2 x) is not a valid Haskell (though valid Lisp :) ).

Functions like (*2) are known as "operator sections" -- the missing argument goes into the empty slot: (* 2) 3 = (3 * 2) = (3 *) 2 = (*) 3 2.

You also asked for some links: see e.g. this, this and this.

Will Ness
  • 70,110
  • 9
  • 98
  • 181