Cos'è un combinatore a Haskell

Question

in Real World Haskell , descrivono i combinatori come questo:

.

A Haskell, ci riferiamo a funzioni che prendono altre funzioni come argomenti e restituiamo nuove funzioni come combinatrici.

E poi in seguito affermano che la funzione maybeIO è un combinatore e la sua firma del tipo è simile a questo:

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

.

Ma tutto quello che posso vedere è che maybeIO è una funzione che prende un valore avvolto in Io Monad e restituisce un valore in Io Monad.Quindi in che modo questa funzione diventa un combinatore?

Answer 1

Ci sono davvero 2 cose che potremmo significare quando diciamo il combinatore. La parola è un po 'sovraccaricata.

.

1. In genere intendiamo una funzione che "combina" cose. Ad esempio la funzione prende un valore IO e accumula un valore più complesso. Usando questi "combinatrici" possiamo combinare e creare nuovi valori generali di IO complessi da relativamente poche funzioni primitive per creare valori IO.

   Ad esempio, anziché creare una funzione che legge 10 file, usiamo mapM_ readFile. Qui i combinatori sono funzioni che usiamo per combinare e costruire valori

2. Il termine Stricter Computer Scienze è una "funzione senza variabili libere". Quindi

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

   .

   Questo fa parte di un campo più grande chiamato "logica combinatoria" in cui si cerca di eliminare essenzialmente le variabili libere e sostituirla con i combinatrici e alcune funzioni primitive.

TLDR: Solitamente quando diciamo il combinatore, ci riferiamo a una nozione più generale chiamata "Pattern di combinatori" in cui abbiamo una manciata di funzioni primitive e molte funzioni definite dall'utente per creare valori più complessi.

Answer 2

Non c'è una definizione rigorosa di un combinatore, quindi non significa davvero nulla in questo senso. Tuttavia, è molto comune a Haskell per costruire funzioni o valori più complessi da quelli più semplici, e talvolta funzioni non si adattano completamente insieme, quindi usiamo qualche colla per farli attaccare. I bit di colla che usiamo per fare ciò che chiamiamo combinatrici.

Ad esempio, se si desidera calcolare la radice quadrata di un numero arrotondato all'Integer più vicino, è possibile scrivere questa funzione come

approxSqrt x = round (sqrt x)

.

Puoi anche capire che ciò che stiamo facendo qui sta prendendo due funzioni e costruendo una funzione più complessa usandole come blocchi di costruzione. Abbiamo bisogno di una specie di colla per metterli insieme, tuttavia, e quella colla è (.):

approxSqrt = round . sqrt

.

Quindi l'operatore di composizione della funzione è un combinatore di funzioni - Combina le funzioni per creare nuove funzioni. Un altro esempio è che forse vuoi leggere ogni riga di un file in un elenco. Potresti farlo il modo ovvio:

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

.

Ma! Cosa faremmo se avessimo una funzione che legge un file e restituisse il contenuto come stringhe? Quindi potremmo fare

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

.

Come si scopre, abbiamo una funzione che legge un file e abbiamo una funzione che prende una grande stringa e restituisce un elenco delle linee in esso. Se avessimo solo una colla per attaccare queste due funzioni insieme in modo significativo, potremmo costruire readFileLines! Ma naturalmente, questo è Haskell, quella colla è facilmente disponibile.

readFileLines = fmap lines . readFile

.

Qui usiamo due combinatori! Utilizziamo il (.) da prima e fmap è in realtà un combinatore molto utile. Diciamo che "solleva" un calcolo puro nell'Io Monad, e ciò che intendiamo veramente è che lines ha la firma del tipo

lines :: String -> [String]

.

Ma fmap lines ha la firma

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

.

Così fmap è utile quando si desidera combinare calcoli puri con IO Calcoli.

---

.

Questi sono stati solo due esempi molto semplici. Mentre impari di più haskell, ti troverai bisogno di aver bisogno (e inventando) sempre più funzioni di combinatore per te stesso. Haskell è molto potente nel modo in cui puoi prendere funzioni e trasformarli, combinarli, girarli dentro e poi li attaccarli. I pezzi di colla a volte abbiamo bisogno quando lo facciamo, quei bit chiamiamo combinatori.

Answer 3

"Combinator" non è esattamente definito con precisione nell'uso in Haskell. È più corretto usarlo per fare riferimento a funzioni che prendono altre funzioni come argomenti A la Combinator calculus ma Nella terminologia Haskell è spesso sovraccaricata per significare anche una funzione "modifica" o "combinazione", in particolare di un Functor o Monad. In questo caso potresti dire che un combinatore è una funzione che "prende qualche azione o valore nel contesto e restituisce una nuova azione o un valore modificato o un valore nel contesto".

Il tuo esempio, maybeIO viene spesso chiamato optional

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

.

E ha una natura simile a un combinatore perché prende il calcolo f a e modificalo genericamente per riflettere il fallimento nel suo valore.

Il motivo per cui questi sono chiamati combinatrici hanno a che fare con il modo in cui vengono utilizzati. Un luogo tipico per vedere optional (e in effetti, Alternative in generale) è in librerie di combinatori di parser. Qui, tendiamo a costruire parsers di base usando semplici generatori di generacodetagcodes come

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

.

E poi "modifichiamo" il loro comportamento usando "Combinator"

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

.

spesso chiamiamo anche funzioni che combinano anche più funzioni / Parser / Functors "combinatrici", che forse fa il senso mnemonico

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

.

Ma in definitiva, i combinatori sono più sull'intento e sull'utilizzo di un'API rispetto alla sua rigida denotazione. Vedrai frequentemente le librerie costruite da "pezzi di base" come funzioni o Monads che vengono quindi modificati e combinati con un set di "combinatrici". L'esempio satisfy sopra è un esempio per eccellenza, ma del tutto questo è un modello Haskell molto comune.