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

Eine andere Art, darüber nachzudenken: foldr existiert, weil das folgende rekursive Muster häufig verwendet wird:

-- Example 1: Sum up numbers
summa :: Num a => [a] -> a
summa []     = 0
summa (x:xs) = x + suma xs

Das Produkt von Zahlen oder auch die Umkehrung einer Liste sieht strukturell sehr ähnlich aus wie die vorherige rekursive Funktion:

-- Example 2: Reverse numbers
reverso :: [a] -> [a]
reverso []      = []
reverso (x:xs)  = x `op` reverso xs
  where
    op = (\curr acc -> acc ++ [curr])

Die Struktur in den obigen Beispielen unterscheidet sich nur durch den Ausgangswert ( 0 für Summa und [] für Reverso) zusammen mit dem Operator zwischen dem ersten Wert und dem rekursiven Aufruf ( + für Summa und (\q qs -> qs ++ [q]) für Reverso). Die Funktionsstruktur für die obigen Beispiele lässt sich also allgemein wie folgt darstellen

-- Generic function structure
foo :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
foo op init_val []      = init_val
foo op init_val (x:xs)  = x `op` foo op init_val xs

Um zu sehen, dass dieses "generische" foo funktioniert, können wir nun reverso umschreiben, indem wir foo verwenden und ihm den Operator, den Anfangswert und die Liste selbst übergeben:

-- Test: reverso using foo
foo (\curr acc -> acc ++ [curr]) [] [1,2,3,4]

Geben wir foo eine allgemeinere Typsignatur, damit es auch für andere Probleme funktioniert:

foo :: (a -> b -> b) -> b -> [a] -> b

Um nun auf Ihre Frage zurückzukommen - wir könnten den Filter so schreiben:

-- Example 3: filter
filtero :: (a -> Bool) -> [a] -> [a]
filtero p []     = []
filtero p (x:xs) = x `filterLogic` (filtero p xs)
  where
     filterLogic = (\curr acc -> if (p curr) then curr:acc else acc)

Auch hier ist die Struktur sehr ähnlich wie bei Summa und Reverso. Daher sollten wir in der Lage sein, foo zu verwenden, um es umzuschreiben. Nehmen wir an, wir wollen die geraden Zahlen aus der Liste [1,2,3,4] herausfiltern. Dann übergeben wir wieder foo den Operator (in diesem Fall filterLogic ), den Anfangswert und die Liste selbst. filterLogic in diesem Beispiel nimmt eine p Funktion, ein so genanntes Prädikat, das wir für den Aufruf definieren müssen:

let p = even in foo (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4] 

foo heißt in Haskell foldr . Wir haben also den Filter mit foldr umgeschrieben.

let p = even in foldr (\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4] 

Also, Filter kann geschrieben werden mit foldr wie wir gesehen haben:

-- Solution 1: filter using foldr
filtero' :: (a -> Bool) -> [a] -> [a]
filtero' p xs = foldr (\curr acc -> if (p curr) then curr:acc else acc) [] xs 

In Bezug auf Karte könnte man auch schreiben als

-- Example 4: map
mapo :: (a -> b) -> [a] -> [b]
mapo f []   = []
mapo f (x:xs) = x `op` (mapo f xs)
  where
    op = (\curr acc -> (f curr) : acc)

die daher wie folgt umgeschrieben werden kann foldr . Zum Beispiel, um jede Zahl in einer Liste mit zwei zu multiplizieren:

let f = (* 2) in foldr (\curr acc -> (f curr) : acc) [] [1,2,3,4]

Also, Karte kann geschrieben werden mit foldr wie wir gesehen haben:

-- Solution 2: map using foldr
mapo' :: (a -> b) -> [a] -> [b]
mapo' f xs = foldr (\curr acc -> (f curr) : acc) [] xs

Answer 2

Ihre Lösung funktioniert fast). Das Problem ist, dass du zwei unterschiedliche Bindungen für x in deinen beiden Funktionen hast (innerhalb des Patternmatching und innerhalb deines Lambda-Ausdrucks), daher verlierst du den Überblick über das erste Element.

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

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

Das sollte genügen :). Außerdem: Sie können Ihre Funktionen ganz einfach im punktfreien Stil schreiben.

Answer 3

*Main> :{
*Main| map' :: (a -> b) -> [a] -> [b]
*Main| map' = \f -> \ys -> (foldr (\x -> \acc -> f x:acc) [] ys)
*Main| :}
*Main> map' (^2) [1..10]
[1,4,9,16,25,36,49,64,81,100]

*Main> :{
*Main| filter' :: (a -> Bool) -> [a] -> [a]
*Main| filter' = \p -> \ys -> (foldr (\x -> \acc -> if p x then x:acc else acc) [] ys)
*Main| :}
*Main> filter' (>10) [1..100]

In den obigen Ausschnitten acc bezieht sich auf den Akkumulator und x bezieht sich auf das letzte Element.

Answer 4

In Ihren Lambda-Ausdrücken ist alles korrekt. Das Problem ist, dass Ihnen das erste Element in der Liste fehlt. Wenn Sie versuchen,

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

dann sollten Sie das erste Element nicht mehr übersehen. Die gleiche Logik gilt für filter .

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