Programming with the List Monad

(Short Introduction to Monads)

I intend to collect here, slowly, over time, examples of programming with the list monad.

Counting Coin Tosses

From How can non-determinism be modeled with a List monad?. To quote:

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?

Running this Haskell program shows that the answer is 2/3 (under natural assumptions on the coins). What is interesting about the program is how the code

experiment = do
  coin   <- pick        
  result <- toss coin   
  if (result==Head) then return coin else [] 

explores all possible experiments "by running inside the List-monad".

Non-Deterministic Automata

From A Short Introduction to Autmata and Haskell.

Run automata04 to see how the code

run :: (State -> Char -> [State]) -> State -> [Char] -> [State]
run delta q [] = return q
run delta q (c:cs) = do
  next <- delta q c 
  run delta next cs 

collects the outcomes of all possible computations of a non-deterministic automaton delta started in state q on a given input string.

Further Reading

School of Haskell: The List Monad.

Wadler's How to Replace Failure by a List of Successes

Bird's program to solve Sudoku. More Sudoku solvers in Haskell.