Differenzlisten in der funktionalen Programmierung

Die Frage Was ist neu in rein funktionalen Datenstrukturen seit Okasaki? und die epische Antwort von jbapple, die anhand von Differenzlisten in der funktionalen Programmierung (im Gegensatz zur logischen Programmierung) erwähnt wurde, woran ich mich in letzter Zeit interessiert habe. Dies führte mich dazu, die Implementierung der Differenzliste für Haskell zu finden. Ich habe zwei Fragen (verzeih mir / korrigiere mich, wenn ich ihnen zwei verschiedene Fragen auf dem StackExchange stellen soll).

Die einfache Frage ist, ob jemand Kenntnis von der wissenschaftlichen Berücksichtigung von Differenzlisten bei der funktionalen Programmierung und / oder bei Implementierungen hat, die nicht in der Haskell-Bibliothek enthalten sind. Die Antwort von jbapple nannte kein Zitat für Differenzlisten (Differenzlisten in der Logikprogrammierung existieren in der Überlieferung und in einigen Quellen, die ich in Around Here Somewhere (TM) habe). Bevor ich die Haskell-Implementierung fand, war mir nicht bewusst, dass die Idee von der Logik zur funktionalen Programmierung übergegangen war. Zugegeben, die Haskell-Differenzlisten sind eine natürliche Anwendung von Funktionen höherer Ordnung und funktionieren ganz anders als die in der Logikprogrammierung, aber die Oberfläche ist sicherlich ähnlich.

Das interessantere (und weitaus unübersichtlichere), worüber ich mich erkundigen wollte, ist, ob die behauptete asymptotische Obergrenze für die oben genannte Haskell-Differenzlistenbibliothek richtig / plausibel erscheint. Meine Verwirrung mag darin liegen, dass mir etwas über das logische Argumentieren von Komplexität mit Faulheit fehlt, aber die beanspruchten Grenzen sind für mich nur dann sinnvoll, wenn die Substitution über eine große Datenstruktur (oder Abschlussformation oder variable Suche oder etwas ) immer konstante Zeit benötigt. Oder liegt der "Haken" einfach daran, dass die Laufzeit für "Kopf" und "Schwanz" nicht beschränkt ist, gerade weil diese Operationen möglicherweise einen beliebigen Stapel verzögerter Berechnungen / Ersetzungen durchlaufen müssen?

Oder liegt der "Haken" einfach daran, dass die Laufzeit für "Kopf" und "Schwanz" nicht beschränkt ist, gerade weil diese Operationen möglicherweise einen beliebigen Stapel verzögerter Berechnungen / Ersetzungen durchlaufen müssen?

$\Theta(m)$$m$

$O(1)$ fromList

{-# LANGUAGE NoMonomorphismRestriction #-}

data DL a = Id
          | Cons a
          | Compose (DL a) (DL a)

fromList [] = Id
fromList (x:xs) = Compose (Cons x) (fromList xs)

toList x = help x []
    where help Id r = r
          help (Cons a) r = a:r
          help (Compose f g) r = help f $ help g r

empty = Id

singleton = Cons

cons x = append (singleton x)

append = Compose

snoc xs x = append xs (singleton x)

$\Theta(n)$headtail[a] -> [a]toList

Ja, die Grenzen hängen von der Annahme ab, dass die Funktionszusammensetzung eine konstante Zeit benötigt. Grundsätzlich, wenn Sie eine Beitrittsliste haben:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

$O(n)$