Kann mir jemand diese Haskell-Funktionen erklären?

Question

Ich habe mich in der Vergangenheit mit Haskell herumgetrieben und bin erst kürzlich wieder ernsthaft dazu gekommen, und ich lese echte Haskell. Einige der Beispiele, die sie geglänzt haben, muss ich noch verstehen. Solch ein:

myLength []  = 0 
myLength (x:xs) = 1 + myLength (xs) 

Ich sehe nicht, wie das funktioniert, was 1 ist auch wirklich hinzugefügt? Wie gibt die Rekursion etwas zurück, das hinzugefügt werden kann? Ich verstehe es nicht.

Und hier haben wir diese:

splitLines [] = [] 
splitLines cs = 
     let (pre, suf) = break isLineTerminator cs 
     in pre : case suf of 
        ('\r':'\n':rest) -> splitLines rest 
        ('\r':rest)  -> splitLines rest 
        ('\n':rest)  -> splitLines rest 
        _    -> [] 

isLineTerminator c = c == '\r' || c == '\n' 

Wie funktioniert das, was wirklich zu sehr an vorbestellt werden? Ich sehe nicht, wie das Ergebnis des Fallausdrucks etwas ist, mit dem man sich verketten kann. Vielleicht brauche ich nur jemanden, der die Auswertung dieser Funktionen im Detail erklärt. Ich muss etwas sehr Wichtiges vermissen.

Vielen Dank im Voraus!

EDIT: Ich weiß, es war ein Kopieren-Einfügen fehlgeschlagen. Es tut uns leid.

EDIT 2: Es scheint, dass meine Verwirrung war mit dem, was diese Funktionen tatsächlich waren/zurückgeben/Ich habe alles jetzt ausgearbeitet. Danke für die Antworten Jungs, es hat endlich geklickt! Ich schätze es!

Answer 1

Wie für die erste, es ist eine sehr einfache Art der Rekursion. Allerdings scheint es fehlt ein Teil zu sein:

myLength [] = 0 

Es funktioniert durch ein Element zu der Zeit aus der Liste die Skalierung ausgeschaltet und das Hinzufügen einer zum Ergebnis bei. Um sichtbar zu machen, betrachten den Anruf

myLength [1,2,3] 

, die evaluieren:

1 + myLength [2,3] 
1 + 1 + myLength [3] 
1 + 1 + 1 + myLength [] 
1 + 1 + 1 + 0 

die 3.

Was die zweite ist, na ja, Sie haben geteilt bereits die Zeichenfolge auf der nächsten Zeilenumbruch in zwei Teile: pre und suff. Nun wird suf entweder mit a \ n oder a \ r oder a \ r \ n beginnen. Wir möchten diese entfernen. Wir verwenden also Mustervergleiche. Sehen Sie, wie die Restvariable im Wesentlichen die Suff-Variable abzüglich der ursprünglichen Zeilenumbruchzeichen ist.

So haben wir vor, was die erste Zeile ist, und Ruhe, die den Rest des Textes ist. Um also den Rest in Zeilen aufzuteilen, rufen wir splitLines rekursiv auf und verketten das Ergebnis nach pre.

Um zu visualisieren, sagen Sie, dass Sie die Zeichenfolge "foo \ nbar \ r \ nbaz" haben.

Also, wenn Sie anrufen, wird das Ergebnis sein:

[ pre => foo, suf => \nbar\r\nbaz, rest => bar\r\n\baz ] 
foo : splitLines bar\r\nbaz 

dann Teilungslinien erneut aufgerufen, und das Ergebnis wird erweitert in:

[ pre => bar, suf => \r\nbaz, rest = baz ] 
foo : bar : splitLines baz 

dann noch einmal:

[ pre => baz, suf => [], rest = [] ] 
foo : bar : baz 

was das Endergebnis ist.

Answer 2

Ich denke, die Definition von myLength der Fall vermisst wo die Liste leer ist:

myLength [] = 0 
myLength (x:xs) = 1 + myLength (xs) 

Mit dieser Definition die myLength einer leeren Liste ist 0. Die (x:xs) patten eine Liste in das erste Element auspackt, a, und eine Liste mit dem Rest der Artikel, xs. Wenn die Liste ein Element hat, dann ist xs eine leere Liste, also ist das Ergebnis 1 + 0. Und so weiter.

Rekursion ist am einfachsten zu verstehen, wenn Sie zuerst den Basisfall betrachten und dann sehen, wie die einzelnen Rekursionsebenen auf dem Ergebnis aufbauen. (Der Basisfall ist der Fall, in dem sich die Funktion nicht selbst aufruft. Wenn eine rekursive Funktion keinen Basisfall hat, ist die Ausgabe unendlich.)

Im zweiten Beispiel der Basisfall (der letzte Fall in der case-statment) ist auch eine leere Liste. Pre wird also immer an eine Liste angehängt, die eine neue, längere Liste ergibt.

Answer 3

Re: myLength (x:xs) = 1 + myLength (xs) - das ist „Hälfte“ der Definition von myLength, sagt es, durch Mustererkennung, dass wenn das Argument einen Kopf und einen Schwanz, dann ist das Ergebnis einer mehr als der rekursive Schwanz Aufruf am Ende - es muss eine weitere Hälfte geben, um zu sagen, dass das Ergebnis 0 ist, wenn das Argument x:xs nicht übereinstimmen kann, dh wenn das Argument eine leere Liste ist.

Im zweiten Fall wird die Möglichkeit, dass verschiedene Muster übereinstimmen, nur etwas explizit über case gemacht.

BTW, ist Faulheit nicht ein Schlüsselproblem hier - ML, mit eifriger Bewertung, aber Mustervergleich sehr ähnlich wie Haskell, würde sehr ähnlich funktionieren. Sieht so aus, als ob Mustererkennung das ist, was du wirklich auffrischen musst.

Answer 4

Zunächst einmal das erste Beispiel so sein sollte (edit: es sieht aus wie Sie es jetzt fest):

myLength []  = 0 
myLength (x:xs) = 1 + myLength (xs) 

Es funktioniert wie folgt: Ich sage es eine Liste mit drei Elementen geben, Es gibt eins plus die Länge des Schwanzes (das ist eins plus die Länge des Schwanzes (das ist eins plus die Länge des Schwanzes, (das ist [] an diesem Punkt), die 1 ist, die w) ist, die ist 3 (die endgültige Antwort). Vielleicht helfen Ihnen verschachtelte Klammern dabei, es zu verstehen. ;-)

Answer 5

Es ist lehrreich zu sehen, was die Typensignaturen der Funktionen wären. Sie könnten sein:

myLength :: [a] -> Int 

In myLength, 1 wird hinzugefügt, um das Ergebnis des rekursiven Aufrufs zu myLength, das ist ein Int, was wiederum in einem Int.

splitLines :: [Char] -> [[Char]] 

In splitLines, pre (a [Char]) mit dem Ergebnis der Case-Anweisung wird vorangestellt, die vom an den Fällen sucht, ist entweder das Ergebnis eines rekursiven Aufrufs zu splitLines, die [[Char]] ist; oder eine leere Liste. In beiden Fällen führt das Voranstellen von pre (ein [Char]) wiederum zu einem [[Char]].