Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5
  1. #1
    Invité de passage
    Inscrit en
    décembre 2010
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : décembre 2010
    Messages : 3
    Points : 1
    Points
    1

    Par défaut parser recursif programming haskell

    bonjour,
    je débute en haskell et j'ai acheté le livre "programming in haskkel".
    au chapitre sur les parsers il y a le code recursif sur les chaines dont je n'arrive pas a comprendre comment il se déroule.

    Voici le code

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    > char                          :: Char -> Parser Char
    > char x                        =  sat (== x)
    > 
    > string                        :: String -> Parser String
    > string []                     =  return []
    > string (x:xs)                 =  do char x
    >                                     string xs
    >                                     return (x:xs)
    
    > sat                           :: (Char -> Bool) -> Parser Char
    > sat p                         =  do x <- item
    >                                     if p x then return x else failure
    la suite est ici http://www.cs.nott.ac.uk/~gmh/Parsing.lhs


    comment le return (x:xs) est atteint?
    j’essaie de décomposer en étape l'exemple suivant:
    Code :
    1
    2
    parse (string "to") "topi"
    mais je ne vois pas comment le résultat aboutit a [("to","pi")].

    si quelqu'un peut dérouler l'exemple.

    Merci.

  2. #2
    Membre confirmé
    Avatar de Chatanga
    Inscrit en
    décembre 2005
    Messages
    184
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 184
    Points : 260
    Points
    260

    Par défaut

    Je n'ai pas lu le livre "Programming in Haskell", mais j'imagine qu'il doit introduire la notion de monade avant de détailler ce parseur. En tout cas, c'est un concept que tu devras apprendre à maîtriser pour profiter pleinement de ce langage. Si ton livre n'est pas assez clair sur ce sujet, tu peux aussi jeter un oeil sur la version en ligne de Real World Haskell (il y a d'ailleurs également un exemple de parseur dedans).

    En attendant, on peut se contenter de dire que les monades constituent un certain formalisme à adopter pour un type (et on l'adopte concrètement en faisant d'un type une instance de la classe Monad) permettant en échange de bénéficier d'un tas de facilités du langage, que ce soit en terme de syntaxe avec la notation 'do' ou de réutilisation de fonctions dédiées aux monades. Plus généralement, les monades sont la forme que prennent (assez) naturellement les types dans la programmation fonctionnelle de haut niveau (dans le sens fonction de fonction).

    Pour en revenir au sujet de ton message, voici comment tu pourrais réécrire la fonction string.

    Tout d'abord en "désugarisant" sa définition (la syntaxe 'do' au style impératif n'est que du sucre syntaxique) :
    Code :
    1
    2
    string2 (x:xs) =
        char x >> string xs >> return (x:xs)
    Puis en utilisant l'opérateur >>= explicitement défini pour Parser :
    Code :
    1
    2
    string3 (x:xs) =
        char x >>= \_ -> string xs >>= \_ -> return (x:xs)
    Et enfin en combinant manuellement les différentes fonctions chaînées par >>= :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    string4 (x:xs) =
        P (\inp -> case parse (char x) inp of
            []          -> []
            [(v,out)]   -> parse (f v) out) where
                f _ = P (\inp -> case parse (string xs) inp of
                    []          -> []
                    [(v,out)]   -> parse (g v) out) where
                        g _ = P (\inp -> [((x:xs),inp)])
    Cette dernière forme devrait t'aider à comprendre le déroulement du code. La forme originelle est évidemment plus compacte et élégante et, une fois les monades devenues une habitude, également plus claire.

  3. #3
    Invité de passage
    Inscrit en
    décembre 2010
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : décembre 2010
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    Merci pour la réponse.
    Bon j'ai encore du chemin pour comprendre le 3eme code.

    Dans le 2eme code (string3) mon erreur est d'oublier le type de String qui est String->Parser String

    aussi je suppose que le raisonnement cidessous est faux:

    String (xs) = String (y:ys) = char y >> string ys >> return (y:ys)


    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    string3 (x:xs) =
        char x >>= \_ -> string xs >>= \_ -> return (x:xs)
    string3b (x:xs) =
        char x >>= char y >>= \_ -> string ys >>= \_ -> return (y:ys)
    string3c (x:xs) =
        char x >>= char y >>= char z >>= \_ -> string zs >>= \_ -> return (z:zs)
    
    ...
    
    string3z (x:xs) = 
        char x >>= char y >>= char z >>= \_ ->... return ()

  4. #4
    Membre confirmé
    Avatar de Chatanga
    Inscrit en
    décembre 2005
    Messages
    184
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 184
    Points : 260
    Points
    260

    Par défaut

    Ton code sort des variables (y, z, etc.) de nulle part, ce qui t'induit ensuite en erreur :

    Code :
    1
    2
    3
    4
    5
    6
    string3 (x:xs) =
        char x >>= \_ -> string xs >>= \_ -> return (x:xs)
    string3b (x:y:xs) =
        char x >>= char y >>= \_ -> string ys >>= \_ -> return (x:y:ys)
    string3c (x:y:z:xs) =
        char x >>= char y >>= char z >>= \_ -> string zs >>= \_ -> return (x:y:z:zs)

  5. #5
    Invité de passage
    Inscrit en
    décembre 2010
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : décembre 2010
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    effectivement c'est plus parlant.
    merci.

+ Répondre à la discussion
Cette discussion est résolue.

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
  •