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))))))))))))))))))))))))