my first monadic program
Greg Bacon
monadic program to solve one of the Project Euler problems.
I put together a brief writeup and posted it to my blog. I first
describe using Maybe directly and then a few changes to express
more directly the intent.
I'll appreciate feedback and especially suggestions for improvement:
http://gbacon.blogspot.com/2007/02/my-first-monadic-program.html
Thanks,
Greg
--
... the consolidation of the states into one vast republic, sure to be
aggressive abroad and despotic at home, will be the certain precursor of
that ruin which has overwhelmed all those that have preceded it.
-- Robert E. Lee
Dirk Thierbach
> I learn best by doing, and I (finally) wrote my first non-trivial
> monadic program to solve one of the Project Euler problems.
Nice project.
> I'll appreciate feedback and especially suggestions for improvement:
>
> http://gbacon.blogspot.com/2007/02/my-first-monadic-program.html
Here's a different approach, also using monads:
The main trick for combinatorial problems is to reduce the number of
remaining choices as early as possible. A little bit of thinking shows
that there are only two possible forms of the equation: x * yyyy = zzzz
and xx * yyy = zzzz.
To implement it, we use a "generate and test" approach. Assume we
had a function "choose" to make a choice from the remaining digits.
We also need a function "verify" that checks if it's argument matches
a valid choice. We can implement it quickly using "guard" from MonadPlus:
> verify v = do
> c <- choose
> guard $ c == v
With those two, we can already write monadic functions for both forms:
> -- x * yyyy = zzzz
> form1 = do
> x1 <- choose
> y1 <- choose
> let (c1,z1) = (x1 * y1) `divMod` 10
> verify z1
> y2 <- choose
> let (c2,z2) = (x1 * y2 + c1) `divMod` 10
> verify z2
> y3 <- choose
> let (c3,z3) = (x1 * y3 + c2) `divMod` 10
> verify z3
> y4 <- choose
> let (c4,z4) = (x1 * y4 + c3) `divMod` 10
> verify z4
> guard $ c4 == 0
> return $ show x1 ++ "*" ++ concatMap show [y4,y3,y2,y1] ++
> "=" ++ concatMap show [z4,z3,z2,z1]
> -- xx * yyy = zzzz
> form2 = do
> x1 <- choose
> y1 <- choose
> let (c1,z1) = (x1 * y1) `divMod` 10
> verify z1
> x2 <- choose
> y2 <- choose
> let (c2,z2) = (x1 * y2 + x2 * y1 + c1) `divMod` 10
> verify z2
> y3 <- choose
> let (c3,z3) = (x1 * y3 + x2 * y2 + c2) `divMod` 10
> verify z3
> let (c4,z4) = (x2 * y3 + c3) `divMod` 10
> verify z4
> guard $ c4 == 0
> return $ concatMap show [x2,x1] ++ "*" ++ concatMap show [y3,y2,y1] ++
> "=" ++ concatMap show [z4,z3,z2,z1]
where the choices are ordered to be able to calculate and verify results
as early as possible. In this way, we have less than 9*8*6*4*2 + 9*8*6*5*3,
that is less than 9936 possibilities to check. That's much better than
40 million :-)
All that remains is to implement "choose". We need the list monad
for nondeterministic choice, and the state monad to keep track of the
remaining digits. So let's use a state monad transformer for the latter.
Now making a choice consists of splitting the list of remaining digits
into the choice and the remaining digits. Here's a helper for that:
> splits :: [a] -> [(a,[a])]
> splits l = splitAccum [] l where
> splitAccum ys [] = []
> splitAccum ys (x:xs) = (x,xs++ys) : splitAccum (x:ys) xs
Then "choose" is straightforward:
> choose :: StateT [a] [] a
> choose = StateT $ \s -> splits s
And while we're at it, we can implement "verify" more efficiently (though
it still makes two passes over the digit list):
> verify :: Eq a => a -> StateT [a] [] ()
> verify v = StateT $ \s ->
> if v `elem` s then [((), delete v s)] else []
Note how the empty list represents failure.
Nearly done, let's look at the results:
> run :: [String]
> run = evalStateT form1 [1..9] ++ evalStateT form2 [1..9]
and we get, very fast even on my old computer:
*Main> run
["4*1738=6952","4*1963=7852","12*483=5796","42*138=5796","27*198=5346",
"48*159=7632","28*157=4396","18*297=5346","39*186=7254"]
- Dirk
Greg Bacon
Greg
--
There are two ways of constructing a software design: One way is to make it
so simple that there are obviously no deficiencies, and the other way is to
make it so complicated that there are no obvious deficiencies. The first
method is far more difficult. -- C. A. R. Hoare