Re: [Caml-list] Help with simple ocaml memoization problem

["Evan Klitzke" <evan@yelp.com>]

On 11/28/07, Peng Zang <peng.zang@gmail.com> wrote:
> I don't know how to increase the stack size off the top of my head, but in
> general you want to avoid recursion on the stack anyways.  An easy way is to
> simply make the function tail recursive so the compiler can optimized it into
> a loop for you.  Here's a pretty faithful replication of your python code.
> Note I use Int64 instead of BigInt as I'm running OCaml 3.09.3.
>
> let ( ++ ) = Int64.add;;
> let ( ** ) = Int64.mul;;
> let ( %% ) = Int64.rem;;
> let ( // ) = Int64.div;;
> let l1 = Int64.of_int 1;;
> let l2 = Int64.of_int 2;;
> let l3 = Int64.of_int 3;;
> let cache = Hashtbl.create 1000000;;
>
> let collatz = function
>   | x when x %% l2 = l1 -> l3 ** x ++ l1
>   | x -> x // l2
> ;;
> let rec find_collatz_len = function
>   | x when x = l1 -> l1
>   | x when Hashtbl.mem cache x -> Lazy.force (Hashtbl.find cache x)
>   | x -> let ans = lazy (l1 ++ find_collatz_len (collatz x)) in
>       Hashtbl.add cache x ans;
>       Lazy.force ans
> ;;
> let lengths = Array.init 999999
>   (fun x -> let x = Int64.of_int (x+1) in (x, find_collatz_len x));;
> Array.sort (fun (a,b) (c,d) -> compare d b) lengths;;
> lengths.(0);;
>
>
> The use of laziness here is just so I can put the recursive call in the tail
> position -- a quick hack because I'm too lazy to spend time making it into a
> loop myself.
>
> There should really be some easy syntax to write BigInts or Int64s directly in
> the code.  Is there some camlp4 that does this somewhere?  And it would nice
> if Int64 operators were predefined in the module.

Thanks Peng. This is much easier to grok than the code that I
originally wrote! One question that I have is what is the difference
between the Map and Hashtbl modules? From the documentation they look
very similar -- why did you use Hashtbl here rather than Map?

-- 
Evan Klitzke <evan@yelp.com>