Well, since it seems difficult to hide that I'm an anonymous coward,
I add a few comments for the list.

From: padio...@irisa.fr

In this particular case, I believe the trouble is rather that the
problem is really geared toward a specific solution. Efficient
memoization requires efficient access to memoized results, which in
this case can be obtained by mapping states to integers. And there
happens to be a trivial mapping. Then any solution will have to
iterate on the states.

If you look at my translation, I do not mutate arrays (except for
memoization), and use no references. That is, the mapping from states
to integers is actually produced in a purely functional way, and
arrays are only there to provide O(1) access. Moreover state
representation uses lists and natural sharing, so that it is
reasonably space efficient.
I also use lists, pattern matching, and recursion, so I believe this
fulfills his requirement about being written in functional style.

Out of curiosity, I also wrote a purely functional version, where
memoizing is done through an array of lazy values.
  http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/garden3.ml
The code is actually slightly shorter. Performance is rather close.
On a Pentium M 1.8, for a 8x8 garden, I obtain (including memory usage)
   Garden.cpp  5.8s  6.1MB (g++ -O)
   Garden.cpp  4.5s  6.2MB (g++ -O3)
   garden2.ml  5.9s  8.3MB (ocamlopt)
   garden3.ml  10s   27.4MB (ocmalopt)
So you can see that garden2, while being almost purely functional,
is really equivalent in performance to his C++ code (which is a bit
dumb, but garden2 doesn't try to be more clever), while garden3 uses
more memory (as expected).

The only thing this example shows is that writing in a functional
language doesn't dispense you of doing a complexity analysis. In
particular the use of structural equality and association lists may
cost a lot in practice.
Some people may have a mystical belief that the compiler will
automatically improve your code through program transformation, but at
least in ocaml the situation is simple: the compiler does no
transformation whatsoever, so you get what you write.
And of course, SICP is a good reading before starting to write
in a functional programming language; I suppose all the structures I
used are explained there in detail.

Jacques Garrigue

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs