Wie würden Sie map und filter mit foldr in Haskell definieren?

Question

Ich beschäftige mich ein wenig mit funktionalen Sprachen (derzeit mit Haskell). Ich bin auf eine Haskell-basierte Aufgabe gestoßen, die die Definition von map und filter in Form von foldr erfordert. Ich verstehe beim besten Willen nicht ganz, wie ich das anstellen soll.

Wenn ich zum Beispiel eine Map-Funktion definiere wie:

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\x xs -> (f x):xs) [] xs

Ich weiß nicht, warum das erste Element der Liste immer ignoriert wird. Das bedeutet, dass:

map' (*2) [1,2,3,4]

ergibt [4,6,8] anstelle von [2,4,6,8]

Ähnliches gilt für die Funktion "Mein Filter":

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p (x:xs)    = foldr (\x xs -> if p x then x:xs else xs ) [] xs

wenn sie als ausgeführt werden:

filter' even [2,3,4,5,6]

ergibt [4,6] anstelle von [2,4,6]

Warum sollte dies der Fall sein? Und wie SOLLTE ich diese Funktionen definieren, um die erwarteten Ergebnisse zu erhalten? Ich nehme an, dass etwas mit meinen Lambda-Ausdrücken falsch ist...

Answer 1

Ich wünschte, ich könnte einfach kommentieren, aber leider habe ich nicht genug Karma.

Die anderen Antworten sind alle gut, aber ich denke, die größte Verwirrung scheint von Ihrer Verwendung von x und xs auszugehen.

Wenn man es umschreibt als

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\y ys -> (f y):ys) [] xs

würden Sie deutlich sehen, dass x wird auf der rechten Seite nicht einmal erwähnt, so dass es unmöglich in der Lösung enthalten sein kann.

Prost

Answer 2

Zu Ihrer ersten Frage, foldr verfügt bereits über einen Fall für die leere Liste, so dass Sie in Ihrer eigenen Map keinen Fall für diese Liste vorsehen müssen und sollten.

map' f = foldr (\x xs -> f x : xs) []

Das Gleiche gilt für filter'

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

Mit Ihren Lambda-Ausdrücken ist alles in Ordnung, aber mit Ihren Definitionen von filter' y map' . Im Fall von cons (x:xs) essen Sie den Kopf ( x ) weg und übergeben dann den Schwanz an foldr . Die foldr Funktion kann nie das erste Element sehen, das man bereits gegessen hat :)

Bitte beachten Sie das:

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

gleichwertig ist ( -Äquivalent ) zu:

filter' p xs = foldr (\x xs -> if p x then x : xs else xs) [] xs

Answer 3

Ich würde die Karte mit foldr und Funktionszusammensetzung wie folgt:

map :: (a -> b) -> [a] -> [b]
map f = foldr ((:).f) []

Und für den Fall des Filters:

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

Beachten Sie, dass es nicht notwendig ist, die Liste selbst zu übergeben, wenn Sie Funktionen über Listen mit foldr oder foldl definieren. Das Problem bei Ihrer Lösung ist, dass Sie den Kopf der Liste weglassen und dann die Map auf die Liste anwenden und Deshalb fehlt der Kopf der Liste, wenn das Ergebnis angezeigt wird.

Answer 4

In Ihren Definitionen führen Sie einen Mustervergleich für x:xs das heißt, wenn Ihr Argument [1,2,3,4] , x ist gebunden an 1 y xs ist an den Rest der Liste gebunden: [2,3,4] .

Was Sie nicht tun sollten, ist einfach wegwerfen x: Teil. Dann wird Ihr foldr wird an der gesamten Liste arbeiten.

Ihre Definitionen sollten also wie folgt aussehen:

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f xs       = foldr (\x xs -> (f x):xs) [] xs

et

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p xs        = foldr (\x xs -> if p x then x:xs else xs ) [] xs

Answer 5

Ich bin neu in Haskell (in der Tat habe ich diese Seite gefunden, die die gleiche Frage stellt), aber dies ist mein Verständnis von Listen und foldr so weit:

• Listen sind Elemente, die mit dem nächsten Element mit dem Cons verknüpft sind (:) Operator. Sie enden mit der leeren Liste [] . (betrachten Sie es als einen binären Operator, genau wie die Addition (+) 1+2+3+4 = 10 , 1:2:3:4:[] = [1,2,3,4]
• Die Funktion foldr nimmt eine Funktion mit zwei Parametern an. Sie ersetzt den Operator cons, der festlegt, wie jedes Element mit dem nächsten verknüpft wird.
• Es nimmt auch den Endwert für die Operation, der als Anfangswert angesehen werden kann, der der leeren Liste zugewiesen wird. für cons ist es die leere Liste [] . Wenn Sie eine leere Liste mit einer beliebigen Liste verknüpfen, ist das Ergebnis die Liste selbst. so ist für eine sum Funktion ist es 0 . für eine Multiplikationsfunktion lautet sie 1 , usw.
• und es nimmt die Liste selbst

Meine Lösung sieht also folgendermaßen aus:

filter' p = foldr (\x n -> if p x then x : n else n) []

der Lambda-Ausdruck ist unsere Verknüpfungsfunktion, die anstelle des Cons verwendet wird (:) Betreiber. Leere Liste ist unser Standardwert für eine leere Liste. Wenn das Prädikat erfüllt ist, verweisen wir auf das nächste Element mit (:) als normal, sonst verlinken wir einfach gar nicht.

map' f = foldr (\x n -> f x : n) []

hier verlinken wir f x zum nächsten Punkt zu wechseln, anstatt nur x , wodurch die Liste einfach dupliziert würde.

Beachten Sie auch, dass Sie den Mustervergleich nicht verwenden müssen, da wir foldr bereits sagen, was im Falle einer leeren Liste zu tun ist.

Ich weiß, dass diese Frage schon sehr alt ist, aber ich wollte sie trotzdem beantworten. Ich hoffe, es ist nicht gegen die Regeln.