Consider a recursive function, say the Euclid algorithm defined by:
let rec gcd a b =
let (q, r) = (a / b, a mod b) in
if r = 0 then b else gcd b r
(This is a simplified, very brittle definition.) How to memoize such a function? The classical approach of defining a high-order function memoize : ('a -> 'b) -> ('a -> 'b)
adding memoization to the function is here useless, because it will only save time on the first call.
I have found details on how to memoize such function in Lisp or Haskell:
These suggestions rely on the ability found in Lisp to overwrite the symbol definition of a function or on the “call-by-need” strategy used by Haskell, and are therefore useless in OCaml.