I did find the Haskell samples instructive, though I don't want to get sidetracked from my project of learning F#. To this end I've once again resorted to Don Syme's thoughts on memoization: here on the CAML list, and here more recently, where he avails himself of some popular .NET collections. So a memoized Fibonacci function in Dr. Syme's older formulation looks like this:
Several problems at Project Euler ask you to do something with the first 10 or last 10 digits of some big integer; for anyone who was wondering how to do that with a number such as the one above, here's one way:
> #light;;
> let cache f =
 let table = ref [] in
 fun n >
 try
 List.assoc n !table
 with Not_found >
 let f_n = f n in
 table := (n, f_n) :: !table;
 f_n


 let rec fib_mem =
 cache (function
 // You'd better return a bigint, not an int!
 ¦ 0 > 0I
 ¦ 1 > 1I
 ¦ n > fib_mem (n  1) + fib_mem (n  2))


 ;;
val cache : ('a > 'b) > ('a > 'b)
val fib_mem : (int > bigint)
> fib_mem(1000);;
val it : bigint
= 434665576869374564356885276750406258025646605173717804024817290895365554179490
51890403879840079255169295922593080322634775209689623239873322471161642996440906
533187938298969649928516003704476137795166849228875I
val ns : seq
You'll notice that the least significant digits appear first, which is of course by design, since dividing by 10 is probably cheap. The last thing I'd want to do is reverse this sequence, i.e.
> fib_mem(1000) > Seq.unfold (fun n > if n > 0I
 then
 let quotient,remainder = BigInt.divmod n 10I
 Some (remainder, quotient)
 else
 None);;
val it : seq= seq [5I; 7I; 8I; 8I; ...]
>
I could clean this up further by applying BigInt.to_Int32 to the generated elements, etc. To sum the first 10 digits (note that this is *not* the Project Euler problem; I'm not about to give away any answers) I could go further, like so:
 > List.of_seq
 > List.rev;;
You get the idea.
 > Seq.take 10
 > Seq.fold1 (+);;
No comments:
Post a Comment