35

Can anyone explain (better with an example in plain English) what a list monad can do to model non-deterministic calculations? Namely what the problem is and what solution a list monad can offer.

1
  • 1
    Good answers in here. To add something I think sequence is a good example of this. For example sequence ["cbs","ae","tb"] would give you all the ways you can pick one letter from each element to form a word.
    – DiegoNolan
    Dec 17, 2013 at 17:22

4 Answers 4

48

Here's an example based on coin tossing. The problem is as follows:

You have two coins, labeled Biased and Fair. The Biased coin has two heads, and the Fair coin has one head and one tail. Pick one of these coins at random, toss it and observe the result. If the result is a head, what is the probability that you picked the Biased coin?

We can model this in Haskell as follows. First, you need the types of coin and their faces

data CoinType = Fair | Biased deriving (Show)

data Coin = Head | Tail deriving (Eq,Show)

We know that tossing a fair coin can come up either Head or Tail whereas the biased coin always comes up Head. We model this with a list of possible alternatives (where implicitly, each possibility is equally likely).

toss Fair   = [Head, Tail]
toss Biased = [Head, Head]

We also need a function that picks the fair or biased coin at random

pick = [Fair, Biased]

Then we put it all together like this

experiment = do
  coin   <- pick         -- Pick a coin at random
  result <- toss coin    -- Toss it, to get a result
  guard (result == Head) -- We only care about results that come up Heads
  return coin            -- Return which coin was used in this case

Notice that although the code reads like we're just running the experiment once, but the list monad is modelling nondeterminism, and actually following out all possible paths. Therefore the result is

>> experiment
[Biased, Biased, Fair]

Because all the possibilities are equally likely, we can conclude that there is a 2/3 chance that we have the biased coin, and only a 1/3 chance that we have the fair coin.

8
  • 2
    Can the next person who comes here leave a comment saying where you came from? I'm curious to learn why this answer suddenly started getting a load of upvotes a year later! Dec 4, 2014 at 8:19
  • I'm doing a course on edx on Haskell and trying to learn about monads. I was brought here by a google search. Dec 5, 2014 at 15:57
  • @ChrisTaylor Linked to recently from here: stackoverflow.com/q/29886852/1463507 . Good answer none the less!
    – kqr
    Apr 27, 2015 at 8:50
  • how is this comparable with model checking as in PROMELA? will it be as performant as SPIN when having lots of state? will GHC build Büchi automatas from this? Oct 6, 2015 at 19:32
  • 1
    @JanusTroelsen GHC will build a list containing every possible output, including repeated outputs. For this reason it is generally very inefficient (e.g. it has no way to collapse multiple paths with the same result into a single path). There are some approaches to modelling distributions based on sets or associative arrays (maps) that can collapse equivalent states efficiently, but you normally need to be quite careful so as not to get accidental explosion of the state space. At the moment, probability-oriented languages have the edge over general purpose languages like Haskell for this task. Jan 4, 2016 at 10:59
21

When we say that it is non-determinism, it means that it has more than one values.

The Learn You A Haskell book nicely explains this:

A value like 5 is deterministic. It has only one result and we know exactly what it is. On the other hand, a value like [3,8,9] contains several results, so we can view it as one value that is actually many values at the same time. Using lists as applicative functors showcases this non-determinism nicely:

ghci> (*) <$> [1,2,3] <*> [10,100,1000]  
[10,100,1000,20,200,2000,30,300,3000]

All the possible combinations of multiplying elements from the left list with elements from the right list are included in the resulting list. When dealing with non-determinism, there are many choices that we can make, so we just try all of them, and so the result is a non-deterministic value as well, only it has many more results.

List monad models non-determinism nicely. Its instance is like this:

instance Monad [] where  
    return x = [x]  
    xs >>= f = concat (map f xs)  
    fail _ = [] 

So, when you feed a non-deterministic value it will produce another set of non-deterministic value:

ghci> [3,4,5] >>= \x -> [x, x * 2]
[3,6,4,8,5,10]
11

So, it's important to clearly define what 'non-determinism' means here, since it's not quite the same as how it might be perceived in, say, a non-deterministic algorithm. The sense being captured here is that the computation branches - there may be multiple states that the system can move to at any particular point.

Lists model this because, simply, they contain multiple elements. What's more, monadic comprehensions give us a way to compose non-deterministic results - that is, to model exploring all branches at once.

11

The list monad can be though of representing "all possible results from a non-deterministic computation". For example, the function

f x = [x, x + 1, x + 2]

can be interpreted as a non-deterministic computation that takes x and returns one of x, x+1 and x+2.

The function

g x = [2 * x, 3 * x]

can be interpreted as a non-deterministic computation that takes x and returns either 2 * x or 3 * x. The "composition" of these two non-deterministic computations should be another non-deterministic computation which takes x, transforms it to one of x, x + 1 or x + 2, and then then either doubles it or triples it. Thus in terms of lists the result should be a list of all six possibilities

Now

g =<< f x = [2 * x, 3 * x, 2 * (x + 1), 3 * (x + 1), 2 * (x + 2), 3 * (x + 2)]

so indeed this models non-determinism as we expected.

(There is some awkwardness to using lists for non-determinism, since they also have a ordering of elements. A "set monad" would probably be a more natural way to model non-determinism. Lists certainly contain enough information to model non-determinism, but the ordering means that we have more information than necessary.)

EDIT: in fact what I wrote only really goes as far as using the list applicative instance. To get something that fully takes advantage of the monadic interface you want a computation that returns a number of results that depends on its input, for example

g 0 = [1000, 1001]
g x = [2 * x, 3 * x, 4 * x]

although admittedly this is a completely arbitrary and unmotivated example!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.