Comment définiriez-vous la carte et le filtre à l'aide de foldr en Haskell?

Pour votre première question, foldr a déjà un cas de la liste vide, de sorte que vous n'avez pas besoin et ne doit pas constituer un cas pour elle dans votre propre carte.

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

La même chose vaut pour filter'

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

Rien de mal avec vos expressions lambda, mais il ya quelque chose de mal avec votre définitions de filter' et map'. Dans les inconvénients cas (x:xs) vous mangez de la tête ( x ), puis de passer à la queue de foldr. Le foldr fonction peut ne jamais voir le premier élément que vous avez déjà mangé. 🙂

Alse noter que:

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

est équivalent (η-équivalent) à:

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

Dans vos définitions, vous faites la correspondance de modèle pour x:xs, ce qui signifie que, lorsque votre argument est [1,2,3,4], x est lié à 1 et xs est lié au reste de la liste: [2,3,4].

Ce que vous ne devriez pas faire est de simplement jeter x: partie. Ensuite, votre foldr sera de travailler sur la totalité de la liste.

De sorte que votre définitions devraient se présenter comme suit:

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

Une manière différente de penser à elle - foldr existe parce que le récursive modèle est souvent utilisé:

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

De prendre le produit de nombres, voire de l'inverser une liste semble structurellement très similaire à la précédente fonction récursive:

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

La structure dans les exemples ci-dessus ne se distingue de la valeur initiale (0 summa et [] pour reverso) avec l'opérateur entre la première valeur et l'appel récursif (+ summa et (\q qs -> qs ++ [q]) pour reverso). Donc la fonction de structure pour les exemples ci-dessus peut être considérée comme

-- 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

De voir que ce "générique" foo œuvres, nous pouvons maintenant réécrire reverso en utilisant foo et de le transmettre à l'opérateur, la valeur initiale, et la liste elle-même:

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

Donnons foo plus générique type de signature, de sorte que cela fonctionne pour d'autres problèmes se posent:

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

Maintenant, pour en revenir à votre question, nous pourrions écrire filtre comme suit:

-- 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)

Ce nouveau dispose d'une structure très similaire à la summa et reverso. Par conséquent, nous devrions être en mesure d'utiliser foo à la réécrire. Disons que nous voulons filtrer le même nombres de la liste [1,2,3,4]. Puis, de nouveau, nous passons foo l'opérateur (dans ce cas filterLogic), valeur initiale, et la liste elle-même. filterLogic dans cet exemple prend un p la fonction d'un prédicat, que nous aurons à définir pour l'appel:

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

foo en Haskell est appelé foldr. Nous avons donc réécrit filtre à l'aide de foldr.

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

Donc, filtre peut être écrit avec foldr comme nous l'avons vu:

-- 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 

Comme pour carte, on pourrait aussi l'écrire comme

-- 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)

qui, par conséquent, peut être réécrite en utilisant foldr. Par exemple, pour multiplier chaque nombre dans une liste en deux:

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

Donc, carte peut être écrit avec foldr comme nous l'avons vu:

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