Wie zu implementieren löschen mit Foldr in Haskell

Question

Ich habe Falten in den letzten paar Tagen studiert. Ich kann mit ihnen einfache Funktionen implementieren, wie length, concat und filter. Was ich feststelle, ist zu versuchen, mit foldr Funktionen wie delete, take und find zu implementieren. Ich habe diese mit expliziter Rekursion implementiert, aber es scheint mir nicht offensichtlich zu sein, diese Arten von Funktionen in richtige Falten umzuwandeln.

Ich habe die Tutorials von Graham Hutton und Bernie Pope studiert. Hittons dropWhile imitierend, konnte ich delete mit foldr implementieren, aber es scheitert an unendlichen Listen.

Aus der Lektüre Implement insert in haskell with foldr, How can this function be written using foldr? und Implementing take using foldr, so scheint es, dass ich foldr verwenden, um eine Funktion zu erzeugen, die dann etwas tut. Aber ich verstehe diese Lösungen nicht wirklich und habe keine Idee, wie man zum Beispiel delete auf diese Weise implementiert.

Könnten Sie mir eine allgemeine Strategie für die Implementierung mit foldr faulen Versionen von Funktionen wie die, die ich erwähnte, erklären. Vielleicht könnten Sie auch delete als Beispiel implementieren, da dies wahrscheinlich einer der einfachsten ist.

Ich bin auf der Suche nach einer detaillierten Erklärung, die ein Anfänger verstehen kann. Ich bin nicht nur an Lösungen interessiert, ich möchte ein Verständnis entwickeln, um selbst Lösungen für ähnliche Probleme zu finden.

Danke.

Bearbeiten: Im Moment des Schreibens gibt es eine nützliche Antwort, aber es ist nicht ganz das, was ich gesucht habe. Mich interessiert eher ein Ansatz, der mit foldr eine Funktion generiert, die dann etwas bewirkt. Die Links in meiner Frage haben Beispiele dafür. Ich verstehe diese Lösungen nicht ganz, daher hätte ich gerne mehr Informationen zu diesem Ansatz.

Answer 1

delete ist eine modale Suche. Es gibt zwei verschiedene Betriebsmodi - ob das Ergebnis bereits gefunden wurde oder nicht. Sie können foldr verwenden, um eine Funktion zu erstellen, die den Status bei jedem Überprü- fen des Elements nach unten übergibt. Im Fall von delete kann der Zustand ein einfacher Bool sein. Es ist nicht gerade der beste Typ, aber es wird reichen. Nachdem Sie den Zustandstyp identifiziert haben, können Sie mit der Arbeit an der foldr Konstruktion beginnen. Ich werde es durchgehen und herausfinden, wie ich es gemacht habe. Ich werde ScopedTypeVariables aktivieren, nur damit ich die Art der Teilausdrücke besser kommentieren kann. Wenn Sie den Zustandstyp kennen, wissen Sie, dass Sie foldr möchten, um eine Funktion zu generieren, die einen Wert dieses Typs annimmt und einen Wert des gewünschten endgültigen Typs zurückgibt. Das ist genug, um Dinge zu skizzieren.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g = undefined 

Es ist ein Anfang. Die genaue Bedeutung von g ist hier ein wenig knifflig. Es ist eigentlich die Funktion zur Bearbeitung des Rests der Liste. Es ist richtig, es als eine Fortsetzung zu betrachten, tatsächlich. Es stellt absolut dar, den Rest der Falte, mit Ihrem beliebigen Staat durchzuführen, den Sie wählen, um fortzufahren. Angesichts dessen ist es an der Zeit herauszufinden, was man in diese undefined Orte stecken kann.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

Das scheint relativ einfach. Wenn das aktuelle Element das Objekt ist, nach dem gesucht wird und das noch nicht gefunden wurde, geben Sie es nicht aus und setzen Sie den Status fort, der auf True gesetzt wurde, um anzuzeigen, dass es gefunden wurde. otherwise, geben Sie den aktuellen Wert aus und fahren Sie mit dem aktuellen Status fort.Dies lässt den Rest der Argumente nur foldr. Der letzte ist der Ausgangszustand. Der andere ist die Statusfunktion für eine leere Liste. Ok, die sind auch nicht schlecht.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f (const []) xs False 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

Unabhängig vom Status eine leere Liste erstellen, wenn eine leere Liste gefunden wird. Und der Ausgangszustand ist, dass das gesuchte Element noch nicht gefunden wurde.

Diese Technik ist auch in anderen Fällen anwendbar. Zum Beispiel kann foldl als foldr auf diese Weise geschrieben werden. Wenn Sie foldl als eine Funktion betrachten, die wiederholt einen anfänglichen Akkumulator transformiert, können Sie erraten, dass die Funktion erzeugt wird - wie der Anfangswert transformiert wird.

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = undefined 

Die Basis Fälle sind nicht zu schwierig zu finden, wenn das Problem als die Manipulation der Anfangsspeicher definiert ist, z dort genannt. Die leere Liste ist die Identitätstransformation id, und der an die erstellte Funktion übergebene Wert ist z.

Die Implementierung von g ist komplizierter. Es kann nicht blind auf Typen durchgeführt werden, da es zwei verschiedene Implementierungen gibt, die alle erwarteten Werte und Typprüfungen verwenden. Dies ist ein Fall, in dem Typen nicht ausreichen und Sie die Bedeutung der verfügbaren Funktionen berücksichtigen müssen.

Beginnen wir mit einer Bestandsaufnahme der Werte, die scheinbar verwendet werden sollten, und ihrer Typen. Die Dinge, die so scheinen, als müssten sie im Körper von g verwendet werden, sind f :: a -> b -> a, x :: b, cont :: (a -> a) und acc :: a. f wird offensichtlich als zweites Argument x nehmen, aber es gibt eine Frage der geeigneten Stelle zu verwenden cont. Um herauszufinden, wo es hingehört, denken Sie daran, dass es die Transformationsfunktion darstellt, die durch die Verarbeitung des Rests der Liste zurückgegeben wird, und dass foldl das aktuelle Element verarbeitet und das Ergebnis dieser Verarbeitung an den Rest der Liste übergibt.

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $ f acc x 

auch Dies deutet darauf hin, dass foldl' mit nur einer winzigen Veränderung auf diese Weise geschrieben werden kann:

{-# LANGUAGE ScopedTypeVariables #-} 

foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl' f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $! f acc x 

Der Unterschied besteht darin, dass ($!) verwendet wird Bewertung der f acc x vorzuschlagen, bevor es zu cont übergeben wird. (Ich sage „vorschlagen“, weil es einige Grenzfälle, wo ($!) nicht Auswertung zwingen sogar soweit WHNF.)

Answer 2

delete funktioniert nicht auf der gesamten Liste gleichmäßig. Die Struktur der Berechnung berücksichtigt nicht nur die gesamte Liste Element für Element. Es unterscheidet sich, nachdem es das gesuchte Element getroffen hat. Dies sagt Ihnen, dass es nicht implementiert werden kann als nur ein foldr. Es muss eine Art Nachbearbeitung geben.

Wenn dies passiert, ist das allgemeine Muster, dass Sie ein Paar Werte erstellen und nur einen von ihnen am Ende der foldr nehmen. Das ist wahrscheinlich das, was Sie getan haben, als Sie Huttons dropWhile nachgeahmt haben, obwohl ich mir nicht sicher bin, da Sie keinen Code hinzugefügt haben. Etwas wie das?

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x (xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

Die Hauptidee ist, dass xs1 wird immer der volle Schwanz der Liste sein, und xs2 ist das Ergebnis der delete über das Ende der Liste. Da Sie nur das erste übereinstimmende Element entfernen möchten, möchten Sie das Ergebnis delete nicht über dem Endwert verwenden, wenn Sie den gesuchten Wert suchen. Sie möchten den Rest der Liste nur unverändert anzeigen. was zum Glück ist, was immer in sein wird.

Und ja, das funktioniert nicht auf unendlichen Listen - aber nur aus einem ganz bestimmten Grund. Das Lambda ist zu streng.foldr funktioniert nur bei unendlichen Listen, wenn die Funktion, die es bereitstellt, nicht immer die Auswertung seines zweiten Arguments erzwingt, und dass Lambda immer die Auswertung seines zweiten Arguments in der Musterübereinstimmung auf dem Paar erzwingt. Der Wechsel zu einer unwiderlegbaren Musterübereinstimmung behebt das, indem es dem Lambda erlaubt, einen Konstruktor zu erzeugen, bevor es sein zweites Argument untersucht.

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x ~(xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

Das ist nicht der einzige Weg, um dieses Ergebnis zu erhalten. Die Verwendung einer Let-Binding oder und snd als Accessoren auf dem Tupel würde auch die Aufgabe erledigen. Aber es ist die Veränderung mit dem kleinsten Unterschied.

Der wichtigste Take-Away hier ist sehr vorsichtig mit dem zweiten Argument der reduzierenden Funktion umgehen, die Sie an foldr übergeben. Sie möchten das zweite Argument so weit wie möglich zurückstellen, damit die foldr in möglichst vielen Fällen träge streamen kann.

Wenn Sie sich das Lambda anschauen, sehen Sie, dass die gewählte Verzweigung ausgewählt wird, bevor Sie etwas mit dem zweiten Argument der reduzierenden Funktion tun. Außerdem werden Sie feststellen, dass die reduzierende Funktion meistens einen Listenkonstruktor in beiden Hälften des Ergebnistupels erzeugt, bevor das zweite Argument ausgewertet werden muss. Da diese Listenkonstruktoren es aus delete machen, sind sie wichtig für das Streaming - solange Sie das Paar nicht in die Quere kommen lassen. Und das Muster-Match auf dem Paar unwiderlegbar zu machen ist das, was es aus dem Weg hält.

Als Bonus Beispiel für die Streaming-Eigenschaften von foldr, mein Lieblingsbeispiel betrachten:

dropWhileEnd :: (a -> Bool) -> [a] -> [a] 
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] 

Es strömt - so viel wie er kann. Wenn Sie genau herausfinden, wann und warum es funktioniert und nicht streamt, werden Sie so ziemlich jedes Detail der Streaming-Struktur von foldr verstehen.

Answer 3

hier ist ein einfaches Löschen, mit foldr implementiert:

delete :: (Eq a) => a -> [a] -> [a] 
delete a xs = foldr (\x xs -> if x == a then (xs) else (x:xs)) [] xs