Dieses Paket enthält einige Funktionen, um rekursive Funktionen für eine bessere Leistung in rekursive Funktionen der dynamischen Programmierung umzuwandeln:
Leider haben sie nur ein Beispiel für die einfachste Art von Funktion, und es gibt keine Beispiele dafür, wie man eine Funktion von 2 Variablen verwendet. Wo finde ich ein Beispiel, wie man beispielsweise [Int] -> Int -> Int function in eine dynamische Programmierfunktion umwandeln kann? Die Dokumentation sagt memo2 nimmt zwei Memo s als erste Argumente, aber ich bin mir nicht sicher, was das bedeutet.
Lösung:
Wie Hammar beschrieben hat, anstatt eine Funktion wie folgt zu definieren:
%Vor%Memo2 verwenden:
%Vor% Die Bibliothek definiert den Typ Memo a , der ein "Memoizer" für Funktionen ist, die Argumente vom Typ a verwenden. Der Schlüssel zum Verständnis der Verwendung dieser Bibliothek besteht darin, zu verstehen, wie diese Memoizer verwendet und zusammengestellt werden.
Im einfachen Fall haben Sie eine einzelne Argumentfunktion und einen einfachen Memoizer, zum Beispiel eine Fibonacci-Funktion und einen Memoizer für Integral arguments. In diesem Fall erhalten wir die Memo-Funktion, indem wir das Memo auf die zu memoende Funktion anwenden:
Einige Memoizer verwenden Argumente, um ihr Verhalten anzupassen, z. B. arrayRange . Im folgenden Beispiel wird fib n nur protokolliert, wenn n zwischen 1 und 100 liegt.
Die Bibliothek bietet auch Kombinatoren, um komplexere Memoizer aus einfachen zu erstellen. Beispiel: list , wodurch ein Memo für a in einen Memoizer für [a] verwandelt wird.
Um schließlich Funktionen mehrerer Argumente zu memoisieren, gibt es die Funktionen memo2 und memo3 , die für jedes Argument und eine Funktion einen Memoizer verwenden und eine Memo-Funktion zurückgeben.
Um Ihre Zwei-Argumente-Funktion zu beschreiben, müssen wir memo2 verwenden. Wir können den integral memoizer für das Int Argument verwenden, und für das [Int] Argument können wir list integral verwenden. Wenn wir das zusammensetzen, bekommen wir so etwas:
Sie können jedoch auch spezifischere Memoizer verwenden, wenn Sie wissen, dass die Nummern in einem bestimmten Bereich liegen. Wenn beispielsweise die Zahlen in der Liste zwischen 1 und 10 und das zweite Argument zwischen 15 und 20 liegt:
%Vor%Ob dies sinnvoll ist oder nicht, hängt von Ihrer Anwendung ab.
Pro Typen und Dokumentation glaube ich
%Vor%sollte per
gespeichert werden %Vor%(Disclaimer: Ich habe keine Daten-Memokombinatoren verwendet).
Tags und Links haskell recursion dynamic-programming