Início / coding / Perguntas / 79551454
Accepted
G. Rodrigues
Asked: 2025-04-03 03:52:50 +0800 CST

Compreendendo a falta de preguiça Alternative.man

  • 772

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")
haskell

1 respostas

  1. Best Answer

    A preguiça não traz o que você quer neste caso.

    Em poucas palavras, considere este cenário:

    case run (many one) "0123" of
   Right (x,y) -> ... -- * --
   Left _ -> someErrorHandling

    No --*--ponto, você está de alguma forma esperando que, se você consumir os primeiros N elementos de x(conforme seu take 2), então você encontrará os elementos não consumidos dentro de y. Mas isso não é realmente possível.

    Concretamente, seus take 2 <$> ...atos são os seguintes:

    case run (many one) "0123" of
   Right (x, y) -> Right (take 2 x, y)
   Left e -> Left e

    mas isso deixará yinalterado. Você não pode alterar a entrada não consumida ypor meio de <$>.

    Só para enfatizar o ponto, pense neste exemplo artificial:

    case run (many one) "0123" of
   Right (x, y) -> Right (take (length y) x, y)
   Left e -> Left e

    Aqui a quantidade de dígitos "tomados" depende de quantos foram deixados sem consumo. Isso não pode ser alcançado com <$>, mas ainda é possível implementar isso no nível mais baixo.

    O tipo de analisador que você tem em mente, onde você pode controlar quanta entrada é realmente analisada de "fora", pode ser realizável, mas exigiria uma representação de analisador completamente diferente.

    • 4

relate perguntas