Memoizing tail call optimized recursive functions in F#

Question

Possible Duplicate:
Combine memoization and tail-recursion

So the following is the code that I wrote, tail call optimized using an accumulation variable

let rec counter init count = 
if init = 1 then count + 1 else
match init with
| Even value -> (counter (value/2)  (1 + count))
| Odd value -> (counter ((3 * value) + 1) (count+1))

let SeqBuilder (initval:int) : int = counter initval 0

How do I memoize this? the problem I ran into when I tried to memoize it is that the recursive call has to go to the memoize object, so you have to have a...recursive object?

Or is it a lot simpler and I am just inexperienced?

Answer 1

F# allows you to define a recursive value (like recursive object that you mentioned), so if you have memoize2 function to do the memoization (taking a function of two arguments - to make it compatible with your counter), then you can write:

let rec counter = memoize2 (fun init count ->
  if init = 1 then count + 1 else 
  match init with 
  | Even value -> (counter (value/2) (1 + count)) 
  | Odd value -> (counter ((3 * value) + 1) (count+1)) )

Recursive references like this can be dangerous, so F# inserts some runtime checks. It also gives a warning FS0040 to notify you about this, but in this case the recursion is correct (a problem could occur if the recursive reference was accessed during initialization - here we use it only later, when the function is already declared, so everything is fine). You can disable the warning by adding #nowarn "40".