Uma biblioteca de análise sintática mínima absoluta poderia ser:
{- | Input error type. -}
data InputError = InputError
deriving (Eq, Show)
instance Semigroup InputError where
(<>) _ _ = InputError
instance Monoid InputError where
mempty = InputError
{- | The parsing monad. -}
newtype Parser s e a = Parser ([s] -> Either e (a, [s]))
deriving stock Functor
-- Instances.
instance Applicative (Parser s e) where
pure x = Parser $ \ xs -> pure (x, xs)
(<*>) p q = Parser $ \ xs -> do
(f, ys) <- run p xs
(x, zs) <- run q ys
pure (f x, zs)
instance Monad (Parser s e) where
(>>=) p h = Parser $ \ xs -> do
(x, ys) <- run p xs
run (h x) ys
instance Monoid e => Alternative (Parser s e) where
empty = Parser $ \ _ -> Left mempty
(<|>) p q = Parser $ \ xs ->
case run p xs of
r1@(Right _) -> r1
Left e1 ->
case run q xs of
r2@(Right _) -> r2
Left e2 -> Left $ e1 <> e2
{- | Primitive parser getting one element out of the stream. -}
one :: Parser s InputError s
one = Parser $ \ xs ->
case uncons xs of
Nothing -> Left InputError
Just p -> Right p
{- | Run the parser on input and return the results. -}
run :: Parser s e a -> [s] -> Either e (a, [s])
run (Parser p) = p
Isto compila (com linguagem GHC2021; tem que adicionar algumas importações). Carregando em ghci em cabal repl:
ghci> let p = take 2 <$> many one
ghci> run p "0123"
Right ("01","")
Isso significa que o analisador consumiu toda a entrada -- o que eu esperava ver era Right ("01", "23").
Então minha pergunta: onde a preguiça "quebra", por assim dizer, e há alguma maneira de restaurá-la? E por "restaurá-la" quero dizer fazer a implementação da instância de forma diferente para que manyseja tão preguiçosa quanto o esperado, porque se eu adicionar
{- | Implement lazy 'many' -}
atMostN :: Monoid e => Word -> Parser s e a -> Parser s e [a]
atMostN n p = go n
where
go 0 = pure []
go m = do
r <- optional p
case r of
Nothing -> pure []
Just x -> (x: ) <$> go (pred m)
E carrego no ghci, obtenho o esperado:
ghci> let q = atMostN 2 one
ghci> run q "0123"
Right ("01","23")