Problem 32 from Project Euler reads

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

Not one of my brighter moments, the first approach I considered was applying *goon*–force to permute a list of eleven characters (`'1' .. '9'`

, `'x'`

, and `'='`

) — a search space of almost 40 million — looking for well-formed and valid statements.

Initially, I looked at using Text.Regex. As I was fishing for examples to crib from, I saw a suggestion that people may as well use Parsec, the monadic parser combinator library. So let’s knock out the preliminaries:

```
> module Main where
>
> import Data.List hiding (map)
> import Text.ParserCombinators.Parsec
```

A parser for the simple expressions reads easily:

```
> num :: Parser Int
> num = do ns <- many1 digit
> return $ read ns
>
> expression :: Parser (Int,Int,Int)
> expression = do multiplier <- num
> times <- char 'x'
> multiplicand <- num
> equals <- char '='
> product <- num
> return (multiplier, multiplicand, product)
```

Generating permutations is no problem in Haskell:

```
> permutations :: [a] -> [[a]]
> permutations [x] = [[x]]
> permutations xs =
> [ y : zs
> | (y,ys) <- selections xs
> , zs <- permutations ys
> ]
>
> selections [] = []
> selections (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- selections xs]
```

I’d been wanting to solve as a learning example one of the Project Euler problems using monads. As I tried to shoehorn the problem into a monadic solution, I remembered the characterization of the `Maybe`

monad as being useful for computations that can fail, and I saw two possibilities for failure: garbage input (*e.g.*, `"x=123456789"`

) and false statements (*e.g.*, `"1x2=3456789"`

).

Having a particular permutation, `check`

tests whether it’s well–formed and valid:

```
check :: String -> Maybe Int
check s = do
result <- parseExpr s
p <- validProduct result
return p
parseExpr :: String -> Maybe (Int,Int,Int)
parseExpr s =
case parse expression "expression" s of
Left err -> Nothing
Right tuple@(mr,md,pr) -> return tuple
validProduct (mr, md, pr)
| mr * md == pr = Just pr
| otherwise = Nothing
```

The test goes just as you would describe it to someone else: parse the input to extract the multiplier, multiplicand, and product. Then check whether the operation holds. Simple.

Fitting these puzzle pieces together also helped another concept click. I remember reading characterizations of being “inside the monad” and feeling mystified. Notice, for example, that `parseExpr`

has type `String`

→ `Maybe (Int,Int,Int)`

. That is, given a string, the result is either `Nothing`

or `Just x`

, where *x* is a 3-tuple. Another way to think about the latter case is `Just`

with some `(Int,Int,Int)`

*inside* it.

Continuing the concept, consider how `parseExpr`

is used in `check`

. The result from `parseExpr`

becomes on the next line an argument to `validProduct`

. You might be tempted to object that the types don’t line up! `validProduct`

wants a plain tuple, but `parseExpr`

gives `Maybe (Int,Int,Int)`

.

For the program to typecheck, `result`

must be a tuple with no wrapper. When “inside the monad,” you can directly access the value without having to explicitly unwrap it.

You wonder, *‘But what about when the parse fails or when the statement is bogus?’* In addition to implicitly unwrapping, the `Maybe`

monad and do-notation syntactic sugar are checking these cases too! “Control” (to borrow an imperative concept) reaches the `return p`

line only if both `parseExpr`

and `validProduct`

succeed. Otherwise, `check`

bails where the failure occurs and returns `Nothing`

.

All that’s left to do is feed it input and sum the result. Note: it’s very s-l-o-w.

```
p32 = sum $ elems $ fromList $ catMaybes $ map check (permutations cs)
where cs = ['1','2','3','4','5','6','7','8','9','x','=']
```

An obvious improvement is to use `nub`

instead of `(elems . fromList)`

. Even better, lists are also monads, so `Maybe`

distractions disappear with only a few very minor changes:

```
> p32 = sum (nub $ concatMap check (permutations cs))
> where cs = ['1','2','3','4','5','6','7','8','9','x','=']
>
> main = print p32
>
> check :: (Monad m) => String -> m Int
> check s = do
> result <- parseExpr s
> p <- validProduct result
> return p
>
> parseExpr :: (Monad m) => String -> m (Int,Int,Int)
> parseExpr s =
> case parse expression "expression" s of
> Left err -> fail (show err)
> Right tuple@(mr,md,pr) -> return tuple
>
> validProduct :: (Monad m) => (Int,Int,Int) -> m Int
> validProduct (mr, md, pr)
> | mr * md == pr = return pr
> | otherwise = fail "invalid product"
```

This works because failure in the list monad is the empty list, and `concatMap`

gets rid of all the empties.