Definition der Länge mit foldr

Zuerst Typ von foldr : (a -> b -> b) -> b -> [a] -> b

Wenn man die Verwendung in Kontext nimmt, nimmt foldr 3 Argumente an: eine Funktion (die a. ein Element einer Liste und b. einen Akkumulator aufnimmt, und gibt den Akkumulator zurück), den Startwert des Akkumulators und eine Liste. foldr gibt das Endergebnis des Akkumulators zurück, nachdem die Funktion über die Liste angewendet wurde.

Wie für dieses Stück Code:

Wie Sie sehen können, fehlt die Liste. Der Rückgabewert der rechten Seite ist also eine Funktion, die eine Liste aufnimmt und ein Int erzeugt (gleicher Typ wie 0 ). Geben Sie Folgendes ein: [a] -> Int .

Was bedeutet die rechte Seite: (\_ n -> 1 + n) 0

\ bedeutet eine unbenannte Funktion deklarieren

_ bedeutet, dass das Element aus der Liste ignoriert wird (entspricht a im Typ foldr ). Wie Sie wissen, wird foldr durch die Liste gehen und die Funktion auf jedes Element anwenden. Dies ist das Element, das an die Funktion übergeben wird. Wir verwenden es nicht in einer length -Funktion, daher geben wir an, dass es ignoriert werden sollte.

n ist der Parameter für den Int, der als Akkumulator übergeben wird.

-> bedeutet Rückkehr

1 + n erhöht den Akkumulator. Sie können sich vorstellen, dass der Rückgabewert an foldr zurückgegeben wird und foldr den Wert speichert, der an den nächsten Aufruf der Funktion (\_ n -> 1 + n) übergeben wird.

Der 0 außerhalb der Klammer ist der Startwert des Zählers.

Die Funktion foldr soll die Liste mit einem rechts assoziativen Operator falten, Sie können leicht verstehen, was die Funktion macht, wenn Sie den Operator (+) verwenden (Die Funktion hat das gleiche Verhalten wie sum ):

Für Ihre Längenfunktion entspricht dies:

Das ist die foldr für

Es gibt mehrere gleichwertige Wege, es zu verstehen. Erster: foldr f z [1, 2, 3, 4, ..., n] berechnet den folgenden Wert:

Also in deinem Fall:

Ein anderer ist von dieser Funktion zu starten, die eine Liste kopiert:

Das mag wie eine triviale Funktion aussehen, aber foldr ist im Grunde nur das, aber abgesehen davon, dass wir die leere Liste [] und den Paarkonstruktor : in die rechte Seite hartkodieren, verwenden wir stattdessen eine beliebige Konstante und Funktion als Argumente angegeben. Manchmal möchte ich diese Argumente fakeCons und fakeNil nennen ( cons und nil sind die Namen der : -Operator und [] -Konstante in der Lisp-Sprache), weil Sie gewissermaßen " Kopieren "der Liste, aber mit gefälschten Konstruktoren:

Unter dieser Interpretation "kopiert" Ihre length -Funktion eine Liste, außer dass sie anstelle der leeren Liste 0 verwendet und statt : die Elemente verwirft und 1 zur laufenden Summe hinzufügt .

Und hier ist noch eine dritte Interpretation von foldr f z xs :

1. z ist die Lösung Ihres Problems, wenn die Liste leer ist.
2. f ist eine Funktion, die zwei Argumente akzeptiert: ein Element der Liste und eine Teillösung : die Lösung für Ihr Problem für die Liste der Elemente, die rechts neben dem Element angezeigt werden, das übergeben wird %Code%. f erzeugt dann eine Lösung, die "ein Element größer" ist.

Also im Falle von f :

1. Die Länge einer leeren Liste ist 0, deshalb verwenden Sie 0 als zweites Argument für length .
2. Wenn die Länge von foldr xs ist, dann ist die Länge von n x:xs . Das ist das, was Ihr erstes Argument in n+1 , foldr tut: es berechnet die Länge einer Liste, die als Argumente das erste Element der Liste (die wir in diesem Fall ignorieren) und die Länge des Rests der Liste angibt Liste ( \_ n -> n + 1 ).

Diese Denkweise von n ist sehr mächtig und sollte nicht unterschätzt werden. Im Grunde genommen dürfen Sie in der Funktion, die Sie als erstes Argument an foldr übergeben, davon ausgehen, dass das Problem, das Sie zu lösen versuchen, bereits für alle Listen gelöst wurde, die kürzer sind als die, mit der Sie es zu tun haben. Alle Ihre Argumentfunktion muss also eine Antwort für eine Liste berechnen, die ein Element länger ist.