Warum wird '++' für Haskell List rekursiv implementiert und kostet O (n) Zeit?

Das ist ziemlich genau das, was die rekursive Lösung tut. Das Kopieren von a benötigt O (n) (wobei n die Länge von a ist. Die Länge von b hat keinen Einfluss auf die Komplexität).

Es gibt wirklich keinen "Trick", um eine Liste von n -Elementen in O (1) -Zeit zu kopieren.

Siehe kopieren (fork) Teil ist das Problem - die rekursive Lösung tut genau dies (und Sie müssen es wirklich tun, weil Sie alle Zeiger für die Elemente in der% anpassen müssen co_de% list.

Sagen wir beispielsweise a und a = [a1,a2,a3] ist eine Liste.

Sie müssen eine neue Kopie von b erstellen (nennen wir es a3 ), weil sie nun nicht mehr auf eine leere Liste, sondern auf den Anfang von a3' zeigen soll.

Dann müssen Sie auch das vorletzte Element b kopieren, da es auf a2 zeigen muss und schließlich - aus dem gleichen Grund - müssen Sie auch eine neue Kopie von a3' erstellen (pointing) zu a1 ).

Genau das ist die rekursive Definition - es ist kein Problem mit dem Algorithmus - es ist ein Problem mit der Datenstruktur (es ist einfach nicht gut mit Verkettung).

Wenn Sie keine Veränderlichkeit zulassen und die Struktur einer Liste wollen, können Sie wirklich nichts anderes tun.

Sie haben das in anderen Sprachen. Auch wenn sie unveränderliche Daten liefern - zum Beispiel in .net Strings sind unveränderlich - so gibt es fast das gleiche Problem mit String-Verkettung wie hier (wenn Sie viele Strings concate Ihr Programm wird schlecht durchführen). Es gibt Workarounds ( a2' ), die besser mit dem Speicherbedarf umgehen - aber das sind natürlich keine unveränderlichen Datenstrukturen mehr.

Es gibt keine Möglichkeit, diese Verkettung in konstanter Zeit durchzuführen, einfach weil die Unveränderlichkeit der Datenstruktur dies nicht erlaubt.

Sie könnten denken, dass Sie etwas Ähnliches wie den Operator "cons" ( : ) tun könnten, der ein zusätzliches Element x0 zum Front einer Liste oldList=[x1,x2,x3] hinzufügt (was zu newList=(x0:oldLIst) ), ohne die gesamte Liste durchlaufen zu müssen. Das liegt nur daran, dass Sie die vorhandene Liste oldList nicht berühren, sondern einfach darauf verweisen.

Aber in Ihrem Fall ( a ++ b ) sprechen wir davon, eine Referenz tief in der Datenstruktur zu aktualisieren. Sie möchten das [] in 1:(2:(3:[])) (die explizite Form von [1,2,3] ) durch das neue Tail b ersetzen. Zählen Sie einfach die Klammern und Sie werden sehen, dass wir tief in das Innere von [] gehen müssen. Das ist immer teuer, weil wir den gesamten äußeren Teil duplizieren müssen, um sicherzustellen, dass a unverändert bleibt. In der resultierenden Liste, wo würde der alte a zeigen, um die unmodifizierte Liste zu haben?

Das ist in der gleichen Datenstruktur unmöglich. Also brauchen wir einen zweiten:

Und das bedeutet, diese : Knoten zu duplizieren, was notwendigerweise die erwähnte lineare Zeit in der ersten Liste kostet. Das "copy (fork)", das Sie erwähnten, ist daher anders als das, was Sie sagten, nicht in O (1).

  

Machen Sie eine Kopie (fork) von einem, nennen wir es ein ', kann es einige Tricks geben, dies in O (1) Zeit

zu tun

Wenn Sie von einem "Trick" sprechen, um etwas in konstanter Zeit auszugeben, denken Sie wahrscheinlich daran, keine vollständige Kopie zu erstellen, sondern einen Verweis auf das ursprüngliche a zu erstellen, wobei die Änderungen als "Anmerkungen" (wie der Hinweis: "Modifikation am Tail: benutze b anstelle von [] ").

Aber das ist es, was Haskell dank seiner Faulheit sowieso tut! Es führt den O (n) -Algorithmus nicht sofort aus, sondern "merkt" sich einfach, dass Sie eine verkettete Liste haben wollten, bis Sie tatsächlich auf seine Elemente zugreifen. Aber das rettet Sie nicht davor, die Kosten am Ende zu bezahlen. Obwohl am Anfang der Verweis billig war (in O (1), wie Sie es wollten), fügt jede Instanz des ++ -Operators, wenn Sie auf die tatsächlichen Listenelemente zugreifen, einen kleinen Overhead hinzu (die Kosten für "interpretieren die Anmerkung ", die Sie zu Ihrer Referenz hinzugefügt haben" für den Zugriff auf jedes Element im ersten Teil der Verkettung, wobei die O (n) -Kosten schließlich addiert werden.