More problems with memoization - fa.caml

Message from discussion More problems with memoization

Andrej Bauer

View profile

More options Oct 2 2006, 7:03 pm

Newsgroups: fa.caml

From: Andrej Bauer <Andrej.Ba...@fmf.uni-lj.si>

Date: Mon, 02 Oct 2006 23:03:23 UTC

Local: Mon, Oct 2 2006 7:03 pm

Subject: Re: [Caml-list] More problems with memoization

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

Diego Olivier FERNANDEZ PONS wrote:

> In my first example you keep the type of [fib] and add a second function
> [fib_mem]. You can use anyone indifferently and hide the latter with the
> .mli
> val fib : int -> int = <fun>
> val fib_mem : int -> int = <fun>

If you want to keep the same type for fib, and have the memoized one, as
well as to have locality you can do something like this:

let make_memo f = ...

let rec make_rec f x = f (make_rec f) x

let fib, fib_mem =
let fib' self = function
| 0 -> 0
| 1 -> 1
| n -> self (n - 1) + self (n - 2)
in
make_rec fib', make_mem fib

(You will notice that make_rec is just the Y combinator.)

> When you compare your solution with what I am trying to do you see there
> is a big difference in locality and transparency

I fail to see this big difference, frankly, since all you're doing is
just a beta-reduction of what Jon and I suggested.

A recursive function _is_ the fixed point of a non-recursive one with an
"extra" argument. You may hide this fact if you wish, but I think it's
more honest to admit it to yourself. The "untied" version of fib has the
advantage that you can do many cool things to it: memoizing is just one
possibility.

Andrej

_______________________________________________
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

Reply to author Forward