列挙によるOCamlの複雑なデータ型の自動的なメモ帳化？

Question

私はOCamlに数学的に記述されたアルゴリズムの実装を書いています。私は実装をきれいにして紙に近づけようとしており、パフォーマンスを改善するために暗記のような明確なテクニックしか使用していません。

残念ながら、memoizationは整数ではうまく機能しますが、大規模または複雑なデータ型の場合でもO（n）になります。メモの前にデータ型を列挙してO（1）のパフォーマンスを得ることは可能です。 たとえば、memo lenはまだO（n）になりますが、DroidMemoized.lenはO（1）になり、DroidMemoizedはDroidの代わりとなります。

DroidMemoizedをDroidから自動的に作成することはできますか？たとえば、モジュールEnumMemoは、let DroidMemoized = EnumMemo.Make(Droid)と書くことができますか？

module Droid = struct 
     type t = string 
     let empty = "" 
     let beep x = x^" notdroids" 
     let boop x = x^" lookingfor" 
     let len x = String.length x 
end 

let memo f = 
    let m = Hashtbl.create 9 in 
    fun x -> 
     try Hashtbl.find m x 
     with Not_found -> 
     let y = f x in 
      Hashtbl.add m x y; y 

module DroidMemoized = struct 
     (* Boilerplate *) 
     let to_id_h : (Droid.t, int) Hashtbl.t = Hashtbl.create 9 
     let from_id_h : (int, Droid.t) Hashtbl.t = Hashtbl.create 9 (*or use array*) 
     let size = ref 0 
     let from_id i = (Hashtbl.find from_id_h i) 
     let to_id (x :Droid.t) : int = 
       if  Hashtbl.mem to_id_h x 
       then Hashtbl.find to_id_h x 
       else (size := (!size)+1; 
         Hashtbl.add to_id_h x (!size); 
         Hashtbl.add from_id_h (!size) x; 
         !size) 
     (* Function wrappers *) 
     let empty = to_id Droid.empty 
     let beep = memo (fun x -> to_id (Droid.beep (from_id x))) 
     let boop = memo (fun x -> to_id (Droid.boop (from_id x))) 
     let len = memo (fun x ->  (Droid.len (from_id x))) 
end 

Answer 1

ボイラープレートはファンクタのために生成することは容易であるが、私は関数ラッパーのために行うことができる最高の例えば、OCamlのシグネチャを解析する外部のユーティリティを使用しています

#!/usr/bin/env perl 
@signature=`ocaml < droid.ml`; 
our $t; 
foreach(@signature) { 
    if (/type t = (\w+)/ ){ 
     $t=$1; 
    } elsif (/val (\w+) : (\w+)$/){ 
     print "let $1 = " . 
     (($2 eq $t) ? " to_id " : "") . 
     "(Droid.$1)\n"; 
    } elsif (/val (\w+) : (\w+) -> (\w+)$/){ 
     print "let $1 = " . 
     (($3 eq "unit") ? "(" : "memo (") . 
     " fun x -> " . 
     (($3 eq $t) ? "to_id (" : "(") . 
     (($2 eq $t) ? " from_id" : "") . 
     " (Droid.$1 x))\n"; 
    } 
} 

私はモジュールをmemoizeするPerlスクリプトにこれをブラッシュアップしている：https://github.com/gmatht/joshell/blob/master/scripts/memoize.pl