¿Qué es un combinador en Haskell?

Question

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?

Answer 1

Realmente hay 2 cosas a las que podríamos referirnos cuando decimos combinador.La palabra está un poco sobrecargada.

1. 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 complejos IO valores de relativamente pocas funciones primitivas para crear IO 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.

2. 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.

Answer 2

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.

Answer 3

"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 Parseres 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.