Control.Monad.Reader

Everything About Mathematics, Functional Programming, and Haskell

Understanding Functions Which Use ‘instance Monad []’ by Equational Reasoning

leave a comment »


GüŸnther Schmidt asked in Haskell-Cafe how to get a stream like this:

        ["a", ... , "z", "aa", ... , "az", "ba", ... , "bz", ... ]

and people in Haskell-Cafe offer some interesting answer for this question. On the one hand, these answers show the power of Haskell and GHC base libraries, but on the other hand, understanding them is a challenge for Haskell newbie like me. But I found to understand these answers, equational reasoning is very helpful, here is why I think so.

        Answer 1 (by Matthew Brecknell):

        concat $ tail $ iterate (map (:) ['a' .. 'z'] <*>) [[]]

Well, how does this expression do what we want? concat, tail, iterate, map, are easy, looks like the magic is in (<*>).

What’s this operator mean? (<*>) comes from class Applicative of Control.Applicative,

        class Functor f => Applicative f where
                – | Lift a value.
                pure :: a -> f a

                – | Sequential application.
                (<*>) :: f (a -> b) -> f a -> f b

and ‘instance Applicative []’ is

        instance Applicative [] where
                pure = return
                (<*>) = ap

ap comes from Control.Monad

        ap :: (Monad m) => m (a -> b) -> m a -> m b
        ap =  liftM2 id

        liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
        liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }

so the key to understand (<*>) is understanding the meaning of liftM2.

liftM2 uses, hum, do-notation, so according to Haskell 98 report, this can be translated to

          liftM2 f m1 m2
        = m1 >>= \x1 ->
          m2 >>= \x2 ->
          return (f x1 x2)

When it is applied to list (you can convince yourself of this by type inference), wee need ‘instance Monad []’

        instance  Monad []  where
                m >>= k             = foldr ((++) . k) [] m
                m >> k              = foldr ((++) . (\ _ -> k)) [] m
                return x            = [x]
                fail _              = []

so
          liftM2 f m1 m2
        = m1 >>= \x1 ->
          m2 >>= \x2 ->
          return (f x1 x2)

let
          f1
        =        \x1 ->
          m2 >>= \x2 ->
          return (f x1 x2)

          f2
        = \x2 -> return (f x1 x2)

we can write

          m1 >>= f1
        = foldr ((++) . f1) [] m1

          m2 >>= f2
        = foldr ((++) . f2) [] m2

Now we can see for list m1, m2, how does ‘liftM2 f m1 m2′ work

        z1 = []
        foreach x1 in (reverse m1); do          – foldr ((++) . f1) [] m1
            z2 = []
            foreach x2 in (reverse m2); do      – foldr ((++) . f2) [] m2
                z2 = [f x1 x2] ++ z2
            done
            z1 = z2 ++ z1
        done

Now we are ready to see how to apply (<*>):

          map (:) ['a' .. 'z'] <*> [[]]
        = (map (:) ['a' .. 'z']) <*> [[]]
        = [('a':), ..., ('z':)] <*> [[]]        – misuse of [...] notation
        = ap [('a':), ..., ('z':)] [[]]
        = liftM2 id [('a':), ..., ('z':)] [[]]
        = [('a':), ..., ('z':)] >>= \x1 ->
          [[]]                  >>= \x2 ->
          return (id x1 x2)

Here x1 bind to (‘z’:), …, (‘a’:) in turn, x2 always bind to [], and noticed that

          return (id (‘z’:) [])         — f = id; x1 = (‘a’:); x2 = []
        = return ((‘z’:) [])
        = return ((:) ‘z’ [])
        = return "z"
        = ["z"]

we have
          map (:) ['a' .. 'z'] <*> [[]]
        = liftM2 id [('a':), ..., ('z':)] [[]]
        = ["a", ..., "z"]

(If you can’t follow the this, work through the definition of foldr step by step will be very helpful.)

          map (:) ['a' .. 'z'] <*> (map (:) ['a' .. 'z'] <*> [[]])
        = map (:) ['a' .. 'z'] <*> ["a", ..., "z"]
        = liftM2 id [('a':), ..., ('z':)] ["a", ..., "z"]
        = ["aa", ..., "az", "ba", ..., "bz", ..., "za", ..., "zz"]

Now it’s easy to know what we get from

          iterate (map (:) ['a' .. 'z'] <*>) [[]]
        = [[], f [[]], f (f [[]]), …]         — f = map (:) ['a' .. 'z'] <*>

so
        concat $ tail $ iterate (map (:) ['a' .. 'z'] <*>) [[]]

is exactly what we want.

Understanding Haskell codes by equational reasoning could be a very tedious process, but it’s also a very helpful and instructive process for the beginners, because it make you think slowly, check the computation process step by step, just like the compiler does. And in my opinion, this is exactly what a debugger does.

        Answer 2 (by Reid Barton):

        concatMap (\n -> replicateM n ['a'..'z']) [1..]

In this solution, the hardest part is replicatM, which come from Control.Monad

        replicateM        :: (Monad m) => Int -> m a -> m [a]
        replicateM n x    = sequence (replicate n x)

        sequence       :: Monad m => [m a] -> m [a]
        sequence ms = foldr k (return []) ms
                    where
                      k m m’ = do { x <- m; xs <- m’; return (x:xs) }

recall the defintion of liftM2:

        liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
        liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }

so k in definition of sequence is an application of liftM2, and sequence itself is a normal foldr.

Exercise:

        Suppose n and xs have appropriate types, prove that

                replicateM n xs = (iterate (map (:) xs <*>) [[]]) !! n

        by equational reasoning.

Answer:

        replicateM n xs = (iterate (map (:) xs <*>) [[]]) !! n

        Definition of replicateM:

                replicateM :: (Monad m) => Int -> m a -> m [a]
                replicateM n x = sequence (replicate n x)

                sequence :: Monad m => [m a] -> m [a]
                sequence ms = foldr k (return []) ms
                            where
                              k m m’ = do { x <- m; xs <- m’; return (x:xs) }

        Definition of (<*>):

                instance Applicative [] where
                        pure = return
                        (<*>) = ap

                ap :: Monad m => m (a -> b) -> m a -> m b
                ap = liftM2 id

                liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
                liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }

        so
                replicateM n xs
                = sequence (replicate n xs)
                = sequence [xs, ..., xs]                – length [xs, ..., xs] == n
                = foldr k (return []) [xs, ..., xs]     — k = liftM2 (:)
                = foldr k [[]] [xs, ..., xs]
                = xs `k` (xs `f` … (xs `k` [[]]) …)
                = k xs (k xs … (k xs [[]]) …)
                = f (f … (f [[]]))                    – f = liftM2 (:) xs

        for right hand, because

                map (:) xs <*>
                = ap (map (:) xs)
                = liftM2 id (map (:) xs)
                = liftM2 (:) xs

        we have

                (iterate (map (:) xs <*>) [[]]) !! n
                = (iterate (liftM2 (:) xs) [[]]) !! n
                = f (f … (f [[]]))                    – f = liftM2 (:) xs

        Left hand and right hand are equal.

About these ads

Written by Lee Duhem

June 19, 2009 at 1:52 pm

Posted in Haskell

Tagged with ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: