English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
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: 2006-10-02 (23:00)
From: Andrej Bauer <Andrej.Bauer@f...>
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)
     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