The List Monad

Like Maybe, [] is also a type constructor elevated into a Functor, Applicative, and Monad.

The code that turns [] into a Functor follows:

instance Functor [] where
   fmap = map

The previous code can be written equivalently:

instance Functor [] where
   fmap _ [] = []
   fmap f (x:xs) = f x : fmap f xs

The code that turns [] into an Applicative follows:

instance Applicative [] where
   pure x = [x]
   fs <*> xs = [ f x | f <- fs, x <- xs ]

The previous code can be written equivalently:

instance Applicative [] where
   pure a = [a]          
   [] <*> _  = []
   (f:fs) <*> as = map f as ++ fs <*> as

The code that turns [] into a Monad follows:

instance  Monad []  where
   return x = [x]
   m >>= k = concat (map k m)

The previous code can be written equivalently:

instance Monad [] where
   return x = [x]
   xs >>= f =
      let yss = map f xs
      in concat yss

Just as in the case of Maybe, we do not have to include any of the previous code, because it is already built in Haskell. But, just as in the case of Maybe, studying this code will be of great help to us.

OK, let us discuss what we just saw. First of all, for [] to become a Functor, we need to decide how we want to apply a function to a list of elements. The decision taken by Haskell is to apply the function to each element of the list. There is a way to apply a function to all elements of a list. A function that does that already exist and it is the map function. Thus, the fmap function that we must create to do this job is the map function.

For [] to become an Applicative, we need to decide how we want to apply a list of functions to a list of elements. The decision taken by Haskell is to apply each function from the list of functions to all elements from the list of elements.

For [] to become a Monad, we must decide how to implement bind (>>=). Bind has to take a list object m and a function k with type signature of the type of a list element to the type of the list, thus something like a -> [b]. The decision taken by Haskell is to take the list m and apply the function k (of type a -> [b]) to each element of the list. Since we will get a list of lists as output, whereas we only want a list, in order to be consistent with the type of >>=, we need to flatten the resulting list of lists to a list, and this can e done by applying the function concat.

The astute reader will remember my blog post “The correspondence between Monads in Category Theory and Monads in Haskell”. I that blog post, I have explained how to derive the following relationship between bind and other functions for a Monad:

m >>= k is equivalent to join . fmap k . m

In the case of the [] Monad, this holds true, (as it should for all Monads).

Indeed, join for the [] Monad is the concat function. This is because join for any Monad has the type M (M a) -> M a, i.e. join “flattens” the Monad space. As far as list are concerned, concat has the type [[a]] -> [a]. Thus concat is the join function for lists.Also, fmap for the [] Monad is the fmap function. Thus:

join . fmap k . m can be written as concat . map k . m, or, equivalently, as concat (map k m), which is the definition used for >>= in the previous code.

Again, let me stress why we need join, i.e. concat. We need join because fmap applies a function k of type a -> m b, thus a function of type a -> [b]. This function is applied to an object of type m a, thus an object of type [a]. The result will be an object of type m (m b), thus [[b]]. Thus, we need a join in the end, in order to collapse, to flatten the m (m b) to m b, thus to flatten the [[b]] to [b].

So, when we write concat (map k m)m is of type [a], k if of type a -> [b], the output of map k m is of type [[b]] and the output of concat (map k m) is of type [b].

Thus, a great way to create the definition for >>= is to use the following equation that we learned and proved in my blog post “The correspondence between Monads in Category Theory and Monads in Haskell”:

g >>= f is equivalent to join . fmap f . g

Of course, for a simple case like the Maybe Monad, this may be overkill. For the Maybe Monad, bind is implemented as follows:

Just x >>= f  = f x

We could have implemented it using join ad fmap, but it would have been overkill and redundant. Instead of the simple definiton

Just x >>= f  = f x

we would have

Just x >>= f  = join (fmap f  (Just x))

where f is of type a -> Maybe b. Thus fmap would have created an object of type Just (f x), and since f x is of type a -> Maybe b, the object Just (f x) would be of type Just (Just x)). Thus we would need the join in the declaration to flatten Just (Just x)) to Just x. So we save ourselves the back and forth by the simpler definition

Just x >>= f  = f x.

But, yes, in cases that are more complex, it may be a good practice, or the only practice, to create bind (g >>= f) as join . fmap f . g.

OK, let us see now how [] functions as a type constructor, Functor, Applicative and Monad, using a small proof-of-concept program:

module Main where

import Control.Applicative

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that [] behaves as a type constructor."

      print ([1])
      print ([1,2,3,4])
      print ([("hello",100),("world",200)])

      putStrLn "Tests that prove that [] behaves as a Functor."

      print (fmap length ["this", "is", "a", "nice", "bike"])
      print (fmap (\x -> x + 1) [100, 200, 300])

      putStrLn "Tests that prove that [] behaves as an Applicative."

      print ([(*2),(+100)] <*> [1,2,3,4])
      print ([fst, snd] <*> [(1,2),(100,200)])

      putStrLn "Tests that prove that [] behaves as a Monad."

      print ([10,20,30] >>= (\x -> [x+1, x+2, x+3]))
      print ([(1,2), (3,4), (5,6)] >>= (\x -> [(snd x, fst x)]))

      putStrLn  "Bonus section: >>= behaves like the function concatMap."

      print (concatMap (\x -> [x+1, x+2, x+3]) [10,20,30])
      print (concatMap (\x -> [(snd x, fst x)]) [(1,2), (3,4), (5,6)])

      putStrLn "Program ends."

This is the output of the previous program:

Program begins.
Tests that prove that [] behaves as a type constructor.
[1]
[1,2,3,4]
[("hello",100),("world",200)]
Tests that prove that [] behaves as a Functor.
[4,2,1,4,4]
[101,201,301]
Tests that prove that [] behaves as an Applicative.
[2,4,6,8,101,102,103,104]
[1,100,2,200]
Tests that prove that [] behaves as a Monad.
[11,12,13,21,22,23,31,32,33]
[(2,1),(4,3),(6,5)]
Bonus section: >>= behaves like the function concatMap.
[11,12,13,21,22,23,31,32,33]
[(2,1),(4,3),(6,5)]
Program ends.
Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.