Hofstadter weibliche und männliche Sequenzen in SML

Question

Dies ist mein erstes SML-Programm. Ich versuche, eine Funktion zu schreiben, die die erste Nummer in Listenform an die n-te Nummer von Hofstadters weiblicher oder männlicher Sequenz zurückgibt. Was ich bisher habe, ist:

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); 

Sie können über die Reihenfolge lernen hier: https://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences

Der Fehler, ich bin immer ist:

[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 

Wie kann ich das korrigieren?

Answer 1

I beendet diesen Ansatz bis unter:

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); 

Es ist ziemlich langsam. Wenn jemand eine schnellere Version hat, würde ich es gerne sehen.

Answer 2

Obwohl sie sich bereits festgelegt haben, gab es zwei Probleme mit Ihrem ursprünglichen Ansatz:

1. Funktion Anwendung Linksassoziativität in SML so m f (n - 1) als (m f) (n - 1) interpretiert wurde, nicht die gewünschte m (f (n - 1)). Sie können dies beheben, indem Sie explizit die Klammer m (f (n - 1)) angeben.

2. zu können f von mundm von f rufen, müssen Sie fun statt val auf der ersten Deklaration das Schlüsselwort verwenden, und das Schlüsselwort and statt fun (die Funktion rekursiv zu machen) oder val auf der zweiten Deklaration (um die Funktion gegenseitig rekursiv mit der ersten Funktion zu machen). Dies würde so aussehen

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

, um es schneller zu machen, können Sie memoize! Der Trick besteht darin, f und m Argumente als Memo-Versionen von sich selbst zu nehmen.

(* 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 

I umbenannt f und m-female und male. Die notierten fMemo und gMemo sind durch female und male von memoizeMutual gefädelt. Interessanterweise, wenn wir male' aufrufen, dann sind Ergebnisse für sowohlmale' als auch female' Memoized.

Um zu bestätigen, dass es in der Tat schneller ist, versuchen Sie hofstadter 10000 auszuwerten. Es ist viel schneller als die Ewigkeit, die deine Version nehmen würde. Als letzte Anmerkung sind die einzigen rekursiven Funktionen fMemo und gMemo. Jede andere Funktion, die ich geschrieben habe, könnte als eine anonyme Funktion geschrieben werden (val memoizeMutual = fn ..., val female = fn ..., usw.), aber ich entschied mich, dies nicht zu tun, weil die Syntax zum Schreiben rekursiver Funktionen in SML viel kompakter ist.

Um dies zu verallgemeinern, könnten Sie die Array-Version von Memoizing durch eine Hash-Tabelle ersetzen. Dann müssten wir nicht vorab die Größe der Memoisierung angeben.