Wie man Listen in erlang kontiniert, ohne verschachtelte Listen zu erstellen?

Question

Ich versuche ein guter Erlanger zu sein und "++" zu vermeiden. Ich muss ein Tupel am Ende einer Liste hinzufügen, ohne eine verschachtelte Liste zu erstellen (und hoffentlich ohne es rückwärts zu bauen und umzukehren). Gegeben Tupel T und listet L0 und L1:

Wenn ich [T | L0] ich [tuple, list0].

Aber wenn ich verwenden [L0 | T], ich verschachtelte Liste [[list0] | Tupel]. Ähnlich gibt [L0 | L1][[list0] | list1] zurück.

Entfernen der äußeren Listenklammern L0 | [T] erzeugt einen Syntaxfehler.

Warum ist "|" nicht symmetrisch? Gibt es eine Möglichkeit, mit "|" das zu tun, was ich will?

Answer 1

| ist nicht "symmetrisch", da eine nicht leere Liste einen Kopf und einen Schwanz hat, wobei der Kopf ein einzelnes Element und der Schwanz eine andere Liste ist. In dem Ausdruck [foo | bar] ist foo der Kopf der Liste und bar ist der Schwanz. Wenn der Schwanz keine richtige Liste ist, wird das Ergebnis auch keine richtige Liste sein. Wenn der Kopf eine Liste ist, wird das Ergebnis einfach eine Liste mit dieser Liste als ihr erstes Element sein.

Es gibt keine Möglichkeit, am Ende einer verketteten Liste in weniger als O (n) Zeit anzuhängen. Aus diesem Grund wird die Verwendung von ++ in der Regel gemieden. Wenn am Ende der Liste eine spezielle Syntax zum Anhängen vorhanden wäre, würde es immer noch eine O (n) -Zeit benötigen und die Verwendung dieser Syntax würde Sie nicht mehr zu einem "guten Erlanger" machen als die Verwendung von ++.

Wenn Sie die O (n) -Kosten pro Einfügung vermeiden möchten, müssen Sie vorgeben und dann umkehren. Wenn Sie bereit sind, die Kosten zu bezahlen, können Sie auch ++ verwenden.

Ein wenig mehr Details auf, wie Listen arbeiten:

[ x | y ] ist etwas genannt cons Zelle. In C ausgedrückt ist es im Grunde eine Struktur mit zwei Mitgliedern. Eine richtige Liste ist entweder die leere Liste ([]) oder eine Cons-Zelle, deren zweites Mitglied eine richtige Liste ist (in diesem Fall wird das erste Mitglied sein Kopf genannt, und das zweite Mitglied wird sein Schwanz genannt).

Wenn Sie also [1, 2, 3] schreiben, werden die folgenden Cons-Zellen erstellt: [1 | [2 | [3 | []]]]. I.e. Die Liste wird als eine Cons-Zelle dargestellt, deren erstes Mitglied (ihr Kopf) 1 ist und das zweite Mitglied (der Schwanz) eine andere Cons-Zelle ist. Diese andere Cons-Zelle hat 2 als ihren Kopf und noch eine andere Cons-Zelle als ihren Schwanz. Diese Zelle hat 3 als ihren Kopf und die leere Liste als ihren Schwanz.

Eine solche Liste wird rekursiv durchlaufen, indem zuerst auf den Kopf der Liste und dann auf die Traversierungsfunktion am Ende der Liste zugegriffen wird.

Jetzt, wenn Sie einen Artikel dieser Liste voranzustellen möchten, ist dies sehr einfach: Sie erstellen einfach eine andere Cons-Zelle, deren Kopf der neue Artikel ist und dessen Schwanz die alte Liste ist.

Das Anhängen eines Objekts ist jedoch viel teurer, da das Erstellen einer einzelnen Zelle nicht ausreicht.Sie müssen eine Liste erstellen, die dieselbe wie die alte ist, außer dass der Schwanz der letzten Cons-Zelle eine neue Cons-Zelle sein muss, deren Kopf das neue Element ist und deren Schwanz die leere Liste ist. Sie können also nicht an eine Liste anhängen, ohne die ganze Liste durchzugehen, also O (n).