Hofstadter SML中的女性和男性序列

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. 爲了能夠從m和m從f叫f，您需要在第一個聲明中使用關鍵字fun，而不是val（使函數的遞歸），以及關鍵字and，而不是fun或val對第二個聲明（使函數與第一個函數相互遞歸）。這看起來像

   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 

我改名爲f和m到female和male。記憶的fMemo和gMemo通過female和male通過memoizeMutual進行線程化。有趣的是，如果我們撥打male'，male'和female'的結果被記錄下來。

要確認它確實速度更快，請嘗試評估hofstadter 10000。它比你的版本要快得多。

作爲最後一點，唯一的遞歸函數是fMemo和gMemo。我寫的每一個函數都可以寫成一個匿名函數（val memoizeMutual = fn ...，val female = fn ...等），但我選擇不這樣做，因爲在SML中寫遞歸函數的語法要緊湊得多。

爲了概括這一點，你可以用類似哈希表的東西來替換memoizing的數組版本。然後，我們不必先指定備忘錄的大小。