svp .. map & filter

[vita fleur]

je veux définir map et filter en utilisant foldr et les fonctions prédéfinits ... pour foldr ça y est j l termine .. mais avec les fonctions prédéfinits j n peux pas le faire .. pouvez vous m'aider svp ... j n'arrive pas a trouver exactement ces fonctions que je les utilise !!!


merci d'avance

[Ptival]

Le rose de tes messages me pique presque autant les yeux que ton respect de l'orthographe.

Ceci étant mentionné, tu souhaites donc définir map et filter sans utiliser de fold. La réponse est : laisse-toi guider par les types !

Code :

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

Tu as une fonction qui transforme un a en b, une liste de a, et tu veux en faire une liste de b. Tu vas devoir traiter chaque élément de la liste un par un. Pour cela, tu vas utiliser une définition avec un filtrage de motifs :

Code :

1
2
map f [] = error "TODO"
map f (a::as) = error "TODO"

Il te reste à remplir le code.
Sur la première ligne, tu reçois une liste vide, et tu dois retourner une liste de b, que comptes-tu faire ?
Pour la seconde ligne tu reçois une liste contenant un a et une sous-liste de a. Tu vas devoir effectuer un appel récursif de la fonction map. J'espère que tu sais ce que c'est.

Pour filter il en va de même, on regarde le type :

Code :

filter :: (a -> Bool) -> [a] -> [a]

Tu procèdes encore une fois par récursivité et analyse de cas :

Code :

1
2
filter cond [] = error "TODO"
filter cond (a::as) = error "TODO"

Ici, dans le cas du bas, tu vas devoir effectuer un test, et renvoyer un résultat différent selon ce que le test retourne.
Un choix est d'utiliser une structure de la forme :

Code :

if ... then ... else

Un autre choix est d'utiliser une garde, ce qui peut être plus simple à lire :

Code :

1
2
3
filter cond [] = error "TODO"
filter cond (a::as) | ... = error "TODO"
filter cond (a::as) | otherwise = error "TODO"

Si tu ne connais pas les gardes, ce n'est pas grave, tu devrais quand même pouvoir écrire filter avec le patron sans gardes.

[Yo Eight]

J'ai sans doute mal compris, mais il me semble qu'elle veut exprimer map et filter avec foldr et les fonctions dans Prelude.

J'avoue que ce n'est pas très clair.

en tout cas map peut être implémentée ainsi:

Code Haskell :

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

filter n'est pas bien différent, il faut juste implémenté la décision en fonction du résultat retourné par le prédicat.

[Ptival]

Yo Eight : Effectivement, en relisant la question j'ai l'impression d'avoir répondu à côté de la plaque.

Le "pour foldr ça y est j l termine" m'a induit en erreur...

L'idée pour réussir ce genre d'exercice, c'est de voir foldr comme :

Code :

1
2
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Et de juste réfléchir à "comment remplacer f et z".

Par exemple :

Code :

1
2
3
4
5
6
7
Pour f = (:), z = [],
x1 `f` (x2 `f` ... (xn `f` z)...)
devient
x1 : (x2 : ... (xn : [])...)
donc
foldr (:) [] est égal à "id"

Code :

1
2
3
4
5
6
7
Pour f = (+), z = 0,
x1 `f` (x2 `f` ... (xn `f` z)...)
devient
x1 + (x2 + ... (xn + 0)...)
donc
foldr (+) 0 est égal à "sum"

etc.

Pour map et filter, il faut utiliser une fonction f un peu plus évoluée.
map transforme son premier argument avant de le mettre en tête de liste.
filter regarde son premier argument et décide s'il le met en tête de liste ou pas.

On comprend aussi le type de foldr :

Code :

1
2
foldr :: (a -> b -> b) -> b -> [a] -> b

Le troisième paramètre est la liste à traiter.
Le deuxième paramètre est un "accumulateur" : c'est lui qui va être altéré par le traitement de chaque élément de la liste à traiter, et qui, une fois la liste complètement traitée, fera office de résultat final.
Le premier paramètre est la fonction de traitement : elle prend un élément, et un accumulateur, et retourne l'accumulateur après traitement de l'élément.

Utiliser un fold, ça revient donc à se demander :
- quelle liste je traite ? (-> définit a)
- quel est le type de ce que je veux calculer ? (-> définit b)
- pour un élément de type a, et un résultat partiel de type b, comment est-ce que je transforme le résultat partiel pour obtenir un nouveau résultat ? (-> définit f :: a -> b -> b)
- quel est la valeur initiale / le résultat du traitement pour une liste vide ? (-> définit z :: b)

Pour plus de détails, n'hésite pas à lire ceci.

[Yo Eight]

Tu es beaucoup plus pédagogue