Was ist ein Kombinator in Haskell?

Question

In Haskell aus der realen Welt, sie beschreiben Kombinatoren wie folgt:

In Haskell beziehen wir uns auf Funktionen, die andere Funktionen als Argumente annehmen und neue Funktionen als Kombinatoren zurückgeben.

Und später sagen sie das maybeIO Die Funktion ist ein Kombinator und ihre Typsignatur sieht folgendermaßen aus:

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

Aber ich kann nur das sehen maybeIO ist eine Funktion, die einen in eine E/A-Monade eingeschlossenen Wert annimmt und einen Wert in einer E/A-Monade zurückgibt.Wie wird diese Funktion dann zu einem Kombinator?

Answer 1

Es gibt eigentlich zwei Dinge, die wir meinen könnten, wenn wir von Kombinator sprechen.Das Wort ist etwas überladen.

1. Normalerweise meinen wir eine Funktion, die Dinge „kombiniert“.Ihre Funktion umfasst beispielsweise eine IO Wert und baut einen komplexeren Wert auf.Mithilfe dieser „Kombinatoren“ können wir neue Komplexe kombinieren und erstellen IO Werte aus relativ wenigen zu erstellenden Grundfunktionen IO Werte.

   Anstatt beispielsweise eine Funktion zu erstellen, die 10 Dateien liest, verwenden wir mapM_ readFile.Hier sind Kombinatoren Funktionen, die wir verwenden, um Werte zu kombinieren und aufzubauen

2. Der strengere Informatikbegriff ist eine „Funktion ohne freie Variablen“.Also

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

   Dies ist Teil eines größeren Bereichs namens „Kombinatorische Logik“, in dem Sie versuchen, freie Variablen im Wesentlichen zu eliminieren und sie durch Kombinatoren und einige primitive Funktionen zu ersetzen.

TLDR:Wenn wir von Kombinator sprechen, beziehen wir uns normalerweise auf einen allgemeineren Begriff namens „Kombinatormuster“, bei dem wir über eine Handvoll primitiver Funktionen und viele benutzerdefinierte Funktionen verfügen, um komplexere Werte aufzubauen.

Answer 2

Es gibt keine strenge Definition eines Kombinators, daher bedeutet er in diesem Sinne eigentlich nichts.Allerdings ist es in Haskell sehr üblich, komplexere Funktionen oder Werte aus einfacheren zu erstellen, und manchmal passen Funktionen nicht vollständig zusammen, sodass wir etwas Kleber verwenden, um sie zusammenzuhalten.Die Kleberstücke, die wir dafür verwenden, nennen wir Kombinatoren.

Wenn Sie beispielsweise die Quadratwurzel einer auf die nächste ganze Zahl gerundeten Zahl berechnen möchten, können Sie diese Funktion als schreiben

approxSqrt x = round (sqrt x)

Sie werden vielleicht auch erkennen, dass wir hier eigentlich zwei Funktionen nehmen und eine komplexere Funktion aufbauen, indem wir sie als Bausteine ​​verwenden.Wir brauchen jedoch eine Art Kleber, um sie zusammenzufügen, und dieser Kleber ist es (.):

approxSqrt = round . sqrt

Der Funktionskompositionsoperator ist also ein Kombinator von Funktionen – er kombiniert Funktionen, um neue Funktionen zu erstellen.Ein anderes Beispiel ist, dass Sie vielleicht jede Zeile einer Datei in eine Liste einlesen möchten.Sie könnten dies auf die offensichtliche Weise tun:

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

Aber!Was würden wir tun, wenn wir eine Funktion hätten, die eine Datei liest und den Inhalt als Strings zurückgibt?Dann könnten wir es tun

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

Wie sich herausstellt, haben wir eine Funktion, die eine Datei liest, und wir haben eine Funktion, die einen großen String akzeptiert und eine Liste der darin enthaltenen Zeilen zurückgibt.Wenn wir nur etwas Klebstoff hätten, um diese beiden Funktionen sinnvoll miteinander zu verbinden, könnten wir bauen readFileLines!Aber da es sich um Haskell handelt, ist dieser Kleber natürlich leicht verfügbar.

readFileLines = fmap lines . readFile

Hier verwenden wir zwei Kombinatoren!Wir benutzen das (.) von früher, und fmap ist tatsächlich auch ein sehr nützlicher Kombinator.Wir sagen, dass es eine reine Berechnung in die IO-Monade „hebt“, und was wir wirklich meinen, ist das lines hat die Typsignatur

lines :: String -> [String]

Aber fmap lines hat die Signatur

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

Also fmap ist nützlich, wenn Sie reine Berechnungen mit IO-Berechnungen kombinieren möchten.

---

Das waren nur zwei sehr einfache Beispiele.Wenn Sie mehr über Haskell lernen, werden Sie feststellen, dass Sie immer mehr Kombinatorfunktionen für sich selbst benötigen (und erfinden).Haskell ist sehr leistungsfähig in der Art und Weise, wie man Funktionen übernehmen und umwandeln, kombinieren, auf den Kopf stellen und dann zusammenfügen kann.Die Kleberstücke, die wir manchmal brauchen, wenn wir das tun, diese Stücke nennen wir Kombinatoren.

Answer 3

„Combinator“ ist in seiner Verwendung in Haskell nicht genau definiert.Es ist am korrektesten, es zu verwenden, um auf Funktionen zu verweisen, die andere Funktionen a la als Argumente annehmen Kombinatorrechnung aber in der Haskell-Terminologie wird es häufig überladen und bedeutet auch eine „Modifikations-“ oder „Kombinations“-Funktion, insbesondere von a Functor oder Monad.In diesem Fall könnte man sagen, ein Kombinator sei eine Funktion, die „eine Aktion oder einen Wert im Kontext ausführt und eine neue, geänderte Aktion oder einen neuen Wert im Kontext zurückgibt“.

Dein Beispiel, maybeIO wird oft genannt optional

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

und es hat einen kombinatorähnlichen Charakter, weil es die Berechnung übernimmt f a und modifiziert es allgemein, um Fehler in seinem Wert widerzuspiegeln.

Der Grund, warum diese Kombinatoren genannt werden, hängt auch mit ihrer Verwendung zusammen.Ein typischer Ort zum Sehen optional (und in der Tat, Alternative im Allgemeinen) befindet sich in Parser-Kombinator-Bibliotheken.Hier neigen wir dazu, einfache Parser mit simple zu erstellen Parserist wie

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

und dann „modifizieren“ wir ihr Verhalten mithilfe von „Kombinatoren“

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

Oftmals nennen wir auch Funktionen, die mehrere Funktionen kombinieren/Functors/Monads auch „Kombinatoren“, was mnemonisch vielleicht Sinn macht

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

Letztendlich geht es bei Kombinatoren jedoch mehr um die Absicht und Verwendung einer API als um ihre strenge Bezeichnung.Sie werden häufig Bibliotheken sehen, die aus „grundlegenden Teilen“ wie Funktionen oder aufgebaut sind satisfy die dann modifiziert und mit einer Reihe von „Kombinatoren“ kombiniert werden.Der Parser Das obige Beispiel ist ein typisches Beispiel, aber insgesamt handelt es sich um ein sehr häufiges Haskell-Muster.