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

From: padiolea@irisa.fr
> Yes but this ocaml code use array ?
> In that case it supports what the "troll" said, that is
> the resulting code is no more "functionnal".
> I agree with eijro sumii that ocaml is not just about functionnal
> programming but in the mind of many people advocating ocaml is advocating
> functionnal programming.
> 
> I think the way to answer to those trolls is to teach them the way
> to do, in that case to use Map instead of associative list, and
> not to be pretentious and to tell that he is just a newbie.
> He is not a newbie, this garden optimization problem is not that simple.

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