O que é um combinador em Haskell

Question

Em Haskell do mundo real, eles descrevem combinadores assim:

Em Haskell, nos referimos a funções que recebem outras funções como argumentos e retornam novas funções como combinadores.

E mais tarde eles afirmam que maybeIO function é um combinador e sua assinatura de tipo é semelhante a esta:

maybeIO :: IO a -> IO (Maybe a)

Mas tudo que posso ver é que maybeIO é uma função que recebe um valor agrupado em IO monad e retorna um valor em IO monad.Então como essa função se torna um combinador?

Answer 1

Na verdade, existem duas coisas que podemos querer dizer quando dizemos combinador.A palavra está um pouco sobrecarregada.

1. Geralmente nos referimos a uma função que “combina” coisas.Por exemplo, sua função recebe um IO valor e constrói um valor mais complexo.Usando estes “combinadores” podemos combinar e criar novos complexos IO valores de relativamente poucas funções primitivas para criar IO valores.

   Por exemplo, em vez de criar uma função que leia 10 arquivos, usamos mapM_ readFile.Aqui combinadores são funções que usamos para combinar e construir valores

2. O termo mais estrito da ciência da computação é uma "função sem variáveis ​​livres".Então

    -- 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)
   

   Isso faz parte de um campo maior chamado "Lógica Combinatória", no qual você procura essencialmente eliminar variáveis ​​livres e substituí-las por combinadores e algumas funções primitivas.

TLDR:normalmente, quando dizemos combinador, nos referimos a uma noção mais geral chamada "padrão combinador", onde temos um punhado de funções primitivas e muitas funções definidas pelo usuário para construir valores mais complexos.

Answer 2

Não existe uma definição estrita de combinador, então isso realmente não significa nada nesse sentido.No entanto, é muito comum em Haskell construir funções ou valores mais complexos a partir de funções mais simples, e às vezes as funções não se encaixam completamente, então usamos um pouco de cola para fazê-las ficarem unidas.Os pedaços de cola que usamos para fazer isso chamamos de combinadores.

Por exemplo, se quiser calcular a raiz quadrada de um número arredondado para o número inteiro mais próximo, você pode escrever essa função como

approxSqrt x = round (sqrt x)

Você também pode perceber que o que estamos realmente fazendo aqui é pegar duas funções e construir uma função mais complexa usando-as como blocos de construção.Precisamos de algum tipo de cola para juntá-los, e essa cola é (.):

approxSqrt = round . sqrt

Portanto, o operador de composição de função é um combinador de funções – ele combina funções para criar novas funções.Outro exemplo é que talvez você queira ler cada linha de um arquivo em uma lista.Você poderia fazer isso da maneira óbvia:

do
  contents <- readFile "my_file.txt"
  let messages = lines contents
  ...

Mas!O que faríamos se tivéssemos uma função que lê um arquivo e retorna o conteúdo como strings?Então poderíamos fazer

do
  messages <- readFileLines "my_file.txt"
  ...

Acontece que temos uma função que lê um arquivo e uma função que pega uma string grande e retorna uma lista das linhas contidas nela.Se tivéssemos um pouco de cola para unir essas duas funções de uma forma significativa, poderíamos construir readFileLines!Mas é claro, sendo Haskell, essa cola está prontamente disponível.

readFileLines = fmap lines . readFile

Aqui usamos dois combinadores!Nós usamos o (.) de antes, e fmap é na verdade um combinador muito útil também.Dizemos que isso "eleva" uma computação pura para a mônada IO, e o que realmente queremos dizer é que lines tem a assinatura de tipo

lines :: String -> [String]

mas fmap lines tem a assinatura

fmap lines :: IO String -> IO [String]

então fmap é útil quando você deseja combinar cálculos puros com cálculos IO.

---

Estes foram apenas dois exemplos muito simples.À medida que você aprende mais sobre Haskell, você precisará (e inventará) cada vez mais funções de combinador para si mesmo.Haskell é muito poderoso na maneira como você pode pegar funções e transformá-las, combiná-las, virá-las do avesso e depois juntá-las.Os pedaços de cola que às vezes precisamos quando fazemos isso, esses pedaços que chamamos de combinadores.

Answer 3

"Combinator" não é definido com precisão em seu uso em Haskell.É mais correto usá-lo para se referir a funções que tomam outras funções como argumentos à la Cálculo Combinador mas na terminologia Haskell é frequentemente sobrecarregado para significar também uma função de "modificação" ou "combinação", especialmente de um Functor ou Monad.Nesse caso, você pode dizer que um combinador é uma função que "realiza alguma ação ou valor no contexto e retorna uma ação ou valor novo e modificado no contexto".

Seu exemplo, maybeIO é frequentemente chamado optional

optional :: Alternative f => f a -> f (Maybe a)
optional fa = (Just <$> fa) <|> pure Nothing

e tem uma natureza semelhante a um combinador porque leva o cálculo f a e o modifica genericamente para refletir a falha em seu valor.

A razão pela qual eles também são chamados de combinadores tem a ver com a forma como são usados.Um lugar típico para ver optional (e realmente, Alternative geralmente) está em bibliotecas combinadoras de analisadores.Aqui, tendemos a construir analisadores básicos usando simples Parseré como

satisfy :: (Char -> Bool) -> Parser Char
anyChar    = satisfy (const True)
whitespace = satisfy isSpace
number     = satisfy isNumeric

e então "modificamos" seu comportamento 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)

Muitas vezes também chamamos funções que combinam múltiplas funções/Functors/Monads "combinadores" também, o que talvez faça sentido mnemônico

-- 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')

Mas, em última análise, os combinadores têm mais a ver com a intenção e o uso de uma API do que com sua denotação estrita.Você verá frequentemente bibliotecas construídas a partir de "peças básicas", como funções ou satisfy que são então modificados e combinados com um conjunto de “combinadores”.O Parser O exemplo acima é um exemplo por excelência, mas no geral este é um padrão Haskell muito comum.