Gibt es etwas wie (xs: x)?

Ich bin auch neu bei Haskell, daher ist meine Antwort nicht maßgeblich. Jedenfalls würde ich es mit last und init machen:

oder

Die kurze Antwort lautet: Das ist beim Mustervergleich nicht möglich, Sie müssen eine Funktion verwenden.

Die lange Antwort ist: Es ist nicht in Standard-Haskell, aber es ist, wenn Sie eine Erweiterung namens View Patterns verwenden möchten, und auch wenn Sie kein Problem mit Ihrer Mustererkennung haben, die eventuell länger als konstante Zeit dauert.

Der Grund dafür ist, dass die Mustererkennung darauf basiert, wie die Struktur aufgebaut ist. Eine Liste ist ein abstrakter Typ mit folgender Struktur:

Wenn Sie einen Typ wie diesen deklarieren, generieren Sie drei Objekte: einen Typkonstruktor List und zwei Datenkonstruktoren: Empty und Cons . Der Typkonstruktor übernimmt Typen und wandelt sie in andere Typen um, d. H.% Co_de% übernimmt den Typ List und erstellt einen anderen Typ a . Der Datenkonstruktor funktioniert wie eine Funktion, die etwas vom Typ List a zurückgibt. In diesem Fall haben Sie:

repräsentiert eine leere Liste und

nimmt einen Wert vom Typ List a und eine Liste an und hängt den Wert an den Anfang der Liste an und gibt eine andere Liste zurück. So können Sie Ihre Listen so aufbauen:

Dies ist mehr oder weniger wie Listen funktionieren, aber anstelle von a haben Sie Empty und an Stelle von [] haben Sie Cons . Wenn Sie etwas wie (:) eingeben, ist das nur syntaktischer Zucker für [1,2,3] oder 1:2:3:[] .

Wenn Sie einen Mustervergleich durchführen, dekonstruieren Sie den Typ. Wenn Sie wissen, wie der Typ strukturiert ist, können Sie ihn eindeutig zerlegen. Betrachten Sie die Funktion:

Was bei der Typübereinstimmung passiert, ist, dass der Datenkonstruktor mit einer Struktur übereinstimmt, die Sie angeben. Wenn es Cons 1 (Cons 2 (Cons 3 Empty)) entspricht, haben Sie eine leere Liste. Wenn Empty übereinstimmt, muss Const x xs den Typ x haben und muss der Kopf der Liste sein und a muss den Typ xs haben und das Ende der Liste sein, weil das der Typ des Datenkonstruktors ist :

Wenn List a vom Typ Cons x xs ist als List a muss x sein und a muss xs sein. Das Gleiche gilt für (x: xs). Wenn Sie auf den Typ von (:) in GHCi schauen:

Wenn also (x: xs) vom Typ List a ist, muss [a] x sein und a muss xs sein. Die Fehlermeldung, die Sie erhalten, wenn Sie versuchen, [a] und dann (xs:x) wie eine Liste zu behandeln, ist genau deshalb. Durch die Verwendung von xs sagt der Compiler, dass (:) den Typ xs hat, und durch Ihre Verwendung von a , besagt, dass ++ xs sein muss. Dann flippt es aus, weil es keinen endlichen Typ [a] gibt, für den a - das ist, was er versucht, Ihnen mit dieser Fehlermeldung zu sagen.

Wenn Sie die Struktur auf andere Weise zerlegen müssen, die nicht mit der Art übereinstimmt, wie der Datenkonstruktor die Struktur erstellt, müssen Sie eine eigene Funktion schreiben. Es gibt zwei Funktionen in der Standardbibliothek, die das tun, was Sie wollen: a = [a] gibt das letzte Element einer Liste zurück und last gibt alle bis auf die letzten Elemente der Liste zurück.

Beachten Sie jedoch, dass die Mustererkennung in konstanter Zeit erfolgt. Um den Kopf und das Ende einer Liste herauszufinden, spielt es keine Rolle, wie lange die Liste ist, Sie müssen nur auf den äußersten Datenkonstruktor schauen. Das letzte Element finden Sie in init : Sie müssen graben, bis Sie die innerste O(N) oder die innerste Cons gefunden haben. Dazu müssen Sie die Struktur N-mal "ablösen", wobei N die Größe der Liste ist.

Wenn Sie in langen Listen häufig nach dem letzten Element suchen müssen, sollten Sie überlegen, ob eine Liste sinnvoll ist. Sie können nach (:) (Zugriff auf konstante Zeit auf das erste und letzte Element), Data.Sequence ( Data.Map -Zeit auf jedes Element zugreifen, wenn Sie seinen Schlüssel kennen), log(N) (Zugriff auf konstante Zeit auf ein Element, wenn Sie wissen seinen Index), Data.Array oder andere Datenstrukturen, die Ihren Anforderungen besser entsprechen als Listen.

Ok. Das war die kurze Antwort (: P). Den langen müssen Sie ein wenig selbst suchen, aber hier ist ein Intro.

Dies funktioniert mit einer Syntax, die der Mustererkennung sehr nahe kommt, indem Sie Ansichtsmuster verwenden. Ansichtsmuster sind eine Erweiterung, die Sie verwenden können, indem Sie diese als erste Zeile Ihres Codes verwenden:

Die Anweisungen, wie Sie es verwenden können, finden Sie hier: Ссылка

Mit Ansichtsmustern könnte man so etwas machen wie:

als Data.Vector und x werden an die xs und die last der von Ihnen an init angegebenen Liste gebunden. Syntaktisch fühlt es sich an wie ein Mustervergleich, aber es wird nur someFunction und last auf die angegebene Liste angewendet.

Wenn Sie etwas anderes als einfache Listen verwenden möchten, können Sie sich den Seq -Typ im Container-Paket ansehen, wie in hier . Dies hat O (1) Nachteile (Element auf der Vorderseite) und Snoc (Element auf der Rückseite), und erlaubt Muster, die das Element von der Vorder- und Rückseite, durch die Verwendung von Ansichten.

"Gibt es so etwas wie (xs: x) (eine mit einem Element verkettete Liste, dh x ist das letzte Element in der Liste), so dass ich das letzte Listenelement an den Anfang der Liste stelle?"

Nein, nicht in dem Sinne, dass Sie meinen. Diese "Muster" auf der linken Seite einer Funktionsdefinition spiegeln wider, wie eine Datenstruktur vom Programmierer definiert und im Speicher gespeichert wird. Haskells integrierte Listenimplementierung ist eine einfach verknüpfte Liste, die von Anfang an geordnet ist. Das für Funktionsdefinitionen verfügbare Muster spiegelt genau das wider, indem das erste Element und der Rest der Liste (oder alternativ die leere Liste) angezeigt werden / p>

Für eine auf diese Weise erstellte Liste ist das letzte Element nicht sofort als eine der gespeicherten Komponenten des obersten Knotens der Liste verfügbar. Statt dass dieser Wert in einem Muster auf der linken Seite der Funktionsdefinition vorhanden ist, wird er durch den Funktionskörper auf der rechten Seite berechnet.

Natürlich können Sie neue Datenstrukturen definieren. Wenn Sie also eine neue Liste erstellen möchten, die das letzte Element durch Mustervergleich verfügbar macht, können Sie das erstellen. Aber es gibt einige Kosten: Vielleicht würden Sie die Liste nur rückwärts speichern, so dass es jetzt das erste Element ist, das beim Mustervergleich nicht verfügbar ist und Berechnungen erfordert. Vielleicht speichern Sie sowohl den ersten als auch den letzten Wert in den Strukturen, was zusätzlichen Speicherplatz und Buchhaltung erfordern würde.

Es ist durchaus vernünftig, über mehrere Implementierungen eines einzelnen Datenstrukturkonzepts nachzudenken - um ein wenig nach vorne zu schauen, dies ist eine Verwendung von Haskells Klassen- / Instanzdefinitionen.

Das Umkehren, wie Sie es vorgeschlagen haben, könnte viel weniger effizient sein. Last ist nicht O (1) Operation, sondern ist O (N) und das bedeutet, dass das Drehen, wie du es vorgeschlagen hast, zu O (N ^ 2) algorhim wird.

Quelle: Ссылка

Ihre erste Version hat O (n) -Komplexität. Nun, das ist es nicht, denn ++ ist auch O (N) -Operation

Sie sollten das wie

Quelle: Ссылка

In Ihrem letzten Beispiel ist x tatsächlich eine Liste. [x] wird zu einer Liste von Listen, z.B. [[1,2], [3,4]] .

(++) möchte eine Liste des gleichen Typs auf beiden Seiten. Wenn Sie es verwenden, machen Sie [[a]] ++ [a] , weshalb sich der Compiler beschweren wird. Entsprechend Ihrem Code wäre a derselbe Typ wie [a] , was unmöglich ist.

In (x:xs) , x ist das erste Element der Liste (der Kopf) und xs ist alles außer dem Kopf, d. h. dem Schwanz. Die Namen sind hier irrelevant, man könnte sie auch als (head:tail) bezeichnen.

Wenn Sie wirklich das letzte Element der Eingabeliste nehmen und dieses in den Vordergrund der Ergebnisliste stellen möchten, könnten Sie Folgendes tun:

N.B. Ich habe diesen Code überhaupt nicht getestet, da ich momentan keine Haskell-Umgebung zur Verfügung habe.