Entrada e saída e parsers com combinadores

getLine :: IO String representa uma ação de leitura, não a string que será lida. Já length "ana" é um cálculo puro que vale 3. O tipo IO permite sequenciar ações e passar os valores produzidos a funções puras. IO () é uma ação que devolve (); pode imprimir, como putStrLn, ou nem produzir interação observável, como pure ().

I/O com do

main :: IO ()
main = do
  putStrLn "Como te chamas?"
  nome <- getLine
  putStrLn ("Ola, " ++ nome ++ "!")

Cada linha do do corre por ordem; o bloco também pode conter definições puras com let. A seta <- corre a ação e dá nome ao resultado: nome fica com a string lida. Sem seta, como em putStrLn, o resultado é ignorado.

"Ola, " ++ nome ++ "!" é um cálculo puro; putStrLn cria a ação que o imprime. Separa os cálculos em funções puras e reserva o bloco do para ligar cada ação ao seu resultado.

Parsers como funções

Um parser consome um prefixo da entrada e devolve um valor e a entrada restante. Nesta representação, o construtor P guarda a função que faz esse trabalho:

newtype Parser a = P (String -> [(a, String)])

parse :: Parser a -> String -> [(a, String)]
parse (P p) = p

item :: Parser Char
item = P (\inp -> case inp of
                   []     -> []
                   (c:cs) -> [(c, cs)])

Ler item e nat passo a passo

parse item "abc" dá [('a',"bc")]; parse item "" dá []. A lista vazia representa falha. Nesta página, um sucesso tem exatamente um par. Embora o tipo permita mais resultados, os combinadores seguintes assumem este contrato determinístico.

Para ler "42x" com nat, seguimos os estados:

pure 1 tem sucesso sem consumir: parse (pure 1) "abc" dá [(1,"abc")]. fmap transforma só o valor. p >>= f usa o valor de p para escolher o parser seguinte, executado no resto. p +++ q tenta q na entrada original quando p falha. As definições tornam explícita essa passagem de estado:

import Data.Char (isDigit, isSpace)

instance Functor Parser where
  fmap f p = P (\inp -> case parse p inp of
                         []        -> []
                         [(v,out)] -> [(f v, out)])

instance Applicative Parser where
  pure v = P (\inp -> [(v, inp)])
  pf <*> px = P (\inp -> case parse pf inp of
                            []        -> []
                            [(f,out)] -> parse (fmap f px) out)

instance Monad Parser where
  p >>= f = P (\inp -> case parse p inp of
                         []        -> []
                         [(v,out)] -> parse (f v) out)

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = P (\inp -> case parse p inp of
                       []        -> parse q inp
                       [(v,out)] -> [(v,out)])

sat :: (Char -> Bool) -> Parser Char
sat pr = do c <- item
            if pr c then return c else P (const [])

digit :: Parser Char
digit = sat isDigit

many :: Parser a -> Parser [a]
many p = many1 p +++ return []

many1 :: Parser a -> Parser [a]
many1 p = do v  <- p
             vs <- many p
             return (v:vs)

nat :: Parser Int
nat = do xs <- many1 digit
         return (read xs)

space :: Parser ()
space = do many (sat isSpace)
           return ()

token :: Parser a -> Parser a
token p = do space
             v <- p
             space
             return v

symbol :: Char -> Parser Char
symbol c = token (sat (== c))

Functor aplica uma função ao resultado com fmap. Applicative fornece pure, sucesso sem consumir entrada, e <*>, sequência de um parser de funções com um parser de argumentos. Monad fornece >>=, que escolhe o parser seguinte a partir do valor acabado de ler, com return no mesmo papel que pure e o do assente em >>=. Cada combinador faz uma coisa pequena: sat testa um caráter, many repete zero ou mais vezes, token ignora espaços à volta. nat pressupõe que o número cabe em Int; para naturais arbitrariamente grandes, muda o resultado para Integer. A gramática seguinte compõe os combinadores para ler expressões:

expr :: Parser Int
expr = do t <- term
          (do symbol '+'
              e <- expr
              return (t + e)) +++ return t

term :: Parser Int
term = do f <- factor
          (do symbol '*'
              t <- term
              return (f * t)) +++ return f

factor :: Parser Int
factor = (do symbol '('
             e <- expr
             symbol ')'
             return e) +++ token nat

A precedência vive na estrutura: expr soma terms e term multiplica factors, por isso * liga mais que +.

Avalia parse expr "2+3*4": o term lê 2 e para no +, e o expr soma 2 com o expr de "3*4", que multiplica 3 por 4, dando [(14, "")]; parse expr "(2+3)*4" dá [(20, "")], com os parênteses a forçar a soma primeiro.

import Data.Char (isDigit, isSpace)

newtype Parser a = P (String -> [(a, String)])

parse :: Parser a -> String -> [(a, String)]
parse (P p) = p

item :: Parser Char
item = P (\inp -> case inp of
                   []     -> []
                   (c:cs) -> [(c, cs)])

instance Functor Parser where
  fmap f p = P (\inp -> case parse p inp of
                         []        -> []
                         [(v,out)] -> [(f v, out)])

instance Applicative Parser where
  pure v = P (\inp -> [(v, inp)])
  pf <*> px = P (\inp -> case parse pf inp of
                            []        -> []
                            [(f,out)] -> parse (fmap f px) out)

instance Monad Parser where
  p >>= f = P (\inp -> case parse p inp of
                         []        -> []
                         [(v,out)] -> parse (f v) out)

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = P (\inp -> case parse p inp of
                       []        -> parse q inp
                       [(v,out)] -> [(v,out)])

sat :: (Char -> Bool) -> Parser Char
sat pr = do c <- item
            if pr c then return c else P (const [])

digit :: Parser Char
digit = sat isDigit

many :: Parser a -> Parser [a]
many p = many1 p +++ return []

many1 :: Parser a -> Parser [a]
many1 p = do v  <- p
             vs <- many p
             return (v:vs)

nat :: Parser Int
nat = do xs <- many1 digit
         return (read xs)

space :: Parser ()
space = do many (sat isSpace)
           return ()

token :: Parser a -> Parser a
token p = do space
             v <- p
             space
             return v

symbol :: Char -> Parser Char
symbol c = token (sat (== c))

expr :: Parser Int
expr = do t <- term
          (do symbol '+'
              e <- expr
              return (t + e)) +++ return t

term :: Parser Int
term = do f <- factor
          (do symbol '*'
              t <- term
              return (f * t)) +++ return f

factor :: Parser Int
factor = (do symbol '('
             e <- expr
             symbol ')'
             return e) +++ token nat

completa :: Parser a -> String -> Maybe a
completa p texto = case parse (token p) texto of
  [(valor, "")] -> Just valor
  _ -> Nothing

main :: IO ()
main = do
  print (parse nat "42x")
  print (parse (many1 digit) "7+8")
  print (parse expr "2+3*4")
  print (parse expr "(2+3)*4")
  print (parse expr "2+")
  print (map (completa expr) [" 2 + 3*4 ", "2+", "2+3x", "(2+3"])

Alternativa, falha e entrada restante

O +++ definido nesta página tenta q na entrada original quando p devolve []. Por isso há retrocesso mesmo que p tenha consumido caracteres antes de falhar. Este contrato difere de parsers que guardam explicitamente se a falha aconteceu depois de consumir entrada.

Um parser não determinístico pode devolver vários pares. Nesse contrato, os casos [(v,out)] destas instâncias seriam incompletos: a sequência teria de combinar todos os resultados de cada etapa, em vez de escolher um só.

parse expr "2+3x" dá [(5,"x")]. A alternativa também permite que parse expr "2+" recue para o prefixo 2 e deixe "+". Uma aplicação que exige uma expressão inteira deve aceitar apenas [(v,"")], depois de consumir espaços:

completa :: Parser a -> String -> Maybe a
completa p texto = case parse (token p) texto of
  [(valor, "")] -> Just valor
  _ -> Nothing

completa expr " 2 + 3*4 " dá Just 14; "2+", "2+3x" e "(2+3" dão Nothing, porque sucesso do prefixo não valida todo o ficheiro.

Precedência e associatividade

A gramática expr = term '+' expr | term dá prioridade à multiplicação, mas associa a soma à direita, ou seja como a adição de inteiros é associativa, os resultados não revelam essa escolha. Se trocares + por -, 8-3-1 passa a 8-(3-1)=6. A associatividade usual à esquerda daria (8-3)-1=4. Uma solução é ler um primeiro termo, ler pares operador-termo e acumular pela esquerda.

Recursão à esquerda, como expr = expr '+' term | term, não serve diretamente num parser recursivo descendente: chama expr de novo sem consumir nada. Reformula a gramática com um acumulador ou um combinador de cadeias.

Sequenciar ações sem confundir valores

getLine :: IO String, enquanto length :: [a] -> Int. Não podes escrever length getLine: uma ação não é a string que vai produzir. Em do, linha <- getLine liga o valor produzido; let n = length linha dá nome a um cálculo puro e não usa <-. return n cria uma ação que devolve n; não interrompe as ações seguintes como um return imperativo.

Um modelo da sequência é acao >>= continuacao, com continuacao :: a -> IO b se acao :: IO a. O resultado de IO fica dentro do programa de efeitos; uma função pura pode receber o valor lido, mas não extrair sozinha um valor de uma ação arbitrária.