In einer objektorientierten Sprache, wenn ich die Ergebnisse einer Funktion für eine bekannte Lebensdauer cache / memoisieren möchte, folge ich im Allgemeinen diesem Muster:
Dieser objektbasierte Ansatz ist dem hier beschriebenen funktionsbasierten Memoisierungsmuster sehr ähnlich: Ссылка
Der Hauptvorteil dieses Ansatzes besteht darin, dass die Ergebnisse nur für die Lebensdauer des Cache-Objekts beibehalten werden. Ein häufiger Anwendungsfall ist die Verarbeitung einer Liste von Arbeitselementen. Für jedes Arbeitselement erstellt man das Cache-Objekt für dieses Element, verarbeitet das Arbeitselement mit diesem Cache-Objekt und verwirft dann das Arbeitselement und das Cache-Objekt, bevor mit dem nächsten Arbeitselement fortgefahren wird.
Was sind gute Möglichkeiten, kurzlebige Memoization in Haskell zu implementieren? Und hängt die Antwort davon ab, ob die zu cachenden Funktionen rein sind oder IO beinhalten?
Nur um es noch einmal zu wiederholen - es wäre schön, Lösungen für Funktionen zu sehen, die IO betreffen.
Lasst uns Luke Palmers Memo-Bibliothek verwenden: Daten. MemoCombinators
%Vor%Ich werde die Dinge etwas anders definieren als seine Bibliothek, aber es ist im Grunde dasselbe (und außerdem kompatibel). Ein "memoizable" Ding nimmt sich selbst als Eingabe und produziert das "echte" Ding.
%Vor%Ein "Memoizer" übernimmt eine Funktion und erzeugt die Memo-Version davon.
%Vor% Lassen Sie uns eine kleine Funktion schreiben, um diese beiden Dinge zusammenzufügen. Bei einer Memoizable -Funktion und einer Memoizer wollen wir die resultierende Memo-Funktion.
Dies ist ein wenig Magie mit dem Fixpunkt-Kombinator ( fix ). Vergiss das nicht; Sie können es googeln, wenn Sie interessiert sind.
Lassen Sie uns eine Memoizable Version des klassischen fib Beispiels schreiben:
Die Verwendung einer self Konvention macht den Code einfach. Denken Sie daran, self ist die erwartete Version dieser Funktion, daher sollten rekursive Aufrufe auf self stehen. Jetzt feuern ghci.
Nun, das Coole an runMemo ist, dass Sie mehr als eine frisch gemouncte Version derselben Funktion erstellen können, und sie nicht Speicherbänke teilen. Das bedeutet, dass ich eine Funktion schreiben kann, die fib' lokal erstellt und verwendet, aber sobald fib' außerhalb des Gültigkeitsbereichs liegt (oder früher, abhängig von der Intelligenz des Compilers), kann Garbage Collected sein Es muss nicht auf oberster Ebene gespeichert werden . Dies kann oder kann nicht gut mit Memo-Techniken funktionieren, die auf unsafePerformIO angewiesen sind. Data.MemoCombinators verwendet eine reine, faule Trie, die perfekt zu runMemo passt. Anstatt ein Objekt zu erstellen, das im Wesentlichen zu einem Memo-Manager wird, können Sie einfach Memo-Funktionen auf Anforderung erstellen. Wenn Ihre Funktion rekursiv ist, muss sie als Memoizable geschrieben werden. Die gute Nachricht ist, dass Sie beliebig Memoizer anschließen können. Sie könnten sogar verwenden:
Die Lazy-Haskell-Programmierung ist gewissermaßen das Paradigma der Memoisierung. Was auch immer du in einer imperativen Sprache machst, ist in Haskell möglich, entweder mit IO-Monade, der ST-Monade, Monaden-Transformatoren, Pfeilen oder du nennst was.
Das einzige Problem ist, dass diese Abstraktionsgeräte viel komplizierter sind als das Imperativ, das Sie erwähnten, und sie brauchen eine ziemlich tiefe Umverdrahtung.
Ich glaube, die obigen Antworten sind komplexer als notwendig, obwohl sie tragbarer sind als das, was ich beschreiben werde.
Wie ich es verstehe, gibt es in ghc eine Regel, nach der jeder Wert genau einmal berechnet wird, wenn ein Lambda-Ausdruck eingegeben wird. So können Sie genau Ihr kurzlebiges Memo-Objekt wie folgt erstellen:
Was macht das? Es gruppiert alle Elemente in Data.Vector t , die übergeben wurden, als zweites Argument vec gemäß der Ganzzahl, die durch das erste Argument idx berechnet wurde, wobei ihre Gruppierung als Data.Vector [t] beibehalten wird. Sie gibt eine Funktion vom Typ Int -> [t] zurück, die diese Gruppierung anhand dieses vorberechneten Indexwerts nachschlägt.
Unser Compiler ghc hat versprochen, dass tbl nur einmal angegeben wird, wenn wir indexerVector aufrufen. Wir können daher den von \e -> tbl ! e zurückgegebenen Lambda-Ausdruck indexVector einem anderen Wert zuweisen, den wir wiederholt verwenden können, ohne befürchten zu müssen, dass tbl jemals neu berechnet wird. Sie können dies überprüfen, indem Sie trace in tbl einfügen.
Kurz gesagt, Ihr Caching-Objekt ist genau dieser Lambda-Ausdruck.
Ich habe festgestellt, dass fast alles, was Sie mit einem Kurzzeitobjekt erreichen können, besser erreicht werden kann, indem Sie einen Lambda-Ausdruck wie diesen zurückgeben.
Sie können das gleiche Muster auch in Haskell verwenden. Die Lazy-Auswertung prüft, ob der Wert bereits ausgewertet wurde. Es wurde bereits mehrfach erwähnt, aber Codebeispiel könnte nützlich sein. Im Beispiel unten wird memoedValue nur einmal berechnet, wenn es angefordert wird.
Noch besser: Sie können Werte memoisieren, die von anderen memoisierten Werten abhängen. Sie sollten Abhängigkeiten vermeiden. Sie können zur Nichtbeendigung führen.
%Vor%Tags und Links haskell memoization