Cos'è un combinatore a Haskell
-
21-12-2019 - |
Domanda
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?
Soluzione
Ci sono davvero 2 cose che potremmo significare quando diciamo il combinatore. La parola è un po 'sovraccaricata.
- .
-
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 diIO
complessi da relativamente poche funzioni primitive per creare valoriIO
.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 -
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.
Altri suggerimenti
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.
"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.