¿Qué es un combinador en Haskell?
-
21-12-2019 - |
Pregunta
En Haskell del mundo real, describen combinadores como este:
En Haskell, nos referimos a funciones que toman otras funciones como argumentos y devuelven nuevas funciones como combinadores.
Y luego afirman que maybeIO
La función es un combinador y su firma de tipo se ve así:
maybeIO :: IO a -> IO (Maybe a)
Pero todo lo que puedo ver es que maybeIO
es una función que toma un valor incluido en la mónada IO y devuelve un valor en la mónada IO.Entonces, ¿cómo se convierte esta función en un combinador?
Solución
Realmente hay 2 cosas a las que podríamos referirnos cuando decimos combinador.La palabra está un poco sobrecargada.
Normalmente nos referimos a una función que "combina" cosas.Por ejemplo, su función toma un
IO
valor y construye un valor más complejo.Usando estos "combinadores" podemos combinar y crear nuevos complejosIO
valores de relativamente pocas funciones primitivas para crearIO
valores.Por ejemplo, en lugar de crear una función que lea 10 archivos, usamos
mapM_ readFile
.Aquí los combinadores son funciones que usamos para combinar y construir valores.El término informático más estricto es "función sin variables libres".Entonces
-- The primitive combinators from a famous calculus, SKI calculus. id a = a -- Not technically primitive, genApp const const const a b = a genApp x y z = x z (y z)
Esto es parte de un campo más amplio llamado "lógica combinatoria" en el que esencialmente se busca eliminar las variables libres y reemplazarlas con combinadores y algunas funciones primitivas.
TLDR:Generalmente, cuando decimos combinador, nos referimos a una noción más general llamada "patrón combinador", donde tenemos un puñado de funciones primitivas y muchas funciones definidas por el usuario para construir valores más complejos.
Otros consejos
No existe una definición estricta de combinador, por lo que realmente no significa nada en ese sentido.Sin embargo, es muy común en Haskell construir funciones o valores más complejos a partir de otros más simples y, a veces, las funciones no encajan completamente, por lo que usamos algo de pegamento para que se peguen.Los trozos de pegamento que usamos para hacer eso los llamamos combinadores.
Por ejemplo, si desea calcular la raíz cuadrada de un número redondeado al entero más cercano, puede escribir esa función como
approxSqrt x = round (sqrt x)
También puedes darte cuenta de que lo que realmente estamos haciendo aquí es tomar dos funciones y construir una función más compleja usándolas como bloques de construcción.Sin embargo, necesitamos algún tipo de pegamento para unirlos, y ese pegamento es (.)
:
approxSqrt = round . sqrt
Entonces, el operador de composición de funciones es un combinador de funciones: combina funciones para crear nuevas funciones.Otro ejemplo es que quizás desee leer cada línea de un archivo en una lista.Podrías hacer esto de la manera obvia:
do
contents <- readFile "my_file.txt"
let messages = lines contents
...
¡Pero!¿Qué haríamos si tuviéramos una función que lea un archivo y devuelva el contenido como cadenas?Entonces podríamos hacer
do
messages <- readFileLines "my_file.txt"
...
Resulta que tenemos una función que lee un archivo y tenemos una función que toma una cadena grande y devuelve una lista de las líneas que contiene.Si sólo tuviéramos un poco de pegamento para unir esas dos funciones de manera significativa, podríamos construir readFileLines
!Pero, por supuesto, al tratarse de Haskell, ese pegamento está disponible.
readFileLines = fmap lines . readFile
¡Aquí usamos dos combinadores!Usamos el (.)
desde antes, y fmap
En realidad, también es un combinador muy útil.Decimos que "eleva" un cálculo puro a la mónada IO, y lo que realmente queremos decir es que lines
tiene la firma tipográfica
lines :: String -> [String]
pero fmap lines
tiene la firma
fmap lines :: IO String -> IO [String]
entonces fmap
Es útil cuando desea combinar cálculos puros con cálculos IO.
Estos han sido sólo dos ejemplos muy simples.A medida que aprenda más sobre Haskell, se encontrará necesitando (e inventando) más y más funciones de combinación para usted mismo.Haskell es muy poderoso en la forma en que puedes tomar funciones y transformarlas, combinarlas, darles la vuelta y luego unirlas.Los trozos de pegamento que a veces necesitamos cuando hacemos eso, esos trozos los llamamos combinadores.
"Combinador" no está exactamente definido en su uso en Haskell.Es más correcto usarlo para referirse a funciones que toman otras funciones como argumentos al estilo Cálculo combinador pero en la terminología de Haskell frecuentemente se sobrecarga para significar también una función de "modificación" o "combinación", especialmente de una Functor
o Monad
.En este caso, se podría decir que un combinador es una función que "realiza alguna acción o valor en contexto y devuelve una acción o valor nuevo y modificado en contexto".
Tu ejemplo, maybeIO
a menudo se llama optional
optional :: Alternative f => f a -> f (Maybe a)
optional fa = (Just <$> fa) <|> pure Nothing
y tiene una naturaleza similar a un combinador porque toma el cálculo f a
y lo modifica genéricamente para reflejar fallas en su valor.
La razón por la que estos también se llaman combinadores tiene que ver con cómo se usan.Un lugar típico para ver. optional
(y de hecho, Alternative
generalmente) está en bibliotecas combinadoras de analizadores.Aquí, tendemos a construir analizadores básicos usando simples Parser
es como
satisfy :: (Char -> Bool) -> Parser Char
anyChar = satisfy (const True)
whitespace = satisfy isSpace
number = satisfy isNumeric
y luego "modificamos" su comportamiento usando "combinadores"
-- the many and some combinators
many :: Alternative f => f a -> f [a] -- zero or more successes
some :: Alternative f => f a -> f [a] -- one or more successes
many f = some f <|> pure []
some f = (:) <$> f <*> many f
-- the void combinator forgets what's inside the functor
void :: Functor f => f a -> f ()
void f = const () <$> f
-- from the external point of view, this is another "basic" Parser
-- ... but we know it's actually built from an even more basic one
-- and the judicious application of a few "combinators"
blankSpace = Parser ()
blankSpace = void (many whitespace)
word :: Parser String
word = many (satisfy $ not . isSpace)
A menudo también llamamos funciones que combinan múltiples funciones/Functors
/Monads
"combinadores" también, lo que quizás tenga sentido mnemotécnico
-- the combine combinator
combine :: Applicative f => f a -> f b -> f (a, b)
combine fa fb = (,) <$> fa <*> fb
-- the ignore-what's-next combinator
(<*) :: Applicative f => f a -> f b -> f a
fa <* fb = const <$> fa <*> fb
-- the do-me-then-forget-me combinator
(*>) :: Applicative f => f a -> f b -> f b
fa *> fb = flip const <$> fa <*> fb
line = Parser String
line = many (satisfy $ \c -> c /= '\n') <* satisfy (=='\n')
Pero, en última instancia, los combinadores tienen más que ver con la intención y el uso de una API que con su denotación estricta.Con frecuencia verá bibliotecas creadas a partir de "piezas básicas", como funciones o satisfy
que luego se modifican y combinan con un conjunto de "combinadores".El Parser
El ejemplo anterior es un ejemplo por excelencia, pero en conjunto es un patrón de Haskell muy común.