Qu'est-ce qu'un combinateur en Haskell

Question

Dans Haskell du monde réel, ils décrivent les combinateurs comme ceci :

En Haskell, nous faisons référence à des fonctions qui prennent d'autres fonctions comme arguments et renvoient de nouvelles fonctions comme combinateurs.

Et puis plus tard, ils déclarent que maybeIO la fonction est un combinateur et sa signature de type ressemble à ceci :

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

Mais tout ce que je peux voir c'est que maybeIO est une fonction qui prend une valeur enveloppée dans la monade IO et renvoie une valeur dans la monade IO.Alors comment cette fonction devient-elle un combinateur ?

Answer 1

Il y a en réalité deux choses que nous pourrions vouloir dire lorsque nous parlons de combinateur.Le mot est un peu surchargé.

1. Nous entendons généralement une fonction qui « combine » des choses.Par exemple, votre fonction prend en compte un IO valeur et construit une valeur plus complexe.En utilisant ces « combinateurs », nous pouvons combiner et créer de nouveaux complexes IO valeurs de relativement peu de fonctions primitives à créer IO valeurs.

   Par exemple, plutôt que de créer une fonction qui lit 10 fichiers, on utilise mapM_ readFile.Ici, les combinateurs sont des fonctions que nous utilisons pour combiner et créer des valeurs

2. Le terme informatique le plus strict est une « fonction sans variables libres ».Donc

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

   Cela fait partie d'un domaine plus vaste appelé "Logique combinatoire" dans lequel vous cherchez essentiellement à éliminer les variables libres et à les remplacer par des combinateurs et quelques fonctions primitives.

TLDR :généralement, lorsque nous parlons de combinateur, nous faisons référence à une notion plus générale appelée « modèle de combinateur » dans lequel nous avons une poignée de fonctions primitives et de nombreuses fonctions définies par l'utilisateur pour construire des valeurs plus complexes.

Answer 2

Il n’y a pas de définition stricte d’un combinateur, donc cela ne veut vraiment rien dire dans ce sens.Cependant, il est très courant dans Haskell de construire des fonctions ou des valeurs plus complexes à partir de fonctions plus simples, et parfois les fonctions ne s'emboîtent pas complètement, nous utilisons donc de la colle pour les faire coller ensemble.Les morceaux de colle que nous utilisons pour ce faire sont appelés combinateurs.

Par exemple, si vous souhaitez calculer la racine carrée d’un nombre arrondi à l’entier le plus proche, vous pouvez écrire cette fonction sous la forme

approxSqrt x = round (sqrt x)

Vous réaliserez peut-être également que ce que nous faisons ici consiste à prendre deux fonctions et à construire une fonction plus complexe en les utilisant comme éléments de base.Cependant, nous avons besoin d'une sorte de colle pour les assembler, et cette colle est (.):

approxSqrt = round . sqrt

L’opérateur de composition de fonctions est donc un combinateur de fonctions – il combine des fonctions pour créer de nouvelles fonctions.Un autre exemple est que vous souhaitez peut-être lire chaque ligne d'un fichier dans une liste.Vous pouvez procéder de la manière la plus évidente :

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

Mais!Que ferions-nous si nous avions une fonction qui lit un fichier et renvoie le contenu sous forme de chaînes ?Alors nous pourrions faire

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

Il s'avère que nous avons une fonction qui lit un fichier et une fonction qui prend une grosse chaîne et renvoie une liste des lignes qu'elle contient.Si nous avions seulement un peu de colle pour coller ces deux fonctions ensemble de manière significative, nous pourrions construire readFileLines!Mais bien sûr, étant donné Haskell, cette colle est facilement disponible.

readFileLines = fmap lines . readFile

Ici, nous utilisons deux combinateurs !Nous utilisons le (.) d'avant, et fmap est en fait également un combinateur très utile.Nous disons que cela « élève » un calcul pur dans la monade IO, et ce que nous voulons vraiment dire, c'est que lines a la signature de type

lines :: String -> [String]

mais fmap lines a la signature

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

donc fmap est utile lorsque vous souhaitez combiner des calculs purs avec des calculs IO.

---

Ce ne sont là que deux exemples très simples.Au fur et à mesure que vous en apprendrez davantage sur Haskell, vous aurez besoin (et inventer) de plus en plus de fonctions de combinateur pour vous-même.Haskell est très puissant dans la manière dont vous pouvez prendre des fonctions et les transformer, les combiner, les retourner puis les coller ensemble.Les morceaux de colle dont nous avons parfois besoin pour faire cela, ces morceaux que nous appelons combinateurs.

Answer 3

"Combinator" n'est pas exactement défini avec précision dans son utilisation dans Haskell.Il est plus correct de l'utiliser pour faire référence à des fonctions qui prennent d'autres fonctions comme arguments à la Calcul combinateur mais dans la terminologie Haskell, il est souvent surchargé pour signifier également une fonction de « modification » ou de « combinaison », en particulier d'un Functor ou Monad.Dans ce cas, vous pourriez dire qu'un combinateur est une fonction qui "prend une action ou une valeur dans son contexte et renvoie une nouvelle action ou une valeur modifiée dans son contexte".

Votre exemple, maybeIO est souvent appelé optional

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

et il a une nature semblable à un combinateur car il prend le calcul f a et le modifie de manière générique pour refléter l'échec dans sa valeur.

La raison pour laquelle on les appelle combinateurs est également liée à la façon dont ils sont utilisés.Un endroit typique à voir optional (et en effet, Alternative généralement) se trouve dans les bibliothèques de combinateurs d’analyseurs.Ici, nous avons tendance à construire des analyseurs de base en utilisant de simples Parserc'est comme

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

puis on "modifie" leur comportement à l'aide de "combinateurs"

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

Souvent, nous appelons également des fonctions qui combinent plusieurs fonctions/Functors/Monads "combinateurs" également, ce qui a peut-être un sens mnémotechnique

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

Mais en fin de compte, les combinateurs concernent davantage l’intention et l’utilisation d’une API que sa dénotation stricte.Vous verrez fréquemment des bibliothèques construites à partir de « éléments de base » comme des fonctions ou satisfy qui sont ensuite modifiés et combinés avec un ensemble de « combinateurs ».Le Parser L'exemple ci-dessus est un exemple par excellence, mais dans l'ensemble, il s'agit d'un modèle Haskell très courant.