SMLのHofstadter女性と男性シーケンス

Question

これは私の最初のSMLプログラムです。私はリスト形式のHofstadterの女性または男性シーケンスのn番目の番号に最初の番号を返す関数を記述しようとしています。私はこれまで持っていることは次のとおりです。

val m = fn (n) => if n = 0 then 1 :: [] else m f (n - 1); 
val f = fn (n) => if n = 0 then 0 :: [] else f m (n - 1); 

あなたがここにシーケンスを学ぶことができます。 https://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences

私は取得していますエラーは次のとおりです。

[opening sequence.sml] 
sequence.sml:1.49 Error: unbound variable or constructor: f 
sequence.sml:1.47-1.58 Error: operator is not a function [tycon mismatch] 
    operator: int list 
    in expression: 
    (m <errorvar>) (n - 1) 
val it =() : unit 

は、どのように私はこれを修正することができますか？

Answer 1

私はこのアプローチを取ってしまった：

fun 
    m (n) = if n = 0 then 0 else n - (f (m (n - 1))) 
and 
    f (n) = if n = 0 then 1 else n - (m (f (n - 1))); 
val seq = fn n => List.tabulate((n), f); 

それはかなり遅いです。誰かがより速いバージョンを持っているなら、私はそれを見るのが大好きです。

Answer 2

あなたは既にそれらを固定しているが、あなたの独創的なアプローチには二つの問題がありました：

1. 機能アプリケーションが左結合さSMLでそうm f (n - 1)が(m f) (n - 1)、ない希望m (f (n - 1))と解釈されていましたが。 m (f (n - 1))を明示的に指定することでこれを修正できます。

2. するfからmとmからfを呼び出すことができるようにするには、（関数、再帰を作るために）最初の宣言にvalの代わりにキーワードfunを使用する必要がある、とキーワードandの代わりに、funかvalを2番目の宣言に追加します（関数を最初の関数で相互に再帰的にする）。これは、それがより速く行うために

   fun f n = ... (* I can call f or m from here! *) 
   and m n = ... (* I can call f or m from here! *) 
   

ようになり、あなたはmemoizeことができます！そのトリックは、fとmをメモとして扱うことです。

(* Convenience function: Update arr[i] to x, and return x. *) 
fun updateAndReturn arr i x = (Array.update (arr, i, SOME x); x) 

(* 
* Look up result of f i in table; if it's not found, calculate f i and 
* store in the table. The token is used so that deeper recursive calls 
* to f can also try to store in the table. 
*) 
fun memo table f token i = 
    case Array.sub (table, i) 
    of NONE => updateAndReturn table i (f token i) 
    | SOME x => x 

(* 
* Given f, g, and n : int, returns a tuple (f', g') where f' and g' are memoized 
* versions of f and g, respectively. f' and g' are defined only on the domain 
* [0, n). 
*) 
fun memoizeMutual (f, g) n = 
    let 
    val fTable = Array.array (n, NONE) 
    val gTable = Array.array (n, NONE) 
    fun fMemo i = memo fTable f (fMemo, gMemo) i 
    and gMemo i = memo gTable g (gMemo, fMemo) i 
    in 
    (fMemo, gMemo) 
    end 

fun female _ 0 = 1 
    | female (f, m) n = n - m (f (n - 1)) 

fun male _ 0 = 0 
    | male (m, f) n = n - f (m (n - 1)) 

fun hofstadter upTo = 
    let 
    val (male', female') = memoizeMutual (male, female) upTo 
    in 
    (List.tabulate (upTo, male'), List.tabulate (upTo, female')) 
    end 

私はfemaleとmaleへfとmの名前を変更しました。メモのfMemoとgMemoは、femaleとmaleによってmemoizeMutualにスレッドされています。面白いことに、male'と呼ぶと、の結果はmale'とfemale'の両方が記録されます。

それが実際に速いことを確認するには、hofstadter 10000を評価してみてください。それはあなたのバージョンがとる永遠にずっと速いです。

最後の注釈として、唯一の再帰関数はfMemoとgMemoです。私が書いた他の関数はすべて無名関数（val memoizeMutual = fn ...、val female = fn ...など）として記述することができましたが、再帰関数を書くための構文はSMLで非常にコンパクトであるため、そうしないことにしました。

一般化するには、メモバージョンの配列バージョンをハッシュテーブルのようなものに置き換えることができます。その後、私たちはメモのサイズを指定する必要はありません。