The List Monad via Cont

Simulating the list monad via the Cont monad isn't quite as natural as simulating State, Reader, Writer, and Maybe. For those four monads, the code written using their C-versions looked identical to the code written using the original versions, with the minor exception that when programming using MaybeC, we used functions nothing and just instead of the data constructors Nothing and Just. For the list monad, we need a little helper function choose. Every time we an expression

x <- someList

in a do-block in the list monad, we will now use

x <- choose someList

That's the only change in the code. The correct implementation of choose will give us the behaviour of the list monad.

Let's recap how the list monad works. In the expression xs >>= f, we apply f to every element of xs. In our Cont-based list monad, we want that choose xs >>= f applies f to every element in xs. Since f is a continuation, we want to run this continuation multiple times, once per element in xs. This is exactly the type of thing the Cont monad is made for: explicitly manipulating continuations and choosing to run them not at all, again, and again, and again—whatever we want. So here's our list monad then

type ListC r a = Cont [r] a

choose :: [a] -> ListC r a
choose xs = Cont $ \k -> concatMap k xs

runList :: ListC r r -> [r]
runList f = runCont f (\x -> [x])

choose is really where the logic of the list monad lives. Since we're in the ListC r monad, that is, in the Cont [r] a monad, k is a continuation that expects a value of type a and produces a list of rs from it. What we want to do is to apply k to every element in xs and collect the results. Without the Cont wrapper, this is simply

choose xs k = concatMap k xs

Compare this to the implementation of (>>=) for the list monad:

xs >>= k = concatMap k xs

or, in prefix notation,

(>>=) xs k = concatMap k xs

choose is identical to the implementation of (>>=) for the list monad.

There isn't really a very simple example of the list monad that is also interesting. So let's go with a boring one then, for now using the normal list monad. First we have a function

thisOrNext :: Int -> [Int]
thisOrNext x = [x, x + 1]

Viewed as a non-deterministic function, it returns x or the next value x + 1. We also have a function

evens :: Int -> [Int]
evens m = [0, 2 .. m]

Given an upper bound m, it returns all even numbers from 0 up to m or, viewed as a non-deterministic function, it returns any even number between 0 and m. Now what does the following function compute then?

mysteryFunction :: Int -> [Int]
mysteryFunction m = do
    x <- evens m
    thisOrNext x

First it picks an even number between 0 and m. Then it applies thisOrNext to it, which returns either x or x + 1. Thus, if m is odd, this produces any number between 0 and m. If m is even, it produces any number between 0 and m + 1. Indeed, to produce an even number x, we need evens m to pick this number, and then thisOrNext x should just pick x. If x is odd, then evens m should pick x - 1, and then thisOrNext (x - 1) should pick x. Let's try it out:

GHCi

>>> thisOrNext x = [x, x + 1]
>>> evens m = [0, 2 .. m]
>>> :{
  | mysteryFunction m = do
  |     x <- evens m
  |     thisOrNext x
  | :}
>>> mysteryFunction 7
[0,1,2,3,4,5,6,7]
>>> mysteryFunction 8
[0,1,2,3,4,5,6,7,8,9]

Now let's implement it using ListC:

As I said, every time we explicitly use a list when programming using a list monad, this now requires the use of choose. Thinking choose as a non-deterministic function, it picks an arbitrary value from the given list. Our versions of thisOrNext and evens for the ListC r monad are:

thisOrNext :: Int -> ListC r Int
thisOrNext x = choose [x, x + 1]

evens :: Int -> ListC r Int
evens m = choose [0, 2 .. m]

Our implementation of mysteryFunction does not change. Only its type changes:

mysteryFunction :: Int -> ListC r Int
mysteryFunction m = do
    x <- evens m
    thisOrNext x

And now we can try this all out using GHCi. It works as expected:

GHCi

>>> type ListC r a = Cont [r] a
>>> choose xs = cont $ \k -> concatMap k xs
>>> runList f = runCont f (\x -> [x])
>>> thisOrNext x = choose [x, x + 1]
>>> evens m = choose [0, 2 .. m]
>>> :{
  | mysteryFunction m = do
  |     x <- evens m
  |     thisOrNext x
  | :}
>>> runList (mysteryFunction 7)
[0,1,2,3,4,5,6,7]
>>> runList (mysteryFunction 8)
[0,1,2,3,4,5,6,7,8,9]

This discussion of continuations and of the Cont monad got much longer than I thought it would. It just happens to be a very interesting monad. Now on to the last topic you need to learn about before you can build complete programs: modules. This is a much less exciting topic, but it is important for writing maintainable code, and you shouldn't have any problems understanding it. It's not even about programming in Haskell but rather about how to organize our code by splitting it into multiple source code files.