Differenzlisten in der funktionalen Programmierung

13

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?

Rob Simmons
quelle
1
Anfangs war ich verwirrt von "funktionalen Programmiersprachen (im Gegensatz zu funktionalen Programmiersprachen)", aber wollten Sie "(im Gegensatz zu logischen Programmiersprachen)" schreiben?
Tsuyoshi Ito
Oh, hoppla, das habe ich gemeint, es ist jetzt behoben.
Rob Simmons
Die zweite Frage zu Stack Overflow scheint mir angemessener zu sein, aber jetzt, da Sie sie hier gestellt haben, ist es möglicherweise besser, abzuwarten, ob hier jemand antworten kann. Persönlich kann ich keinen Grund finden, die behaupteten Grenzen des Lesens des Quellcodes anzuzweifeln, aber ich bin Ihrer Argumentation nicht gefolgt, um sie anzuzweifeln, und möglicherweise fehlt mir auch etwas.
Tsuyoshi Ito

Antworten:

8

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?

Θ(m)m

Ö(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)

Θ(n)headtail[a] -> [a]toList

Apfel
quelle
Was Sie also von Faulheit bekommen, ist, dass zweimal nach dem Ende einer Liste zu fragen , die teure Operation nicht zweimal erledigt, was schön ist.
Rob Simmons
@Rob, ich verstehe nicht, was du damit meinst.
Jbapple
Ich denke, der Punkt, den ich (schlecht) machen wollte, wird durch dieses Beispiel veranschaulicht: Ich habe eine außerordentlich lange Differenzliste "xs", die ich durch wiederholtes "Schnüffeln" von Dingen auf der ursprünglichen Liste erstellt habe. Wenn ich zum ersten Mal "head xs" aufrufe, wird es voraussichtlich 0 (n) Mal dauern, bis die Berechnung zurückgestellt ist. Da diese Berechnung jedoch gespeichert werden soll, sollte der zweite Aufruf von "head xs" (für dasselbe "xs") O (1) -Zeit benötigen .
Rob Simmons
1
Nun, ich stimme dem zu, aber die Faulheit, auf die ich in meiner Antwort verwiesen habe, handelte von fromList, die in snoc oder head nicht verwendet wird. So pedantisch es auch ist, ich war verwirrt von dem "Was" in deiner Aussage "Was du von Faulheit bekommst". Ich würde sagen, dein Beispiel und meins sind zwei Dinge, die du von Faulheit bekommst.
Jbapple
Ok - und diese Klarstellung hilft mir auch, Ihren früheren Punkt besser zu verstehen.
Rob Simmons
11

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

Ö(n)

Neel Krishnaswami
quelle