Trago a atenção de vocês para a tradução de um maravilhoso artigo de Justin Le. Em seu blog Code, esse autor fala em uma linguagem bastante fácil sobre a essência matemática de soluções funcionais bonitas e elegantes para problemas práticos. Este artigo examina detalhadamente um exemplo de como transferir imediatamente a estrutura matemática que os dados em uma área de assunto formam para um sistema de tipos de programas, como Gerald e Sassman escreveram "automaticamente", levar a uma solução funcional.

O código mostrado na figura é uma implementação extensível e independente do analisador de expressões regulares, gravada do zero. Classe superior, tipo mágico real!

Hoje, implementamos expressões regulares e analisadores de aplicativos (no espírito da biblioteca regex-application ) usando estruturas algébricas livres! Estruturas livres são uma das minhas ferramentas favoritas em Haskell e escrevi anteriormente sobre grupos livres , variações sobre o tópico de mônadas livres e o funcionamento aplicador “gratuito” em monoides .

Expressões regulares (e analisadores para eles) são onipresentes em programação e ciência da computação, por isso espero que, demonstrando como são fáceis de implementar usando estruturas livres, ajudarei o leitor a apreciar os méritos dessa abordagem sem medo de se perder em detalhes desnecessários.

Todo o código do artigo está disponível online como um "executável de pilha". Se você executá-lo ( ./regexp.hs ), a sessão do GHCi começará com todas as definições, assim você terá a oportunidade de brincar com as funções e seus tipos.

Este artigo será totalmente compreensível para o "iniciante avançado" ou o "especialista iniciante" em Haskell. Requer conhecimento dos conceitos básicos de uma linguagem: correspondência de padrões, tipos de dados algébricos e abstrações como monóides, functores e notações.

Línguas regulares

Uma expressão regular é uma maneira de definir uma linguagem regular. Formalmente, essa expressão é construída de três elementos básicos:

1. Um conjunto vazio é um elemento que não é mapeado para nada.
2. Uma sequência vazia é um elemento neutro que corresponde trivialmente a uma sequência vazia.
3. Um literal é um símbolo que corresponde a si mesmo. Muito de um elemento.

E também de três operações:

1. Concatenação: RS , sequência de expressões. O produto de conjuntos (cartesiano).
2. Alternativa: R|S , escolha entre expressões. A união de conjuntos.
3. Estrela da cunha: R* , repetição de uma expressão um número arbitrário de vezes (incluindo zero).

E isso é tudo o que compõe expressões regulares, nem mais nem menos. A partir desses componentes básicos, você pode construir todas as outras operações conhecidas em expressões regulares - por exemplo, a+ pode ser expresso como aa* e categorias como \w podem ser representadas como uma alternativa aos caracteres adequados.

Função alternativa

Quando você olha para a estrutura das expressões regulares, isso não parece familiar? Isso me lembra muito a classe do tipo Alternative . Se um functor pertence a essa classe, isso significa que o seguinte é definido para ele:

1. Um elemento vazio correspondente a falha ou erro de cálculo.
2. pure x - um único elemento (da classe Applicative ).
3. Operação <*> , organizando cálculos seqüenciais.
4. Operação <|> , organizando cálculos alternativos.
5. A função many é a operação de repetir cálculos zero ou mais vezes.

Tudo isso é muito parecido com a construção de uma linguagem comum, certo? Talvez o functor alternativo seja quase o que precisamos, a única coisa que falta é o primitivo correspondente ao caractere literal.

Qualquer pessoa iniciante na classe Alternative pode encontrar uma boa introdução à Typeclassopedia . Porém, na estrutura de nosso artigo, essa classe representa simplesmente um “monóide duplo” com duas maneiras de combinar <*> e <|> , que, em certo sentido, podem ser comparadas com as operações * e + para números. Em geral, para determinar um functor alternativo, os cinco pontos acima e algumas leis adicionais de comutatividade e distributividade são suficientes.

 (<*>) :: Applicative f => f (a -> b) -> fa -> fb 

 (<*) :: Applicative f => fa -> fb -> fa (*>) :: Applicative f => fa -> fb -> fb 

Assim, podemos considerar expressões regulares como um functor alternativo, além de uma primitiva para um caractere literal. Mas, há outra maneira de vê-los, e isso nos leva diretamente a estruturas livres. Em vez do "functor alternativo com literais", podemos transformar o literal em uma instância da classe Alternative .

Liberdade

Vamos escrever assim. Digite para literal primitivo:

 data Prim a = Prim Char a deriving Functor 

Observe que, como trabalhamos com functores (aplicativo, alternativo), então com todas as nossas expressões regulares um certo "resultado" será associado. Isso ocorre porque, ao definir uma instância para as classes Functor , Applicative e Alternative , devemos ter um tipo de parâmetro.

Por um lado, você pode ignorar esse tipo, mas, por outro lado, deve usar esse valor como resultado da correspondência com uma expressão regular, como é feito em aplicativos industriais que trabalham com expressões regulares.

No nosso caso, Prim 'a' 1 :: Prim Int representará uma primitiva que mapeia o caractere 'a' e é imediatamente interpretada, resultando em uma unidade.

Bem, agora ... vamos dar ao nosso primitivo a estrutura matemática desejada usando o functor alternativo free biblioteca free :

 import Control.Alternative.Free type RegExp = Alt Prim 

Isso é tudo! Este é o nosso tipo completo de expressões regulares! Tendo declarado o tipo Alt uma instância da classe Functor , obtivemos todas as operações das classes Applicative e Alternative , pois nesse caso existem instâncias de Applicative (Alt f) e Alternative (Alt f) . Agora temos:

• Conjunto vazio trivial - empty da classe Alternative
• String vazia - pure da classe Applicative
• Caráter literal - Prim
• Concatenação - <*> da classe Applicative
• Alternativa - <|> da classe Alternative
• Kleene Star - many da classe Alternative

E tudo isso nos tornamos completamente "gratuitos", ou seja, "de graça"!

Essencialmente, uma estrutura livre nos fornece automaticamente apenas uma abstração para o tipo base e nada mais. Mas expressões regulares, por si só, também representam apenas uma estrutura: elementos básicos e um conjunto de operações, nem mais nem menos, de modo que o functor alternativo gratuito nos fornece exatamente o que precisamos. Não mais, mas não menos.

Depois de adicionar algumas funções convenientes do wrapper ... o trabalho no tipo está completo!

 -- | charAs:   ,    charAs :: Char -> a -> RegExp a charAs cx = liftAlt (Prim cx) -- liftAlt :: fa -> Alt fa   --   Prim   RegExp -- | char:         char :: Char -> RegExp Char char c = charAs cc -- | string:         string :: String -> RegExp String string = traverse char -- , ? 

Exemplos

Bem, vamos tentar? Vamos construir a expressão (a|b)(cd)*e , que retorna, no caso de uma correspondência bem-sucedida, o tipo de unidade () :

 testRegExp_ :: RegExp () testRegExp_ = void $ (char 'a' <|> char 'b') *> many (string "cd") *> char 'e' 

A função void :: Functor f => fa -> f () do pacote Data.Functor descarta o resultado, nós a usamos, uma vez que estamos interessados ​​apenas no sucesso da comparação. Mas os operadores <|> , *> e many são usados ​​por nós exatamente como é assumido ao concatenar ou escolher uma das opções.

Aqui está um exemplo interessante e mais complicado: vamos definir a mesma expressão regular, mas agora, como resultado da correspondência, calculamos o número de repetições do cd substring.

 testRegExp :: RegExp Int testRegExp = (char 'a' <|> char 'b') *> (length <$> many (string "cd")) <* char 'e' 

Há uma sutileza na operação dos operadores *> e <* : as setas indicam o resultado que deve ser salvo. E como many (string "cd") :: RegExp [String] retorna uma lista de elementos repetidos, podemos, permanecendo dentro do functor, calcular o tamanho dessa lista obtendo o número de repetições.

Além disso, a -XApplicativeDo compilador GHC -XApplicativeDo permite escrever nossa expressão usando do-notation, que provavelmente é mais fácil de entender:

 testRegExpDo :: RegExp Int testRegExpDo = do char 'a' <|> char 'b' cds <- many (string "cd") char 'e' pure (length cds) 

Tudo isso é semelhante à maneira como “capturamos” o resultado da análise de uma string usando uma expressão regular, obtendo acesso a ela. Aqui está um exemplo em Ruby:

 irb> /(a|b)((cd)*)e/.match("acdcdcdcde")[2] => "cdcdcdcd" 

a única diferença é que adicionamos algum pós-processamento para calcular o número de repetições.

Aqui está outro \d regular conveniente que corresponde a um número de 0 a 9 e retorna um número:

 digit :: RegExp Int digit = asum [ charAs (intToDigit i) i | i <- [0..9] ] 

Aqui, a função asum do pacote Control.Applicative.Alternative representa uma seleção dos itens da lista asum [x,y,z] = x <|> y <|> z , e a função intToDigit definida no pacote Data.Char . E, novamente, podemos criar coisas bastante elegantes, por exemplo, a expressão \[\d\] , correspondente ao número entre colchetes:

 bracketDigit :: RegExp Int bracketDigit = char '[' *> digit <* char ']' 

Análise

Bem, tudo o que fizemos foi descrever o tipo de dados para um literal com concatenação, seleção e repetição. Ótimo! Mas o que realmente precisamos é combinar uma string com uma expressão regular, certo? Como um functor alternativo gratuito pode nos ajudar com isso? De fato, isso ajudará bastante. Vejamos duas maneiras de fazer isso!

Descarregar o functor alternativo

O que é liberdade?

A maneira canônica de usar uma estrutura livre é dobrá-la em uma estrutura de concreto usando álgebra adequada. Por exemplo, a foldMap transforma um monóide livre (lista) no valor de qualquer instância da classe Monoid :

 foldMap :: Monoid m => (a -> m) -> ([a] -> m) 

A função foldMap transforma a transformação a -> m na transformação [a] -> m (ou FreeMonoid a -> m ), com um monóide específico m . A idéia geral é que o uso de uma estrutura livre permita que você adie seu uso específico "para mais tarde", separando o tempo de criação e o tempo de uso da estrutura.

Por exemplo, podemos construir um monóide livre a partir de números:

 -- |  "" `Int`     `Int`,  `liftAlt`. liftFM :: Int -> [Int] liftFM x = [x] myMon :: [Int] myMon = liftFM 1 <> liftFM 2 <> liftFM 3 <> liftFM 4 

E agora podemos decidir como queremos interpretar a operação <> :
Talvez esta adição?

 ghci> foldMap Sum myMon Sum 10 -- 1 + 2 + 3 + 4 

Ou multiplicação?

 ghci> foldMap Product myMon Product 24 -- 1 * 2 * 3 * 4 

Ou talvez o cálculo do número máximo?

 ghci> foldMap Max myMon Max 4 -- 1 `max` 2 `max` 3 `max` 4 

A idéia é adiar a seleção de um monóide específico, criando primeiro uma coleção gratuita de números 1, 2, 3 e 4. Um monóide livre sobre números determina a estrutura acima deles de que você precisa, nem mais nem menos. Para usar o foldMap especificamos "como perceber o tipo de base" passando o operador <> para um monóide específico.

Interpretação em um Functor de State

Na prática, obter um resultado de uma estrutura livre consiste em encontrar (ou criar) um functor adequado que nos forneça o comportamento desejado. No nosso caso, temos a sorte de haver uma implementação específica da classe Alternative que funciona exatamente como precisamos: StateT String Maybe .

O produto <*> para este functor consiste em organizar uma sequência de alterações de estado. No nosso caso, no estado, consideraremos o restante da string sendo analisada, para que a análise sequencial seja a melhor correspondência para a operação <*> .

E sua soma <|> funciona como retorno, uma pesquisa com retorno à alternativa em caso de falha. Ele retém o estado desde a última execução bem-sucedida da análise e retorna a ele se a alternativa for selecionada sem êxito. Esse é exatamente o comportamento que esperamos da expressão R|S

Finalmente, uma transformação natural para um functor alternativo gratuito é chamada de runAlt :

 runAlt :: Alternative f => (forall b. pb -> fb) -> Alt pa -> fa 

Ou, para o tipo RegExp:

 runAlt :: Alternative f => (forall b. Prim b -> fb) -> RegExp a -> fa 

Se você não estiver familiarizado com os tipos RankN (com forall b. Construction), poderá ver uma boa introdução aqui . O ponto aqui é que você precisa fornecer uma função runAlt que funcione com Prim b para absolutamente qualquer b , e não de qualquer tipo específico, como Int e Bool , por exemplo. Ou seja, como no foldMap precisamos apenas especificar o que fazer com o tipo base. No nosso caso, responda à pergunta: "O que precisa ser feito com o tipo Prim ?"

 processPrim :: Prim a -> StateT String Maybe a processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

Esta é uma interpretação de Prim como uma ação no contexto da StateT String Maybe , onde o estado é uma string StateT String Maybe . Deixe-me lembrá-lo de que Prim contém informações sobre o caractere correspondente c e sua interpretação na forma de algum valor de x . Prim processamento do Prim consiste nas seguintes etapas:

• Usando get estado (ainda não analisamos parte da string) e imediatamente imprimimos seu primeiro caractere e o restante. Se a linha estiver vazia, uma alternativa retornará. ( O transformador StateT atua dentro do functor Maybe, e se for impossível corresponder ao padrão no lado direito do operador <- dentro do bloco do, os cálculos terminam com o resultado empty , ou seja, Nothing . Approx. Trans. ).
• Usamos a expressão de guarda para combinar o caractere atual com o caractere especificado. Em caso de falha, o empty retornado e passamos para a opção alternativa.
• Mudamos o estado substituindo a string analisada por sua “cauda”, pois nesse momento o caractere atual já pode ser considerado analisado com êxito.
• Retornamos o que o primitivo Prim deve retornar.

Você já pode usar esta função para mapear RegEx para um prefixo de seqüência de caracteres. Para fazer isso, é necessário iniciar os cálculos usando runAlt e runStateT , passando a string analisada para a última função como argumento:

 matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) 

Isso é tudo! Vamos ver como nossa primeira solução funciona:

 ghci> matchPrefix testRegexp_ "acdcdcde" Just () ghci> matchPrefix testRegexp_ "acdcdcdx" Nothing ghci> matchPrefix testRegexp "acdcdcde" Just 3 ghci> matchPrefix testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchPrefix digit "9" Just 9 ghci> matchPrefix bracketDigit "[2]" Just 2 ghci> matchPrefix (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchPrefix (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

Espera, o que foi aquilo?

Parece que tudo aconteceu um pouco mais rápido do que o esperado. Um minuto atrás, escrevemos o nosso primitivo, e depois novamente! e o analisador de trabalho está pronto. Aqui, de fato, todo o código-chave, algumas linhas em Haskell:

 import Control.Monad.Trans.State (evalStateT, put, get) import Control.Alternative.Free (runAlt, Alt) import Control.Applicative import Control.Monad (guard) data Prim a = Prim Char a deriving Functor type RegExp = Alt Prim matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) where processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

E temos um analisador de expressões regulares totalmente funcional? O que aconteceu

Lembre-se de que, em um alto nível de abstração, o Alt Prim já contém pure , empty , Prim , <*> , <|> e many em sua estrutura (há uma sutileza desagradável com esse operador, mas mais sobre isso posteriormente). O que o runAlt faz é usar o comportamento de um functor alternativo específico (no nosso caso, StateT String Maybe ) para controlar o comportamento dos operadores pure , empty , <*> , <|> e de many operadores. No entanto, o StateT não possui um operador processPrim semelhante ao Prim e, para isso, precisamos escrever processPrim .

Portanto, para o tipo Prim , a função runAlt usa runAlt e, para pure , empty , <*> , <|> e many , uma instância adequada da classe Alternative é usada. Assim, 83% do trabalho é feito para nós pelo functor StateT , e os 17% restantes são feitos pelo StateT . Na verdade, isso é um pouco decepcionante. Alguém pode perguntar: por que foi necessário começar com o wrapper Alt ? Por que não definir imediatamente o tipo RegExp = StateT String Maybe e o apropriado primitivo char :: Char -> StateT String Maybe Char ? Se tudo é feito no StateT StateT, por que se preocupar com o Alt - um functor alternativo gratuito?

Alt principal vantagem Alt sobre o StateT é que o StateT é ... uma ferramenta bastante poderosa. Mas, de fato, ele é poderoso, ao ponto do absurdo. Ele pode ser usado para representar um grande número dos mais diversos cálculos e estruturas e, desagradável, é fácil imaginar algo que não é uma expressão regular. Digamos que algo básico como put "hello" :: StateT String Maybe () não corresponde a nenhuma expressão regular válida, mas é do mesmo tipo que RegExp () . Assim, enquanto dizemos que Alt Prim corresponde a uma expressão regular, não mais, mas não menos, não podemos dizer o mesmo com StateT String Maybe . O tipo Alt Prim é a representação perfeita de uma expressão regular. Tudo o que pode ser expresso com sua ajuda é uma expressão regular, mas qualquer coisa que não seja essa expressão não pode ser expressa com sua ajuda. Aqui, no entanto, também existem algumas sutilezas desagradáveis ​​associadas à preguiça de Haskell, mais sobre isso mais tarde.

Aqui podemos considerar StateT apenas como um contexto usado para um
interpretações de expressões regulares - como um analisador. Mas você pode imaginar outras maneiras de usar o RegExp . Por exemplo, podemos precisar de sua representação textual, que é o que StateT não permitirá.

Não podemos dizer que StateT String Maybe é uma expressão regular, apenas que este functor pode representar um analisador baseado em gramáticas regulares. Mas sobre Alt Prim podemos dizer com certeza que essa é uma expressão regular ( como dizem os matemáticos, eles são iguais ao isomorfismo, aproximadamente Trans. ).

Uso direto da estrutura livre

Tudo isso, é claro, é muito bom, mas e se não queremos mudar 83% do trabalho para codificar um tipo que foi escrito por alguém para nós. É possível usar a estrutura Alt gratuita diretamente para escrever um analisador? Esta pergunta é semelhante a esta: como escrever uma função que processa listas (combinando construtores (:) e [] ) em vez de usar apenas foldMap ? Como operar diretamente com essa estrutura em vez de delegar o trabalho a um monóide específico?

Que bom que você perguntou! Vamos dar uma olhada na definição de um functor alternativo gratuito:

 newtype Alt fa = Alt { alternatives :: [AltF fa] } data AltF fa = forall r. Ap (fr) (Alt f (r -> a)) | Pure a 

Esse é um tipo incomum definido por recursão mútua, portanto pode parecer muito confuso. Uma maneira de entender isso é imaginar que o Alt xs contém uma cadeia de alternativas formadas usando o operador <|> . AltF , f , <*> ( ).

AltF fa [fr] , r . Ap (:) , fr , Pure — [] . forall r. -XExistentialQuantification .

, Alt f , . , ( ) <*> <|> , , [a] <> .

, RegExp a -> String -> Maybe a , , . : .

, Alt . , , .

 matchAlts :: RegExp a -> String -> Maybe a matchAlts (Alt res) xs = asum [ matchChain re xs | re <- res ] 

asum :: [Maybe a] -> Maybe a , Just . ( , Maybe a Alternative — Nothing , <|> . . . )

. AltF , Ap Pure :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = _ matchChain (Pure x) cs = _ 

" ": GHC "", , , . ( Haskell "" (holes) , _ , . . . ) :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = case cs of [] -> Nothing d:ds | c == d -> matchAlts (($ x) <$> next) ds | otherwise -> Nothing matchChain (Pure x) _ = Just x 

Ap ( (:) ), , - . , . Prim r , , next :: RegExp (r -> a) . , next . , "" , Nothing . , Pure x ( [] ), , , .

, , . , , " " Ap , Pure , AltF .., .

:

 ghci> matchAlts testRegexp_ "acdcdcde" Just () ghci> matchAlts testRegexp_ "acdcdcdx" Nothing ghci> matchAlts testRegexp "acdcdcde" Just 3 ghci> matchAlts testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchAlts digit "9" Just 9 ghci> matchAlts bracketDigit "[2]" Just 2 ghci> matchAlts (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchAlts (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

?

foldMap . , , foldMap, , , , ! , — , — (:) [] .

, , : , , , (:) , [] . , . , [1,2,3] <> [4] , [1] <> [2,3] <> [4] . , , .

. , :

 data RegExp a = Empty | Pure a | Prim Char a | forall r. Seq (RegExp r) (RegExp (r -> a)) | Union (RegExp a) (RegExp a) | Many (RegExp a) 

RegExp , . . , RegExp :

 -- | a|(b|c) abc1 :: RegExp Int abc1 = Prim 'a' 1 `Union` (Prim 'b' 2 `Union` Prim 'c' 3) -- | (a|b)|c abc2 :: RegExp Int abc2 = (Prim 'a' 1 `Union` Prim 'b' 2) `Union` Prim 'c' 3 

, .

Alt Prim , , , . , matchAlts , . (a|b)|c a|(b|c) . Alt . , , .

, , (a|b)|c , (a|b)|c , , , RegExp . Alt , .

, , Alt , Alt Prim . , Alt Prim a|a a . , Alt f f . , : . , , , .

, . , , . RegExp , , — .

, Haskell. , - [a] . ( , - , "" $$$\bot$, - "" . . . )

: a|aa|aaa|aaaa|aaaaa|aaaaaa|... , ( , , , . . . ). , Haskell . , Alt many . , a* a|aa|aaa|aaaa|aaaaa|aaaaaa|... , . - many (char 'a') , . Haskell Alt , .

, , , , (), . , many .

, ! "" Alt , Control.Alternative.Free.Final , many (, , ).

, , runAlt . , Alternative , many ( RE regex-applicative ) . , Haskell , , , many .

, . ( ), ( , , . . ). matchPrefix , , , . , , , , . , GHC .

, , tails ( ) mapMaybe ( ). , , listToMaybe .

 matches :: RegExp a -> String -> [a] matches re = mapMaybe (matchPrefix re) . tails firstMatch :: RegExp a -> String -> Maybe a firstMatch re = listToMaybe . matches re 

, , matchPrefix Nothing , listToMaybe , Nothing ( , . . . ).

, . , , — , . , . , , , .

Alt Prim , : , , , .

? . :

 data Prim a = Only Char a --    | Letter a --     | Digit (Int -> a) --    , | Wildcard (Char -> a) --    , | Satisfy (Char -> Maybe a) --    , --   

, . .

, , . runAlt Alt .

(). , , , , . | . ( , . . . ). , - . , MonadPlus - , , . , .

, , . , !