Implementing Monad for a custom List type in Haskell


As an extension to the previous blog, we finally reach the highest level of abstraction yet – the Monad. Let’s see how we can implement our custom List type as an instance of the Monad typeclass. Here is the definition of the Monad typeclass as given in the book:

class Applicative m => Monad m where
    return :: a -> m a

    (>>=) :: m a -> (a -> m b) -> m b

    return = pure

This means that in order to make our List type an instance of Monad, we will have to make it an instance of Functor as well as Applicative.

Here is a simple but comprehensive implementation:

data List a = Nil | Cons a (List a) deriving Show

append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys = Cons x (append xs ys)

instance Functor List where
    -- fmap :: (a -> b) -> List a -> List b
    fmap _ Nil = Nil
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Applicative List where
    -- pure :: a -> List a
    pure x = Cons x Nil

    -- (<*>) :: List (a -> b) -> List a -> List b
    Nil <*> _ = Nil
    (Cons g gs) <*> xs = fmap g xs `append` (gs <*> xs)

instance Monad List where
    -- (>>=) :: List a -> (a -> List b) -> List b
    Nil >>= _ = Nil
    (Cons x xs) >>= f = (f x) `append` (xs >>= f)

We also define some test data to work with, and a function called pairs that simply returns the cross-product of the two input lists.


-- test data
l1 :: List Int
l1 = Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 Nil))))

l2 :: List String
l2 = Cons "Hello" (Cons "World" (Cons "we" (Cons "meet" (Cons "again" Nil))))

pairs :: Monad m => m a -> m b -> m (a, b)
pairs xs ys = xs >>= \x ->
                ys >>= \y ->
                    return (x, y)

Note that the pairs function could also have been written using the do notation as follows:

pairs :: Monad m => m a -> m b -> m (a, b)
pairs xs ys = do x <- xs
                 y <- ys
                 return (x, y)

This is identical to the previous version since the do notation is simply syntactic sugar for the bind operator.

Sample test run:

*Main> :t l1
l1 :: List Int
*Main> l2
Cons "Hello" (Cons "World" (Cons "we" (Cons "meet" (Cons "again" Nil))))
*Main> pairs l1 l2
Cons (1,"Hello") (Cons (1,"World") (Cons (1,"we") (Cons (1,"meet") (Cons (1,"again") (Cons (2,"Hello") (Cons (2,"World") (Cons (2,"we") (Cons (2,"meet") (Cons (2,"again") (Cons (3,"Hello") (Cons (3,"World") (Cons (3,"we") (Cons (3,"meet") (Cons (3,"again") (Cons (4,"Hello") (Cons (4,"World") (Cons (4,"we") (Cons (4,"meet") (Cons (4,"again") (Cons (5,"Hello") (Cons (5,"World") (Cons (5,"we") (Cons (5,"meet") (Cons (5,"again") Nil))))))))))))))))))))))))
Advertisements

Speak your mind!

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s