Les traigo a su atención una traducción de un maravilloso artículo nuevo de Justin Le. En su blog en Code, este autor habla en un lenguaje bastante fácil sobre la esencia matemática de soluciones funcionales hermosas y elegantes para problemas prácticos. Este artículo examina en detalle un ejemplo de cómo la transferencia de la estructura matemática que forman los datos en un área temática a un sistema de tipos de programas puede inmediatamente, como Gerald y Sassman escribieron "automáticamente", conducir a una solución de trabajo.

El código que se muestra en la imagen es una implementación completa y autónoma y extensible del analizador de expresiones regulares, escrito desde cero. De primera clase, tipo real de magia!

¡Hoy implementamos analizadores y expresiones regulares aplicativas (en el espíritu de la biblioteca aplicativa regex ) usando estructuras algebraicas gratuitas! Las estructuras libres son una de mis herramientas favoritas en Haskell y escribí anteriormente sobre grupos libres , variaciones sobre el tema de las mónadas libres y el functor aplicativo "libre" en monoides .

Las expresiones regulares (y los analizadores para ellos) son omnipresentes en programación y ciencias de la computación, por lo que espero que al demostrar cuán fáciles son de implementar utilizando estructuras libres, ayudaré al lector a apreciar los méritos de este enfoque sin temor a perderse en detalles innecesarios.

Todo el código del artículo está disponible en línea como un "ejecutable de pila". Si lo ejecuta ( ./regexp.hs ), la sesión de GHCi comenzará con todas las definiciones, por lo que tendrá la oportunidad de jugar con las funciones y sus tipos.

Este artículo será completamente comprensible para el "principiante avanzado" o el "especialista principiante" en Haskell. Requiere el conocimiento de los conceptos básicos de un lenguaje: coincidencia de patrones, tipos de datos algebraicos y abstracciones como monoides, functores y anotaciones do.

Idiomas regulares

Una expresión regular es una forma de definir un lenguaje regular. Formalmente, tal expresión está construida de tres elementos básicos:

1. Un conjunto vacío es un elemento que no se asigna a nada.
2. Una cadena vacía es un elemento neutral que coincide trivialmente con una cadena vacía.
3. Un literal es un símbolo que coincide con sí mismo. Un montón de un elemento.

Y también de tres operaciones:

1. Concatenación: RS , secuencia de expresiones. El producto de conjuntos (cartesiano).
2. Alternativa: R|S , elección entre expresiones. La unión de conjuntos.
3. Wedge Star: R* , repetición de una expresión un número arbitrario de veces (incluido cero).

Y eso es todo lo que compone las expresiones regulares, ni más ni menos. A partir de estos componentes básicos, puede construir todas las demás operaciones conocidas en expresiones regulares; por ejemplo, a+ puede expresarse como aa* , y categorías como \w pueden representarse como una alternativa a los caracteres adecuados.

Functor alternativo

Cuando miras la estructura de las expresiones regulares, ¿no te parece familiar? Me recuerda mucho a la clase de tipo Alternative . Si un functor pertenece a esta clase, esto significa que se definen los siguientes para él:

1. Un elemento vacío correspondiente a la falla o error de cálculo.
2. pure x : un elemento único (de la clase Applicative ).
3. Operación <*> , organización de cálculos secuenciales.
4. Operación <|> , organización de cálculos alternativos.
5. La función many es la operación de repetir cálculos cero o más veces.

Todo esto es muy similar a la construcción de un lenguaje regular, ¿verdad? Quizás el functor alternativo es casi lo que necesitamos, lo único que falta es la primitiva correspondiente al carácter literal.

Cualquier persona nueva en la clase Alternative puede encontrar una buena introducción a Typeclassopedia . Pero en el marco de nuestro artículo, esta clase representa simplemente un "doble monoide" con dos formas de combinar <*> y <|> , que, en cierto sentido, se pueden comparar con las operaciones * y + para los números. En general, para determinar un functor alternativo, los cinco puntos anteriores y algunas leyes adicionales de conmutatividad y distributividad son suficientes.

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

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

Por lo tanto, podemos considerar las expresiones regulares como un functor alternativo, más una primitiva para un carácter literal. Pero, hay otra forma de verlos, y nos lleva directamente a estructuras libres. En lugar del "functor alternativo con literales", podemos convertir el literal en una instancia de la clase Alternative .

Libertad

Escribamos así. Escriba para literal primitivo:

 data Prim a = Prim Char a deriving Functor 

Tenga en cuenta que dado que trabajamos con functores (aplicativos, alternativos), con todas nuestras expresiones regulares se asociará un cierto "resultado". Esto se debe a que al definir una instancia para las clases Functor , Applicative y Alternative , debemos tener un tipo de parámetro.

Por un lado, puede ignorar este tipo, pero por otro lado, debe usar este valor como resultado de la coincidencia con una expresión regular, como se hace en aplicaciones industriales que funcionan con expresiones regulares.

En nuestro caso, Prim 'a' 1 :: Prim Int representará una primitiva que se asigna al carácter 'a' y se interpreta de inmediato, dando como resultado una unidad.

Bueno, ahora ... demosle a nuestro primitivo la estructura matemática deseada usando el functor alternativo gratuito de la biblioteca free :

 import Control.Alternative.Free type RegExp = Alt Prim 

Eso es todo! ¡Este es nuestro tipo completo para expresiones regulares! Al declarar el tipo Alt como una instancia de la clase Functor , obtuvimos todas las operaciones de las clases Applicative y Alternative , ya que en este caso hay instancias de Applicative (Alt f) y Alternative (Alt f) . Ahora tenemos:

• Conjunto vacío trivial: empty de la clase Alternative
• Cadena vacía: pure de la clase Applicative
• Carácter Literal - Prim Básico
• Concatenación - <*> de la clase Applicative
• Alternativa - <|> de la clase Alternative
• Kleene Star - many de la clase Alternative

¡Y todo esto lo obtuvimos completamente "gratis", es decir, "gratis"!

Esencialmente, una estructura libre automáticamente nos proporciona solo una abstracción para el tipo base y nada más. Pero las expresiones regulares, por sí mismas, también representan solo una estructura: elementos básicos y un conjunto de operaciones, ni más ni menos, por lo que el functor alternativo gratuito nos proporciona exactamente lo que necesitamos. No más, pero no menos.

Después de agregar algunas funciones de envoltura convenientes ... ¡el trabajo sobre el 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 -- , ? 

Ejemplos

Bueno, vamos a intentarlo? Construyamos la expresión (a|b)(cd)*e , que devuelve, en caso de una coincidencia exitosa, el tipo de unidad () :

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

La función void :: Functor f => fa -> f () del paquete Data.Functor descarta el resultado, lo usamos, ya que solo estamos interesados ​​en el éxito de la comparación. Pero los operadores <|> , *> y many utilizamos exactamente como se supone al concatenar o elegir una de las opciones.

Aquí hay un ejemplo más complicado e interesante: definamos la misma expresión regular, pero ahora, como resultado de la coincidencia, calculamos el número de repeticiones del cd de la subcadena.

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

Hay una sutileza en la operación de los operadores *> y <* : las flechas indican el resultado que debe guardarse. Y dado que many (string "cd") :: RegExp [String] devuelve una lista de elementos que se repiten, podemos, permaneciendo dentro del functor, calcular la longitud de esta lista obteniendo el número de repeticiones.

Además, la -XApplicativeDo compilador GHC -XApplicativeDo permite escribir nuestra expresión usando do-notation, que probablemente sea más fácil de entender:

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

Todo esto es algo similar a cómo "capturamos" el resultado de analizar una cadena usando una expresión regular, obteniendo acceso a ella. Aquí hay un ejemplo en Ruby:

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

La única diferencia es que agregamos algo de procesamiento posterior para calcular el número de repeticiones.

Aquí hay otra conveniente regular \d que coincide con un número del 0 al 9 y devuelve un número:

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

Aquí, la función asum del paquete Control.Applicative.Alternative representa una selección de los elementos de la lista asum [x,y,z] = x <|> y <|> z , y la función intToDigit define en el paquete Data.Char . Y, nuevamente, podemos crear cosas bastante elegantes, por ejemplo, la expresión \[\d\] , correspondiente al número entre corchetes:

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

Analizando

Bueno, bueno, todo lo que hicimos fue describir el tipo de datos para un literal con concatenación, selección y repetición. Genial Pero lo que realmente necesitamos es hacer coincidir una cadena con una expresión regular, ¿verdad? ¿Cómo puede ayudarnos un functor alternativo gratuito con esto? De hecho, ayudará mucho. ¡Veamos dos formas de hacer esto!

Descargar el functor alternativo

¿Qué es la libertad?

La forma canónica de usar una estructura libre es doblarla en una estructura de concreto usando álgebra adecuada. Por ejemplo, la transformación foldMap convierte un monoide (lista) libre en el valor de cualquier instancia de la clase Monoid :

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

La función foldMap convierte la transformación a -> m en la transformación [a] -> m (o, FreeMonoid a -> m ), con un monoide específico m . La idea general es que el uso de una estructura libre le permite posponer su uso específico "para más adelante", separando el tiempo de creación y el tiempo de uso de la estructura.

Por ejemplo, podemos construir un monoide libre 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 

Y ahora podemos decidir cómo queremos interpretar la operación <> :
Tal vez esta adición?

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

O la multiplicación?

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

¿O tal vez el cálculo del número máximo?

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

La idea es posponer la selección de un monoide en particular mediante la construcción de una colección gratuita de números 1, 2, 3 y 4. Un monoide libre sobre los números determina la estructura sobre ellos que necesita, ni más ni menos. Para usar foldMap especificamos "cómo percibir el tipo base" pasando el operador <> a un monoide en particular.

Interpretación en un Fundador del State

En la práctica, obtener un resultado de una estructura libre consiste en encontrar (o crear) un functor adecuado que nos proporcione el comportamiento deseado. En nuestro caso, tenemos la suerte de que haya una implementación específica de la clase Alternative que funcione exactamente como la necesitamos: StateT String Maybe .

El producto <*> para este functor consiste en organizar una secuencia de cambios de estado. En nuestro caso, bajo el estado, consideraremos el resto de la cadena analizada, por lo que el análisis secuencial es la mejor coincidencia para la operación <*> .

Y su suma <|> funciona como retroceso, una búsqueda con un retorno a la alternativa en caso de falla. Conserva el estado desde la última ejecución exitosa del análisis y vuelve a él si la alternativa se selecciona sin éxito. Este es exactamente el comportamiento que esperamos de la expresión R|S

Finalmente, una transformación natural para un functor alternativo gratuito se llama runAlt :

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

O, para el tipo RegExp:

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

Si no está familiarizado con los tipos de RankN (con una construcción completa), puede ver una buena introducción aquí . El punto aquí es que debe proporcionar una función runAlt que funcione con Prim b para absolutamente cualquier b , y no de ningún tipo en particular, como Int y Bool , por ejemplo. Es decir, como con foldMap solo necesitamos especificar qué hacer con el tipo base. En nuestro caso, responda la pregunta: "¿Qué se debe hacer con el tipo Prim ?"

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

Esta es una interpretación de Prim como una acción en el contexto de la StateT String Maybe , donde el estado es una cadena StateT String Maybe . Permíteme recordarte que Prim contiene información sobre el carácter coincidente c su interpretación en forma de algún valor de x . Prim procesamiento Prim consta de los siguientes pasos:

• Usando get estado (parte aún no analizada de la cadena) e imprimimos inmediatamente su primer carácter y el resto. Si la línea está vacía, volverá una alternativa. ( El transformador StateT actúa dentro del functor Maybe, y si es imposible hacer coincidir el patrón en el lado derecho del operador <- dentro del bloque do, los cálculos terminarán con el resultado empty , es decir, Nothing . Approx. Trans. ).
• Usamos la expresión de guardia para unir el carácter actual con el carácter dado. En caso de falla, empty devuelve el empty y pasamos a la opción alternativa.
• Cambiamos el estado reemplazando la cadena analizada con su "cola", ya que en este momento el carácter actual ya puede considerarse analizado con éxito.
• Devolvemos lo que la primitiva primitiva debería devolver.

Ya puede usar esta función para asignar RegEx a un prefijo de cadena. Para hacer esto, debe comenzar los cálculos usando runAlt y runStateT , pasando la cadena analizada a la última función como argumento:

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

Eso es todo! Veamos cómo funciona nuestra primera solución:

 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, que fue eso?

Parece que todo sucedió un poco más rápido de lo que esperabas. Hace un minuto escribimos nuestro primitivo, ¡y luego otra vez! y el analizador de trabajo está listo. Aquí, de hecho, todo el código clave, algunas líneas en 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 

¿Y tenemos un analizador de expresiones regulares completamente funcional? Que paso

Recuerde que a un alto nivel de abstracción, Alt Prim ya contiene pure , empty , Prim , <*> , <|> , y many en su estructura (hay una sutileza desagradable con este operador, pero más sobre eso más adelante). Lo que runAlt hace runAlt es usar el comportamiento de un functor alternativo particular (en nuestro caso, StateT String Maybe ) para controlar el comportamiento de los operadores pure , empty , <*> , <|> y many . Sin embargo, StateT no tiene un operador incorporado similar a Prim , y para esto necesitábamos escribir processPrim .

Entonces, para el tipo Prim , la función runAlt usa runAlt , y para pure , empty , <*> , <|> y many , se usa una instancia adecuada de la clase Alternative . Por lo tanto, el 83% del trabajo lo realiza para nosotros el functor StateT , y el 17% restante lo realiza StateT . En verdad, esto es algo decepcionante. Uno puede preguntarse: ¿por qué fue necesario comenzar con el envoltorio Alt ? ¿Por qué no definir inmediatamente el tipo RegExp = StateT String Maybe y la primitiva apropiada char :: Char -> StateT String Maybe Char ? Si todo se hace en el StateT StateT, ¿por qué molestarse con Alt , un functor alternativo gratuito?

Alt principal ventaja de Alt sobre StateT es que StateT es ... una herramienta bastante poderosa. Pero, de hecho, es poderoso, hasta el punto del absurdo. Se puede usar para representar una gran cantidad de los cálculos y estructuras más diversos, y, desafortunadamente, es fácil imaginar algo que no sea una expresión regular. Digamos algo básico como put "hello" :: StateT String Maybe () no coincide con ninguna expresión regular válida, pero es del mismo tipo que RegExp () . Por lo tanto, mientras decimos que Alt Prim coincide con una expresión regular, no más, pero no menos, no podemos decir lo mismo con StateT String Maybe . El tipo Alt Prim es la representación perfecta de una expresión regular. Todo lo que se puede expresar con su ayuda es una expresión regular, pero cualquier cosa que no sea tal expresión no se puede expresar con su ayuda. Aquí, sin embargo, también hay algunas sutilezas desagradables asociadas con la pereza de Haskell, más sobre esto más adelante.

Aquí podemos considerar StateT solo como un contexto utilizado para uno
interpretaciones de expresiones regulares - como un analizador sintáctico. Pero puedes imaginar otras formas de usar RegExp . Por ejemplo, podemos necesitar su representación textual, que es lo que StateT no permitirá.

No podemos decir que StateT String Maybe es una expresión regular, solo que este functor puede representar un analizador basado en gramáticas regulares. Pero sobre Alt Prim podemos decir con certeza que esta es una expresión regular ( como dicen los matemáticos, son iguales al isomorfismo, aprox. Trans. ).

Uso directo de estructura libre.

Todo esto, por supuesto, es muy bueno, pero ¿qué pasa si no queremos cambiar el 83% del trabajo para codificar un tipo que fue escrito por alguien para nosotros? ¿Es posible usar la estructura Alt libre directamente para escribir un analizador? Esta pregunta es similar a esta: ¿cómo escribir una función que procese listas (haciendo coincidir los constructores (:) y [] ) en lugar de usar solo foldMap ? ¿Cómo operar directamente con esta estructura en lugar de delegar el trabajo a un monoide específico?

Me alegra que hayas preguntado! Echemos un vistazo a la definición de un functor alternativo gratuito:

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

Este es un tipo inusual definido a través de la recursividad mutua, por lo que puede parecer muy confuso. Una forma de entenderlo es imaginar que Alt xs contiene una cadena de alternativas formadas usando el 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 - , , . , .

, , . , !