Nondeterminism in Haskell

In nondeterministic programming an expression may have more than one value. In SICP we are given the following logic puzzle with its Scheme solution:

"Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?" (SICP, pp. 418)

A Haskell version of the (almost) same solution follows (Control.Monad and Data.List are needed):

type Name = String
type Floor = Int

adjacent :: Floor -> Floor -> Bool
adjacent a b = abs (a-b) == 1

distinct :: [Floor] -> Bool
distinct l = l == nub l

dinesman :: [[(Name,Floor)]]
dinesman = do
  baker <- [1..5]         
  cooper <- [1..5]         
  fletcher <- [1..5]
  miller <- [1..5]         
  smith <- [1..5]         
  guard (distinct [baker,cooper,fletcher,miller,smith])         
  guard (baker /= 5)         
  guard (cooper /= 1)         
  guard (not (fletcher == 1) || fletcher == 5))         
  guard (miller > cooper)
  guard (not (adjacent smith fletcher))
  guard (not (adjacent fletcher cooper))
  return [("Baker", baker),
          ("Cooper", cooper),
          ("Fletcher", fletcher),
          ("Miller", miller),
          ("Smith", smith)]

Nondeterminism allows us to omit writing the loops that try all possible execution paths. Nondeterministic computing can be imagined as if the computer simultaneously tried all the possible branches of a computation, where the computation branches every time there are multiple choices to proceed, and stops the branches that yield no result, and finally, returns all results from the succeeded branches.

Our nondeterministic process proceeds as follows. Initially we state that each person may live in any five possible floors. That makes 3125 different initial branches to take. The first restriction drops all branches where two or more persons would share the same room. That leaves 120 active branches. The next restriction drops all branches where Baker is living on the top floor. The next restriction drops all branches where Cooper is living on the first floor, etc. Finally what we have is one remaining branch that is the only solution to the problem.

To understand the code, let's take a look on Haskell's MonadPlus class. The class defines two operations:

class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a

The operation mzero denotes failure while the operation mplus denotes choice or combination. Here are the semantics of the operations:

mzero >>= f = mzero
a `mplus` mzero = a
mzero `mplus` b = b
a `mplus` (b `mplus` c) = (a `mplus` b) `mplus` c

The first reads that if a failure is applied on some action, the result is still a failure. The second reads that if something other than a failure is added to a failure, the result is the non-failure thing. The third reads that if a failure is added to something other than a failure, the result is again the non-failure thing. The two previous definitions are thus analogous to logical OR. The last one reads that the mplus binary operation is associative.

It appears that lists are instances of MonadPlus, defined as below:

instance MonadPlus [] where
mzero = []
a `mplus` b = a ++ b

The previous means that with lists, the empty list represents a failure and appending represents combination.

Let's go back to the code. The guard operation which we use to make restrictions on branches is defined as follows:

guard :: MonadPlus m => Bool -> m ()
guard True = return ()
guard False = mzero

So guard is an operation that takes a boolean expression and returns a () value meaning "no information" if the boolean argument evaluates to true, and mzero if the boolean argument evaluates to false.

So when a single branch runs a guard operation in our code, at that point, we have some combination of the floor numbers for each person. If the predicate is true, the branch will continue normally. If the predicate is false, the guard yields a failure. From the definition of MonadPlus, we remember that a failure applied on anything yields a failure. It means that the first failing guard will fail the whole branch. Succeeding branches will return a list of name-floor pairs. The return value of the function is just a combination of the results of all succeeded branches.

Does it work?
>> dinesman
[[("Baker", 3), ("Cooper", 2), ("Fletcher", 4), ("Miller", 5), ("Smith", 1)]]