# Why monads matter

Today, a friend of mine told me that he was writing a Sudoku solver in Haskell. I could not resist and also wrote a brute-force one. The code is ugly (I was trying to generate as short a program as possible), but it led me to interesting thoughts.

First, here is the code. Beware, you are supposed to know Haskell and monads to understand the comments following the code:

```
import Control.Monad (msum, mzero, MonadPlus)
import List (elemIndex, (\\), intersperse)
import Maybe (fromJust)
= [s!!(ll*9+cc) | ll <- [l..l+ln], cc <- [c..c+cn]]
get s (l, ln, c, cn) = [(f 0 9 1, 0, 0, 8), (0, 8, f 9 1 1, 0),
getall n s 0 27 3, 2, f 9 3 3, 2)] >>= get s
(f where f m d t = ((if m == 0 then n else n `mod` m) `div` d) * t
solve :: (Eq a, MonadPlus m) => [a] -> a -> [a] -> m [a]
= case elemIndex n s of
solve g n s Nothing -> return s
Just idx -> msum $ (g \\ getall idx s) >>= \x ->
return $ solve g n $ take idx s ++ [x] ++ drop (idx+1) s
= unlines $ "Solution:" : (flip map [0..8] $ \n -> sline n s)
showSudoku s where sline n s = concat $ intersperse " " $
map show $ get s (n, 0, 0, 8)
= do
main <- getContents
s let display = do
<- solve [1..9] 0 $ map read $ words s
choice return $ showSudoku choice
putStr $ fromJust display
```

The interesting piece here is not the code itself, which is indeed
pretty boring and unclear, it is the type declaration of the `solve`

function: its return type is `m [a]`

, where `[a]`

represents a completed
Sudoku grid and `m`

is a `MonadPlus`

instance. What is the point of
choosing a `MonadPlus`

type when, in the `main`

function, the result is
coerced to a `Maybe`

(which is a `MonadPlus`

instance) before being
printed by the usage of `fromJust`

?

The `Maybe`

type can contain zero or one result. It means that the code,
when executed, will either find no solution or return exactly one
solution which will then be printed. But what can we change if we want
to print **all** the solutions? (if we start from the empty
grid for example)

We are using Haskell after all. Instead of using a `Maybe`

type, we
might as well use a list. All right, the list type is also an instance
of the `MonadPlus`

class. It can contain nothing (empty list), one
result, or more. Let’s change the line containing `fromJust`

in `main`

by:

`mapM_ putStr display`

The use of `mapM_`

coerces the use of `solve`

to a list type. Now, all
the solutions will be printed, not only one of them.

If you want to try it, create a file called `empty`

containing 9 lines
of 9 space-separated zeroes:

```
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
```

and compile the program (either variant). Then you can feed it the
`empty`

sudoku grid:

```
% ghc -o sudoku sudoku.hs
./sudoku < empty
```

Monad matters. For real.