I couldn't help but notice that the Haskell program to solve the given
cryptarithm is very different indeed from the C++ or Mercury
implementations. It selects from a set represented by a list (and
does repeated list difference using \\) rather than generating and
testing permutations. Here's a generate-and-test version of the same
algorithm (which I alas can't run through Hugs at the moment, so
apologies for any gross errors):
import List
-- All permutations of all elements
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (a:as) =
[ r | p <- permutations as, r <- allins a p]
-- All insertions of a into ps.
allins :: a -> [a] -> [[a]]
allins a ps =
(a:ps):case ps of
[] -> []
(p:ps) -> map (p:) (allins a ps)
expand a b c d e f = f + e*10 + d*100 + c*1000 + b*10000 + a*100000
digits = [0,1..9] -- all the digits
answer = head [ [t,h,i,r,y,w,e,l,v,n] |
[t,h,i,r,y,w,e,l,v,n] <- permutations digits,
expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y]
Of course, the big thing to note here is I had to roll my own
"permutations" function (luckily I happened to have one sitting
around, but allins is not especially pretty at the cost of being a bit
more lazy than the obvious definition:
allins a [] = [a]
allins a ps'@(p:ps) = (a:ps') : map (p:) (allins a ps)
I'm sure there's a better permutations definition, and that a bit of
thought would turn it up. Which leads to a bigger question---why
isn't "permutations" or something of the sort in List? It seems
Mr. Engleberg (and, not coincidentally, students in our multithreading
class at MIT) would benefit from having such a function in the
libraries. This is certainly the reason the C++ is so brief.
[My instinct from using Haskell for teaching, by the way, is that most
uses of (\\), especially in list comprehensions, could be done better
using some other algorithm! Most frequently, it's turned out to be
something permutation-like or partitioning-like. But then, I have a
mental performance model that says "(\\) is n squared", which doesn't
leap readily to the minds of new haskell users.]
-Jan-Willem Maessen
