parser recursif programming haskell [Résolu]

[jjinkou2]

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.

[Chatanga]

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.

[jjinkou2]

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

[Chatanga]

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)

[jjinkou2]

effectivement c'est plus parlant.
merci.