Memoize eine Funktion des Typs() -> '

Question

This memoize function schlägt auf alle Funktionen des Typs () -> 'a zur Laufzeit mit einer Null-Argument-Ausnahme.

let memoize f = 
    let cache = System.Collections.Generic.Dictionary() 
    fun x -> 
     if cache.ContainsKey(x) then 
      cache.[x] 
     else 
      let res = f x 
      cache.[x] <- res 
      res 

Gibt es eine Möglichkeit, eine memoize Funktion zu schreiben, die auch für eine () -> 'a funktioniert?

(Meine einzige Alternative für die jetzt einen Lazy Typen verwendet. x.Force() rief den Wert zu erhalten.)

Answer 1

Der Grund, warum die Funktion fehlschlägt, ist, dass F # Einheit darstellt () mit null vom Typ unit. Das Wörterbuch erlaubt keine null Werte als Schlüssel und so schlägt es fehl.

In Ihrem speziellen Fall gibt es nicht viel Sinn, in memoizing Funktion vom Typ unit -> 'a (weil es besser ist lazy dafür zu benutzen), aber es gibt andere Fälle, in denen dies ein Problem sein würde - None zum Beispiel ist auch vertreten auch durch null so versagt diese:

let f : int option -> int = memoize (fun a -> defaultArg a 42) 
f None 

Der einfache Weg, um dies zu beheben ist, den Schlüssel in einer anderen Datentyp wickeln, um sicherzustellen, dass es nie null:

type Key<'K> = K of 'K 

Dann können Sie wickeln einfach die Taste mit dem K Konstruktor und alles gut funktioniert:

let memoize f = 
    let cache = System.Collections.Generic.Dictionary() 
    fun x -> 
     if cache.ContainsKey(K x) then 
      cache.[K x] 
     else 
      let res = f x 
      cache.[K x] <- res 
      res 

Answer 2

memoization eine reine Funktion (nicht nur vom Typ unit -> 'a, aber andere auch) als Suchschlüssel unmöglich, weil Funktionen im Allgemeinen keinen Gleichheitsvergleich für die reason haben.

Es könnte scheinen, dass für diese spezifische Art von Funktion unit -> 'a es möglich wäre, mit einem benutzerdefinierten Gleichheitsvergleich zu kommen. Der einzige Ansatz zum Implementieren eines solchen Vergleichs über Extreme hinaus (Reflektion, IL, etc.) wäre , wobei die Lookup-Funktion als f1 = f2 iff f1() = f2() aufgerufen wird, was offensichtlich jegliche Leistungsverbesserung, die von Memoisierung erwartet wird, aufhebt.

So, vielleicht, wie bereits erwähnt, sollten für diesen Fall Optimierungen um lazy Muster aufgebaut werden, aber nicht memoization eins.

UPDATE: In der Tat, nach dem zweiten Blick auf die Frage alle oben über Funktionen fehlenden Gleichheitsvergleich ist richtig, aber nicht anwendbar, weil memoization innerhalb jeder einzelnen cache der Funktion von der Schließung geschieht. Auf der anderen Seite ist für diese spezielle Art von Funktionen mit der Signatur unit->'a, d. H. Höchstens ein einzelner Wert des Arguments, die Verwendung von Dictionary mit dem meisten Eintrag ein Overkill. Die folgende ähnlich Stateful, aber einfachere Implementierung mit nur einem Wert memoized tun:

let memoize2 f = 
    let notFilled = ref true 
    let cache = ref Unchecked.defaultof<'a> 
    fun() -> 
     if !notFilled then 
      cache := f() 
      notFilled := false 
     !cache 

verwendet als let foo = memoize2(fun() -> ...heavy on time and/or space calculation...) mit dem ersten Gebrauch foo() Durchführung und das Ergebnis der Berechnung zu speichern und alle aufeinanderfolgenden foo() nur den gespeicherten Wert wiederzuverwenden.

Answer 3

Ich fand nur, dass die letzte memoize Funktion on the same website mit Map statt Dictionary Werke für 'a Option -> 'b und () -> 'a zu:

let memoize1 f = 
    let cache = ref Map.empty 
    fun x -> 
     match (!cache).TryFind(x) with 
     | Some res -> res 
     | None -> 
      let res = f x 
      cache := (!cache).Add(x,res) 
      res 

Answer 4

Lösung mit wandelbaren Wörterbuch und einzigen Wörterbuch-Lookup Aufruf: let memoize1 f = // printfn "Dictionary" let cache = System.Collections.Generic.Dictionary() fun x -> let result, value = cache.TryGetValue(x) match result with | true -> value | false -> // printfn "f x" let res = f x cache.Add(x, res) res