Haskell foldl Implementierung mit foldr

Question

Ich habe Probleme, die Implementierung der foldl Funktion mit foldr zu verstehen. Ich habe diese Frage (Writing foldl using foldr) gelesen und ich habe noch einige Dinge, die ich nicht verstehen, in dem folgende Beispiel:

fun :: [Int] -> [Int] 
fun l = foldr g (const []) l 1 
    where g x f lst = if gcd x lst == 1 then x : f x else f lst 

Die Funktion nimmt eine Liste als Parameter und zurückzukehren und eine andere Liste gcd(l[i], l[i + 1] = 1 wo.

Meine Fragen sind:
1. Wer x sind, f und lst
2. Was const[] ist und warum kann ich die id Funktion nicht verwenden?

Answer 1

foldr ‚s Art Signatur ist diese

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 

Dies bedeutet, dass Ihr foldr auf seine drei Argumente angewendet muss eine Funktion zurück, die die 1 als Argument.

So können Sie spezialisieren Ihre foldr auf diese

foldr :: (Int -> (Int -> [Int]) -> (Int -> [Int])) 
     -> (Int -> [Int]) 
     -> [Int] 
     -> (Int -> [Int]) 

Dies bedeutet, dass Ihre g Funktion den folgenden Typ

g :: Int -> (Int -> [Int]) -> Int -> [Int] 

So haben müssen Ihre Parameter den Typ

x :: Int 
f :: Int -> [Int] 
lst :: Int 

Und foldr in seinem 2. argumen t erfordert eine Int -> [Int] statt nur Int, so dass Sie nicht den Wert [] übergeben können.

Zum Glück const gibt eine Funktion, die ihr Argument ignoriert und das Rück nur immer einen konstanten Ausdrucks

const [] :: a -> [b] 

In Ihrem Fall f ist in der Tat eine Art Akkumulator. Aber anstatt z.B. eine Liste von Werten zu einer bestimmten Anzahl, Sie verketten Funktionen hier. Wenn Sie am Ende die Funktion 1 an diese Funktionskette übergeben, wird sie ausgewertet und erstellt dann die tatsächliche Liste, die Sie in fun zurückgeben.

Answer 2

foldr ist eines dieser komischen Werkzeuge wie Fahrräder, die wirklich einfach zu bedienen sind, sobald man den Dreh raus hat, aber schwer von Anfang an zu lernen. Nach einigen Jahren Erfahrung, bin ich wirklich gut darin gewesen, Probleme zu erkennen, die ich mit foldr lösen kann, und zwar sofort und korrekt, aber es könnte leicht eine Weile dauern, um herauszufinden, was genau ich getan habe Detail zu erklären!

Vom praktischen Standpunkt denke ich normalerweise an foldr in vage Fortsetzung-passender Sprache. Das Ignorieren der „einfachen“ Fall, in dem foldr nur auf drei Argumente angewendet wird, sieht eine Anwendung von foldr wie folgt aus:

foldr go finish xs acc1 acc2 ... where 
    finish acc1 acc2 ... = ? 
    go x cont acc1 acc2 ... = ? 

acc1 usw. sind Akkumulatoren bestanden „von links nach rechts“.Das Ergebnis besteht konzeptuell aus einem einzelnen Wert, der "von rechts nach links" übergeben wird.

finish erhält die Endwerte der Akkumulatoren und erzeugt etwas vom Ergebnistyp. Es ist in der Regel der einfachste Teil zu schreiben, weil

foldr go finish [] acc1 acc2 ... 
= 
finish acc1 acc2 ... 

Also, wenn Sie nur herausfinden, was Sie wollen Falte zu erzeugen, schreiben finish ziemlich mechanisch ist.

go erhält ein einzelnes Containerelement, eine "Fortsetzung" und die Akkumulatoren. Er übergibt modifizierte Werte, wenn diese Akkumulatoren zur Fortsetzung "weiterleiten", um ein Ergebnis zu erhalten, und verwendet dieses Ergebnis, um ein eigenes Ergebnis zu erstellen.

foldl ist ein besonders einfacher Fall, weil seine go Funktion nur das Ergebnis zurückgibt, das es vom Falten des Rests des Containers mit einem neuen Akkumulatorargument erhält. Ich denke, es ist ein bisschen aufschlussreicher, ein Beispiel zu betrachten, das ein bisschen mehr tut. Hier ist eine, die einen Container mit Zahlen nimmt und eine Liste von Paaren erstellt, die eine laufende Summe und ein laufendes Produkt darstellen.

sumsProducts :: (Num n, Foldable f) => f n -> [(n, n)] 
sumsProducts xs = foldr go finish xs 0 1 
    where 
    finish total prod = [(total, prod)] 
    go x cont total prod = 
     (total, prod) : cont (x + total) (x * prod)