This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

More problems with memoization
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Andrej Bauer Subject: Re: [Caml-list] More problems with memoization
```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

```