J'essaye d'implémenter mon propre analyseur applicatif, voici le code que j'utilise:
{-# LANGUAGE ApplicativeDo, LambdaCase #-}
module Parser where
-- Implementation of an Applicative Parser
import Data.Char
import Control.Applicative (some, many, empty, (<*>), (<$>), (<|>), Alternative)
data Parser a = Parser { runParser :: String -> [(a, String)] }
instance Functor Parser where
-- fmap :: (a -> b) -> (Parser a -> Parser b)
fmap f (Parser p) = Parser (\s -> [(f a, s') | (a,s') <- p s])
instance Applicative Parser where
-- pure :: a -> Parser a
-- <*> :: Parser (a -> b) -> Parser a -> Parser b
pure x = Parser $ \s -> [(x, s)]
(Parser pf) <*> (Parser p) = Parser $ \s ->
[(f a, s'') | (f, s') <- pf s, (a, s'') <- p s']
instance Alternative Parser where
-- empty :: Parser a
-- <|> :: Parser a -> Parser a -> Parser a
empty = Parser $ \_s -> []
(Parser p1) <|> (Parser p2) = Parser $ \s ->
case p1 s of [] -> p2 s
xs -> xs
char :: Char -> Parser Char
char c = Parser $ \case (c':cs) | c == c' -> [(c,cs)] ; _ -> []
main = print $ runParser (some $ char 'A') "AAA"
Quand je l'exécute, il reste bloqué et ne revient jamais. Après avoir creusé le problème, j'ai identifié la cause première de ma mise en œuvre de la <|>méthode. Si j'utilise l'implémentation suivante, tout se passe comme prévu:
instance Alternative Parser where
empty = Parser $ \_s -> []
p1 <|> p2 = Parser $ \s ->
case runParser p1 s of [] -> runParser p2 s
xs -> xs
Ces deux implémentations sont, à mon avis, assez équivalentes. Ce que je suppose, c'est que cela peut avoir quelque chose à voir avec le système d'évaluation paresseux de Haskell. Quelqu'un peut-il expliquer ce qui se passe?
Fait "star": dans votre mise en œuvre de (<*>):
Parser p1 <*> Parser p2 = ...
... nous devons calculer suffisamment pour savoir que les deux arguments sont en fait des applications du Parserconstructeur à quelque chose avant de pouvoir passer au côté droit de l'équation.
Fait "pipe strict": dans cette implémentation:
Parser p1 <|> Parser p2 = ...
... nous devons calculer suffisamment pour savoir que les deux analyseurs sont en fait des applications du Parserconstructeur à quelque chose avant de pouvoir passer au côté droit du signe égal.
Fait "pipe paresseux": dans cette implémentation:
p1 <|> p2 = Parser $ ...
... nous pouvons passer à la partie droite du signe égal sans faire de calcul sur p1ou p2.
Ceci est important, car:
some v = some_v where
some_v = pure (:) <*> v <*> (some_v <|> pure [])
Prenons votre première implémentation, celle dont nous connaissons le fait "pipe strict". Nous voulons savoir si some_vc'est une application de Parserquelque chose. Merci à fait « star », il faut donc savoir si pure (:), vet some_v <|> pure []sont des applications de Parserquelque chose. Pour connaître ce dernier, en fait "pipe strict", il faut savoir si some_vet pure []sont des applications de Parserquelque chose. Oups! Nous venons de montrer que pour savoir s'il some_vs'agit d'une application de Parserà quelque chose, nous devons savoir si some_vest une application de Parserà quelque chose - une boucle infinie!
D'un autre côté, avec votre deuxième implémentation, pour vérifier si some_vc'est a Parser _, nous devons toujours vérifier pure (:), vet some_v <|> pure [], mais grâce au fait "pipe paresseux", c'est tout ce que nous devons vérifier - nous pouvons être sûrs que some_v <|> pure []c'est un Parser _sans premier vérifier récursivement que some_vet pure []sont.
(Et ensuite, vous en apprendrez davantage sur newtype- et serez encore une fois confus lorsque le passage de dataà newtypefait que les deux implémentations fonctionnent!)
Cet article est collecté sur Internet, veuillez indiquer la source lors de la réimpression.
En cas d'infraction, veuillez [email protected] Supprimer.
laisse moi dire quelques mots