[Haskell-cafe] Heavy lift-ing

[Jürgen Doser]

El vie, 23-07-2010 a las 15:05 -0400, Nick Bowler escribió:
> On 11:43 Fri 23 Jul     , michael rice wrote:
> [...]
> > But how does one add [0,1] and [0,2] to get [0,2,1,3]?
> 
> liftM2 (+) [0,1] [0,2] gives the list
> 
>   [0+0, 0+2, 1+0, 1+2]

which one could have found out by asking ghci:

Prelude Control.Monad> let f a b = show a ++ " + " ++ show b
Prelude Control.Monad> liftM2 f [0,1] [0,2]
["0 + 0","0 + 2","1 + 0","1 + 2"]

or simpler:

Prelude Control.Monad> liftM2 (,) [0,1] [2,3]
[(0,2),(0,3),(1,2),(1,3)]

i.e., the in the list monad, you pair each element of one list with each
element of the other(s).

> (recall that (>>=) in the list monad is concatMap).

(>>=) = flip concatMap, to be precise. Or, concatMap = (=<<)

Now let's have some fun with equational reasoning to see what liftM2
does exactly: (Only read this if you really want to!)

liftM2 f a b 

    = { definition of liftM2 }

do {x <- a; y <- b; return (f x y)}

    = { simplified translation of do-notation }

a >>= \x -> (b >>= \y -> return (f x y))

    = { change (>>=) to (=<<) and flip arguments }

(\x -> ((\y -> return (f x y)) =<< b)) =<< a 

    = { specialized to the list monad }

(\x -> ((\y -> [f x y])) `concatMap` b)) `concatMap` a 

    = { change concatMap to prefix application }

concatMap (\x -> concatMap (\y -> [x+y]) b) a

and indeed:

Prelude> concatMap (\x -> concatMap (\y -> [x+y]) [0,2]) [0,1]
[0,2,1,3]

with some effort, I think one can understand what happens here. It
should also be clear how this is generalized to liftM3, liftM4, etc. 

Oh, btw, what about liftM1? Obviously, this should be the following:

liftM1 f a

    = { definition }

do { x <- a ; return f a }
  
    = { same changes as above }

concatMap (\x -> [f x]) a

    = { definition of concatMap }

concat (map (\x -> [f x]) a

    = { concating singletons can be simplified } 

map (\x -> f x) a

    = { eta-reduction }

map f a

i.e., liftM1 = map, which is indeed just fmap for lists, as already
pointed out.

You can use this to simplify the last line of the concatMap derivation
above:

concatMap (\x -> concatMap (\y -> [x+y]) b) a

    = { see above }

concatMap (\x -> map (\y -> x+y) b) a

    = { use operator section }

concatMap (\x -> map (x+) b) a

which is about as clear as possible a definition for liftM2 (+)


	Jürgen