Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Discussion: svp .. map & filter

  1. #1
    Invité de passage
    Femme Profil pro SourCe 'Of HOpe
    Étudiant
    Inscrit en
    septembre 2011
    Messages
    6
    Détails du profil
    Informations personnelles :
    Nom : Femme SourCe 'Of HOpe
    Localisation : Autre

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Biens de consommation

    Informations forums :
    Inscription : septembre 2011
    Messages : 6
    Points : 2
    Points
    2

    Par défaut svp .. map & filter

    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

  2. #2
    Membre actif Avatar de Ptival
    Homme Profil pro Valentin Robert
    Étudiant
    Inscrit en
    juin 2004
    Messages
    70
    Détails du profil
    Informations personnelles :
    Nom : Homme Valentin Robert
    Âge : 25
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2004
    Messages : 70
    Points : 168
    Points
    168

    Par défaut

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

  3. #3
    Membre éclairé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2009
    Messages
    98
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Finance

    Informations forums :
    Inscription : mai 2009
    Messages : 98
    Points : 304
    Points
    304

    Par défaut

    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.

  4. #4
    Membre actif Avatar de Ptival
    Homme Profil pro Valentin Robert
    Étudiant
    Inscrit en
    juin 2004
    Messages
    70
    Détails du profil
    Informations personnelles :
    Nom : Homme Valentin Robert
    Âge : 25
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2004
    Messages : 70
    Points : 168
    Points
    168

    Par défaut

    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.

  5. #5
    Membre éclairé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2009
    Messages
    98
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Finance

    Informations forums :
    Inscription : mai 2009
    Messages : 98
    Points : 304
    Points
    304

    Par défaut

    Tu es beaucoup plus pédagogue

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •