Re: [Caml-list] More problems with memoization

[Tom <tom.primozic@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1262 bytes --]

In case you know me, you probably know what kind of solution I am going to
tell you...

Well, in case you don't... my solution is going to be dirty, is going to use
the undocumented Obj module (Obj.magic lets you change an ocaml value into
another ocaml value of any type).

-----------

The solution is to memoize the very make_mem function!

let make_mem' = function f ->
      let table = ref [] in
      function n ->
      try
       List.assoc n !table
      with Not_found ->
       let f_n = f n in
         table := (n, f_n) :: !table;
   f_n;;

let make_mem = make_mem' make_mem'

Well, the problem is, that the ocaml type inference forbids a function to
return a polymorphic value, so the type of make_mem' is only ('_a -> '_b) ->
'_a -> '_b. So the right thing to do here (as this type is, obviously,
incorrect) is to use Obj.magic:

let make_mem'' = Obj.magic make_mem'

let make_mem = (make_mem'' : ('a -> 'b) -> 'a -> 'b)

Now, the fibb will work as expected (instantaneously) and memoization will
be simple to apply. A bit of thinking is needed, of course, to reckon
whether my implementation is optimal and safe (not yielding unexpected
results, for example when you rename functions, use partial evaluation,
etc.). But it works.

Have fun, Tom

[-- Attachment #2: Type: text/html, Size: 2995 bytes --]