Real World Haskell, Kapitel 4, Seite 98 des Drucks fragt, ob words
mit Falten implementiert werden kann, und dies ist auch meine Frage:
Ist es möglich? Wenn nicht, warum? Wenn ja, wie?
Ich kam auf Folgendes, das auf der Idee basiert, dass jedem Nicht-Leerzeichen das letzte Wort in der Ausgabeliste vorangestellt werden sollte (dies geschieht im otherwise
Guard) und dass ein Leerzeichen das Anhängen eines leeren Wortes an auslösen sollte die Ausgabeliste, falls noch keine vorhanden ist (dies wird im if
- then
- behandelt else
).
myWords :: String -> [String]
myWords = foldr step [[]]
where
step x yss@(y:ys)
| x == ' ' = if y == "" then yss else "":yss
| otherwise = (x:y):ys
Diese Lösung ist eindeutig falsch, da führende Leerzeichen in der Eingabezeichenfolge zu einer führenden leeren Zeichenfolge in der Ausgabeliste der Zeichenfolgen führen.
Unter dem obigen Link habe ich einige der vorgeschlagenen Lösungen für andere Leser untersucht, und viele von ihnen funktionieren ähnlich wie meine Lösung, aber sie "verarbeiten" im Allgemeinen die Ausgabe der Falte nach, indem tail
sie sie beispielsweise dort bereitstellen ist eine leere führende Zeichenfolge.
Andere Ansätze verwenden Tupel (eigentlich nur Paare), so dass die Falte sich mit dem Paar befasst und die führenden / nachfolgenden Leerzeichen gut handhaben kann.
Bei all diesen Ansätzen foldr
(oder einer anderen Falte, fwiw) ist dies nicht die Funktion, die die endgültige Ausgabe sofort liefert. Es gibt immer etwas anderes, bei dem die Ausgabe irgendwie angepasst werden muss.
Daher gehe ich zurück zur ursprünglichen Frage und frage, ob es tatsächlich möglich ist, words
mithilfe von Falten zu implementieren (so, dass nachfolgende / führende / wiederholte Leerzeichen korrekt behandelt werden). Mit Falten meine ich, dass die Faltfunktion die äußerste Funktion sein muss:
myWords :: String -> [String]
myWords input = foldr step seed input
quelle
["xa"] == words "xa" == step 'x' (words "a") == step 'x' (words " a") == words "x a" == ["x", "a"]
, was den Vorteil hat, ein gültiges Argument für jede Richtung der Falte zu sein@chi hat ein wunderbares Argument, dass Sie nicht
words
mit "a" Fold implementieren können , aber Sie haben gesagt, mit Fold s .Sowohl die äußerste als auch die innerste Funktion sind Falten. ;-);
quelle
Ja. Obwohl es ein wenig schwierig ist, können Sie diesen Job dennoch ordnungsgemäß ausführen, indem Sie einen einzelnen
foldr
und nichts anderes verwenden, wenn Sie sich mit CPS ( Continuation Passing Style ) befassen . Ich hatte eine besondere Art von gezeigtchunksOf
Funktion gezeigt.Bei dieser Art von Falten ist unser Akkumulator, daher ist das Ergebnis der Faltung eine Funktion, und wir müssen es auf eine Identitätseingabe anwenden, damit wir das Endergebnis erhalten. Dies kann also als letzte Verarbeitungsstufe gelten oder nicht, da wir hier eine einzelne Falte verwenden und deren Typ die Funktion enthält. Offen für Debatten :)
sf
: Der anfängliche Funktionswert, mit dem begonnen werden soll.go
: Die IteratorfunktionWir nutzen die Leistung des CPS hier tatsächlich nicht vollständig aus, da wir in jeder Runde sowohl den vorherigen
pc
als auch den richtigen Charakterc
zur Hand haben. Es war sehr nützlich bei derchunksOf
Funktion oben erwähnt , während eines Chunking[Int]
in[[Int]]
jede Zeit eine aufsteigende Folge von Elementen gebrochen.quelle