Beträgt harkells Foldr immer ein Zwei-Parameter-Lambda?

foldr nimmt eine Funktion von 2 Argumenten, dies hindert jedoch nicht daran, eine Funktion von 3 Argumenten zu nehmen, vorausgesetzt, dass die Funktion die richtige Typ-Signatur hat.

Wenn wir eine Funktion hätten

Mit

Wo wir g an foldr weitergeben wollen, dann (a -> b -> b) ~ (x -> y -> z -> w) (wobei ~ Gleichheit des Typs ist). Da -> rechts assoziativ ist, können wir die Signatur g als

und seine Bedeutung ist dieselbe. Jetzt haben wir eine Funktion von zwei Parametern erzeugt, die eine Funktion eines Parameters zurückgibt. Um dies mit dem Typ a -> b -> b zu vereinheitlichen, müssen wir nur die Argumente anordnen:

Das bedeutet, dass b ~ z -> w , also y ~ b ~ z -> w und a ~ x so g 's Typ wirklich

impliziert

Dies ist sicherlich nicht unmöglich, obwohl eher unwahrscheinlich. Unser Akkumulator ist stattdessen eine Funktion, und das ist für mich mit DiffLists zu demonstrieren:

Beachten Sie, dass foldr append (const []) xs eine Funktion zurückgibt, die wir auf [] anwenden, um eine Liste umzukehren. In diesem Fall haben wir einen Alias ​​für Funktionen vom Typ [a] -> [a] namens DiffList vergeben, aber das ist wirklich nicht anders als das Schreiben von

was eine Funktion von 3 Argumenten ist.

Wie bei allen Dingen in Haskell sehen Sie sich die Typen der Dinge an, die Sie als Wegweiser für jede Funktion in ghci verwenden können.

Betrachten wir dies für foldr sehen wir:

Diese leicht abstrakte Zeichenkette kann in Englisch geschrieben werden als:

foldr ist eine Funktion, die

1) eine Funktion mit zwei Parametern vom Typ a und einem vom Typ b und gibt etwas vom Typ b

2) Ein Wert vom Typ b

3) Eine Liste von Werten vom Typ a

Und gibt einen Wert vom Typ b

Wobei a und b Typvariablen sind (siehe hier für ein gutes Tutorial zu ihnen), das kann mit einem beliebigen Typ ausgefüllt werden.

Es stellt sich heraus, dass Sie Ihr compress Problem mit einem foldr mit einer Drei-Argument-Funktion lösen können.

Lass uns das analysieren. Erstens können wir die Lesbarkeit verbessern, indem wir die letzten beiden Zeilen in

Dies macht deutlich, dass eine ternäre Funktion nichts anderes als eine binäre Funktion ist, die eine unäre Funktion zurückgibt. Der Vorteil, es auf diese Weise zu betrachten, ist, dass foldr am besten verstanden wird, wenn eine binäre Funktion übergeben wird. In der Tat übergeben wir eine binäre Funktion, die zufällig eine Funktion zurückgibt.

Konzentrieren wir uns jetzt auf Typen:

Also, x::a ist das Element der Liste, auf die wir folden. Die Funktion k ist das Ergebnis der Faltung auf dem Listenende. Das Ergebnis von f x k hat etwas vom selben Typ wie k .

Die allgemeine Idee hinter dieser anonymen Funktion ist wie folgt. Der Parameter k spielt die gleiche Rolle wie acc im OP-Code, außer dass es eine Funktion ist, die das vorherige Element w in der Liste erwartet, bevor die akkumulierte komprimierte Liste erstellt wird.

Konkret verwenden wir jetzt k x , wenn wir acc verwenden, und leiten das aktuelle Element an den nächsten Schritt weiter, da zu diesem Zeitpunkt x zum vorherigen Element w wird. Auf der obersten Ebene übergeben wir z an die Funktion, die von foldr f (const []) zurückgegeben wird.

Diese compress -Variante ist im Gegensatz zur veröffentlichten Lösung faul. In der Tat muss die veröffentlichte Lösung die gesamte Liste scannen, bevor sie etwas produziert: Dies liegt an ( \x acc -> ...) ist streng in acc und an der Verwendung von last xs . Stattdessen gibt die obige Komprimierung Listenelemente in aus eine "streaming" Mode. Tatsächlich funktioniert es auch mit unendlichen Listen:

Davon abgesehen denke ich, dass die Verwendung eines foldr hier ein bisschen komisch wirkt: Der obige Code ist wohl weniger lesbar als die explizite Rekursion.