After reading about the stellar performance of the Haskell entries in the
ICFP contest, I started reading the Haskell documentation to learn more
about the language. My knowledge of functional programming languages
primarily comes from Scheme.
For the most part, I like the syntax of Haskell, and I really like the way
that pattern matching and list generators are such a fundamental part of the
language.
I decided to test out Haskell by writing a program to solve a cryptarithm
that a friend had showed me the day before. For those of you who are
unfamiliar with cryptarithms, the idea is that you are presented with an
arithmetic equation in which each digit is replaced by a distinct letter in
the alphabet. The puzzle is to find the mapping of letters to digits that
makes the equation valid. Typically, the letters used in the puzzle make
the equation seem mildly witty, such as "HOCUS + POCUS = PRESTO"
In this case, I was trying to solve the puzzle (best viewed in a
non-proportional font):
THIRTY
TWELVE
TWELVE
TWELVE
TWELVE
+ TWELVE
-----------------
NINETY
The algorithm is pretty straightforward - you just need to consider all
possible mappings of letters to digits, and test the equation to see if it
works.
This seems like a perfect opportunity to exploit Haskell's list generation
and lazy evaluation capabilities. The crux of the problem is to find a
concise way of describing the list of all permutations of digits. I don't
want to embarrass myself by posting my first attempt here, but I'll show you
my second, slightly-less naive approach to writing this program:
----------------------
import List
expand a b c d e f = f + e*10 + d*100 + c*1000 + b*10000 + a*100000
xs = [0,1..9] -- all the digits
answer = head [ [t,h,i,r,y,w,e,l,v,n] | t<-xs, e<-xs\\[t], h<-xs\\[t,e],
i<-xs\\[t,e,h],
r<-xs\\[t,e,h,i], y<-xs\\[t,e,h,i,r], w<-xs\\[t,e,h,i,r,y],
l<-xs\\[t,e,h,i,r,y,w], v<-xs\\[t,e,h,i,r,y,w,l],
n<-xs\\[t,e,h,i,r,y,w,l,v],
expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y]
------------------------------------
Impressively concise, but how does it run? Well, I loaded it into the HUGS
interpreter; typed answer, and after a couple minutes, the answer printed
out. Not too bad, but how would this compare to a solution in C++?
So I sat down and thought about how to solve the same problem using C++. As
you might expect, each language brings a different set of strengths to each
problem. C++ doesn't really have pattern matching, list generators, or any
of that good stuff in an easy to use fashion, but it does have a very
powerful toolkit of algorithms and structures made standard as part of the
Standard Template Library. In particular, there is a function that
mutatively changes an array into the "next permutation". If you invoke the
next_permutation function enough times, you eventually end up iterating
through all possible permutations.
So let's look at the final program in C++:
-------------------------------
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long expand (long a, long b, long c, long d, long e, long f)
{
return f+10*e+100*d+1000*c+10000*b+100000*a;
}
void main()
{
long t,h,i,r,y,w,e,l,v,n;
long temp[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<long> x(temp,temp+10);
while (1)
{
t = x[0];
h = x[1];
i = x[2];
r = x[3];
y = x[4];
w = x[5];
e = x[6];
l = x[7];
v = x[8];
n = x[9];
if (expand(n,i,n,e,t,y) == expand(t,h,i,r,t,y)+5*expand(t,w,e,l,v,e))
break;
next_permutation(x.begin(), x.end());
}
cout << t << h << i << r << y << w << e << l << v << n;
}
------------------------------
It's a little longer, but not unreasonably so. How does it run? Well,
running it inside the debugger, it generated the correct answer within a
couple of seconds.
This is a huge difference, and makes Haskell look incredibly slow by
comparison. The speed difference in this case is well worth the extra few
lines of code.
Presumably, since I am a total newcomer to Haskell, my Haskell program is
not truly representative of how to best implement this algorithm in Haskell,
so the comaprison to C++ is probably unfair.
So I ask you who are more experienced: What would be a better way to
implement this program in Haskell?
Looking forward to your responses,
Mark Engelberg
