Wie funktioniert Daten.Memokombinatoren funktionieren?

Question

Ich habe nach der Quelle gesucht Daten.Memokombinatoren aber ich kann nicht wirklich sehen, wo das Herz davon ist.

Bitte erklären Sie mir, was die Logik hinter all diesen Kombinatoren ist und Mechaniker wie sie tatsächlich funktionieren, um Ihr Programm in der realen Programmierung zu beschleunigen.

Ich suche nach Einzelheiten für dieser implementierung und optional Vergleich / Kontrast mit anderen Haskell-Ansätzen zur Memoisierung.Ich verstehe, was Memoisierung ist und bin nicht suchen Sie nach einer Beschreibung, wie es im Allgemeinen funktioniert.

Answer 1

Diese Bibliothek ist eine einfache Kombinatorisierung der bekannten Technik der Memoisierung.Beginnen wir mit dem kanonischen Beispiel:

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

Ich interpretiere das, was Sie gesagt haben, so, dass Sie wissen, wie und warum das funktioniert.Also werde ich mich auf die Kombinatorik konzentrieren.

Wir versuchen im Wesentlichen, die Idee von zu erfassen und zu verallgemeinern (map f [0..] !!).Der Typ dieser Funktion ist (Int -> r) -> (Int -> r), was Sinn macht:es nimmt eine Funktion von Int -> r und gibt eine gespeicherte Version derselben Funktion zurück.Jede Funktion, die semantisch die Identität ist und diesen Typ hat, wird als "Memoizer für" bezeichnet Int" (auch id, die sich nicht merken).Wir verallgemeinern auf diese Abstraktion:

type Memo a = forall r. (a -> r) -> (a -> r)

Also ein Memo a, ein Memoizer für a, nimmt eine Funktion von a zu irgendetwas und gibt eine semantisch identische Funktion zurück, die gespeichert wurde (oder nicht).

Die Idee der verschiedenen Memoizer besteht darin, einen Weg zu finden, die Domäne mit einer Datenstruktur aufzuzählen, die Funktion über sie abzubilden und dann die Datenstruktur zu indizieren. bool ist ein gutes Beispiel:

bool :: Memo Bool
bool f = table (f True, f False)
    where
    table (t,f) True = t
    table (t,f) False = f

Funktionen von Bool sind äquivalent zu Paaren, außer dass ein Paar jede Komponente nur einmal auswertet (wie dies für jeden Wert der Fall ist, der außerhalb eines Lambdas auftritt).Also mappen wir einfach auf ein Paar und zurück.Der wesentliche Punkt ist, dass wir die Bewertung der Funktion über das Lambda für das Argument heben (hier das letzte Argument von table) durch Aufzählung der Domäne.

Memoisieren Maybe a ist eine ähnliche Geschichte, außer dass wir jetzt wissen müssen, wie man auswendig lernt a für die Just Fall.Also der Memoizer für Maybe nimmt einen Memoizer für a als Argument:

maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
    where
    table (n,j) Nothing = n
    table (n,j) (Just x) = j x

Der Rest der Bibliothek besteht nur aus Variationen dieses Themas.

Die Art und Weise, wie integrale Typen gespeichert werden, verwendet eine geeignetere Struktur als [0..].Es ist ein bisschen kompliziert, aber im Grunde erstellt es nur einen unendlichen Baum (der die Zahlen in Binärform darstellt, um die Struktur aufzuklären):

1
  10
    100
      1000
      1001
    101
      1010
      1011
  11
    110
      1100
      1101
    111
      1110
      1111

Das Nachschlagen einer Zahl im Baum hat also eine Laufzeit, die proportional zur Anzahl der Bits in ihrer Darstellung ist.

Wie sclv hervorhebt, verwendet die MemoTrie-Bibliothek von Conal dieselbe zugrunde liegende Technik, verwendet jedoch eine Typklassenpräsentation anstelle einer Kombinatorpräsentation.Wir haben unsere Bibliotheken gleichzeitig unabhängig voneinander veröffentlicht (tatsächlich innerhalb weniger Stunden!).Conals ist in einfachen Fällen einfacher zu bedienen (es gibt nur eine Funktion, memo, und es wird die zu verwendende Memostruktur basierend auf dem Typ bestimmen), während meine flexibler ist, da Sie solche Dinge tun können:

boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
   where
   memof = integral f

Die nur Werte speichert, die kleiner als eine gegebene Grenze sind und für die Implementierung eines der Euler-Probleme des Projekts benötigt werden.

Es gibt andere Ansätze, zum Beispiel das Offenlegen einer offenen Fixpunktfunktion über eine Monade:

memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)

Was noch mehr Flexibilität ermöglicht, zB.löschen von Caches, LRU usw.Aber es ist eine Nervensäge zu benutzen, und es setzt auch strenge Einschränkungen für die zu speichernde Funktion (z.keine unendliche linke Rekursion).Ich glaube nicht, dass es Bibliotheken gibt, die diese Technik implementieren.

Hat das beantwortet, worauf Sie neugierig waren?Wenn nicht, machen Sie vielleicht die Punkte deutlich, über die Sie verwirrt sind?

Answer 2

Das Herz ist der bits Funktion:

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

Es ist die einzige Funktion (außer der trivialen unit :: Memo ()), die Ihnen eine geben kann Memo a Wert.Es verwendet die gleiche Idee wie in diesem Seite über Haskell Memoization.Abschnitt 2 zeigt die einfachste Memoisierungsstrategie unter Verwendung einer Liste und Abschnitt 3 macht dasselbe unter Verwendung eines binären Naturbaums ähnlich dem IntTree wird in Memokombinatoren verwendet.

Die Grundidee ist, eine Konstruktion wie zu verwenden (map fib [0 ..] !!) oder im Fall von Memokombinatoren - IntTrie.apply (fmap f IntTrie.identity).Was hier zu beachten ist, ist die Korrespondenz zwischen IntTie.apply und !! und auch zwischen IntTrie.identity und [0..].

Der nächste Schritt besteht darin, Funktionen mit anderen Argumenttypen zu speichern.Dies geschieht mit dem wrap funktion, die einen Isomorphismus zwischen Typen verwendet a und b um eine zu konstruieren Memo b von einem Memo a.Beispielsweise:

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

Der Rest des Quellcodes befasst sich mit Typen wie List, Maybe, Either und dem Speichern mehrerer Argumente.

Answer 3

Ein Teil der Arbeit wird von IntTrie erledigt: http://hackage.haskell.org/package/data-inttrie-0.0.4

Lukes Bibliothek ist eine Variation von Conals Memobibliothek, die er hier beschrieben hat: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

Einige weitere Erweiterungen - der allgemeine Begriff hinter der funktionalen Memoisierung besteht darin, eine Funktion von zu übernehmen a -> b und ordnen Sie es einer Datenstruktur zu, die indiziert ist durch alles möglich werte von a und enthält Werte von b.Eine solche Datenstruktur sollte auf zwei Arten faul sein - erstens sollte sie in den Werten, die sie enthält, faul sein.Zweitens sollte es träge selbst produziert werden.Ersteres ist standardmäßig in einer nicht strengen Sprache.Letzteres wird durch Verwendung verallgemeinerter Versuche erreicht.

Die verschiedenen Ansätze von Memokombinatoren, Memotrie usw. sind alles nur Möglichkeiten, Kompositionen von Versuchsteilen über einzelne Arten von Datenstrukturen zu erstellen, um die einfache Konstruktion von Versuchen für immer komplexere Strukturen zu ermöglichen.

Answer 4

@luqui Eine Sache, die mir nicht klar ist: Hat dies das gleiche operative Verhalten wie folgt: generasacodicetagpre.

Das oben genannte sollte FIB auf der obersten Ebene moltzt, und wenn Sie zwei Funktionen definieren: generasacodicetagpre.

Wenn wir dann f 5 berechnen, erhalten wir, dass fib 5 beim Berechnen fib 6 nicht neu berechnet wird.Es ist mir nicht klar, ob die Memanisierungskombinatoren das gleiche Verhalten haben (d. H. Nidrige Niveau, anstatt nur die Recomputation "innen" der FIB-Berechnung zu verbieten), und wenn ja, warum genau?