How can non-determinism be modeled with a List monad?

Question

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.

Answer 1

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.