[Haskell-cafe] Heavy lift-ing

[michael rice]

Thanks all,

Wild, at least up to the "optional" part, which I haven't dug into yet.

So the (+) for the Maybe monad and the (+) for the List monad are one in the same, the magic springs from the monads.

Why is it called "lift"-ing?

Michael


--- On Fri, 7/23/10, Jürgen Doser <jurgen.doser at gmail.com> wrote:

From: Jürgen Doser <jurgen.doser at gmail.com>
Subject: Re: [Haskell-cafe] Heavy lift-ing
To: "michael rice" <nowgate at yahoo.com>
Cc: haskell-cafe at haskell.org
Date: Friday, July 23, 2010, 4:50 PM

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






      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100723/8ef63409/attachment.html