久しぶりにOcaml(pascalの三角形)

まずはふつうに

let rec pascal  = function
    1 -> [1]
  | n -> 
      let prev = pascal (n-1) in
      let right = 0 :: prev in
      let left = List.rev right in
	List.map2 (+) left right 

memo化したい

let pascal2  n =
  let mem = Array.init n (fun x -> []) in
  let rec loop  = function
      1 -> [1]
    | n -> 
	match mem.(n-1) with
	    [] -> 
	      let prev = loop (n-1) in
	      let right = 0 :: prev in
	      let left = List.rev right in
	      let result = List.map2 (+) left right in
		mem.(n-1) <- result;
		result
	  | l -> l
  in
    if n > 1 then loop n else []

memo化の関数と分離させたい

let memoize  n = 
  let mem = Array.init (n+1) (fun x -> []) in
    fun f  n ->
      match mem.(n) with
	  [] -> let result = f n in
	    mem.(n) <- result;
	    result
	| result -> result

let memopascal n =
  let mem = memoize n in
    mem pascal n

まだまだ上手く使えない。例外処理とか使って正負の処理とかしたいかも

追記

あー、最後のだとmemo化されていない。

追記2

何やっているんだろう。もともとmemo化が必要な処理じゃないじゃないか。
memo化が必要なのはこういう場合だった。

let rec fib  = function
    0 -> 0
  | 1 -> 1
  | n -> (fib (n-2)) + (fib (n-1))
      
let  memofib n = 
  let init = -1 in
  let mem = Array.init (n+1) (fun x -> init) in
  let rec calc = function
      0 -> 0 
    | 1 -> 1 
    | n -> (loop (n-2)) + (loop (n-1)) 
  and loop  n  = 
    match mem.(n) with
      | re when re == init ->
	  let result  =  calc n in
	    mem.(n) <- result;
	    result
      | re -> re  in
    (loop n)

追記3

こういう時にCPS変換を使えばいいのかも

let rec fib_cps n f =
  match n with
      0 ->  0 
    | 1 ->  1
    | _ ->
	f (n - 2) + f (n - 1 )

let rec memo_cps  fn_cps =
  fun n ->
    let mem = Array.init (n+1) (fun x-> -1) in
    let rec loop n =
      match mem.(n) with
	  v when v == -1 ->
	    let re = fn_cps n loop in
	      mem.(n) <- re;
	      re 
	| v -> v
    in loop n
	
let memo_fib_cps = memo_cps fib_cps
(* memo_fib_cps 70 *)

できた