Was können Pfeile tun, die Monaden nicht können?

Question

Pfeile scheinen in der Haskell-Community an Popularität zu gewinnen, aber es scheint mir, als wären Monaden mächtiger. Was erreicht man, wenn man Pfeile benutzt? Warum können nicht stattdessen Monaden verwendet werden?

Answer 1

Ich habe es immer schwierig gefunden, das Problem in diesen Begriffen zu sehen: was man mit Pfeilen gewinnt. Wie andere Kommentatoren erwähnt haben, kann jede Monade trivialerweise in einen Pfeil verwandelt werden. So kann eine Monade alle pfeilförmigen Dinge tun. Wir können jedoch Pfeile machen, die keine Monaden sind. Das heißt, wir können Typen erstellen, die diese Pfeil-y-Dinge tun können, ohne dass sie eine monadische Bindung unterstützen. Es mag nicht so aussehen, aber die monadische Bindefunktion ist eigentlich eine ziemlich restriktive (daher mächtige) Operation, die viele Typen disqualifiziert.

Siehe, um Bind zu unterstützen, müssen Sie in der Lage sein zu behaupten, dass unabhängig vom Eingabetyp, was herauskommen wird, in der Monade verpackt wird.

(>>=) :: forall a b. m a -> (a -> m b) -> m b 

Aber, wie wir binden für einen Typ wie data Foo a = F Bool a Sicher definieren würde, können wir ein Foo ein mit fremden kombinieren könnte, aber wie würden wir die Bools kombinieren. Stellen Sie sich vor, dass der Bool beispielsweise angibt, ob sich der Wert des anderen Parameters geändert hat oder nicht. Wenn ich a = Foo False whatever habe und ich es in eine Funktion binde, habe ich keine Ahnung, ob sich diese Funktion ändern wird oder nicht whatever. Ich kann keine Bindung schreiben, die den Bool korrekt setzt. Dies wird oft als Problem statischer Metainformationen bezeichnet. Ich kann die gebundene Funktion nicht überprüfen, um zu bestimmen, ob sie geändert wird oder nicht whatever.

Es gibt mehrere andere Fälle wie diese: Typen, die Mutating-Funktionen darstellen, Parser, die früh beenden können usw. Aber die Grundidee ist folgende: Monaden setzen einen High-Balken, den nicht alle Typen löschen können. Pfeile ermöglichen es Ihnen, Typen (die diesen hohen, verbindlichen Standard unterstützen können oder nicht) auf leistungsstarke Weise zusammenzusetzen, ohne die Bindung zu erfüllen. Natürlich verlieren Sie etwas von der Macht der Monaden.

Moral der Geschichte: Es gibt nichts, was ein Pfeil tun kann, dass Monade nicht kann, weil eine Monade immer in einen Pfeil gemacht werden kann. Manchmal können Sie Ihre Typen jedoch nicht zu Monaden machen, aber Sie möchten immer noch zulassen, dass sie den größten Teil der kompositorischen Flexibilität und Kraft von Monaden haben.

Viele dieser Ideen durch die hervorragende Understanding Haskell Arrows

Answer 2

Die Frage ist nicht ganz richtig. Es ist, als würde man fragen, warum man Orangen statt Äpfel essen sollte, da Äpfel überall nahrhafter erscheinen.

Pfeile, wie Monaden, sind eine Möglichkeit, Berechnungen auszudrücken, aber sie müssen einem anderen Satz von laws folgen. Insbesondere neigen die Gesetze dazu, die Pfeile schöner zu machen, wenn man funktionsähnliche Dinge hat.

Das Haskell Wiki listet einen few introductions zu Pfeilen auf. Insbesondere ist die Wikibook eine nette Einführung auf hohem Niveau, und die tutorial von John Hughes ist ein guter Überblick über die verschiedenen Arten von Pfeilen.

Für ein Beispiel aus der Praxis vergleichen Sie this tutorial, die die pfeilbasierte Schnittstelle von Hakyll 3 verwendet, mit ungefähr the same thing in Hakyll 4's monadbasierter Schnittstelle.

Answer 3

Jede Monade führt zu einem Pfeil

newtype Kleisli m a b = Kleisli (a -> m b) 
instance Monad m => Category (Kleisli m) where 
    id = Kleisli return 
    (Kleisli f) . (Kleisli g) = Kleisli (\x -> (g x) >>= f) 
instance Monad m => Arrow (Kleisli m) where 
    arr f = Kleisli (return . f) 
    first (Kleisli f) = Kleisli (\(a,b) -> (f a) >>= \fa -> return (fa,b)) 

Aber gibt es Pfeile, die nicht Monaden sind. So gibt es Pfeile, die Dinge tun, die man mit Monaden nicht machen kann. Ein gutes Beispiel ist der Pfeil Transformator einige statische Informationen

data StaticT m c a b = StaticT m (c a b) 
instance (Category c, Monoid m) => Category (StaticT m c) where 
    id = StaticT mempty id 
    (StaticT m1 f) . (StaticT m2 g) = StaticT (m1 <> m2) (f . g) 
instance (Arrow c, Monoid m) => Arrow (StaticT m c) where 
    arr f = StaticT mempty (arr f) 
    first (StaticT m f) = StaticT m (first f) 

dieser Pfeil tranformer ist nützlich hinzuzufügen, weil es verwendet werden kann, den Überblick über statische Eigenschaften eines Programms zu halten. Sie können dies beispielsweise verwenden, um Ihre API zu instrumentieren, um statistisch zu messen, wie viele Anrufe Sie tätigen.

Answer 4

Nun inspiriert wurden, werde ich hier etwas betrügen, indem die Frage von Arrow zu Applicative ändern. Viele der gleichen Motive gelten, und ich kenne Anwendungen besser als Pfeile. (Und in der Tat, every Arrow is also an Applicative aber not vice-versa, so bin ich es nur nach unten nehmen ein bisschen weiter den Hang hinunter zu Functor.)

Wie jedes Monad ist ein Arrow, jeder Monad ist auch ein Applicative. Es gibt Applicatives, die nicht Monad sind (z. B. ZipList), also ist das eine mögliche Antwort.

Aber nehmen wir an, dass es sich um einen Typ handelt, der sowohl eine Monad Instanz als auch eine Applicative zulässt. Warum könnten wir irgendwann die Applicative Instanz anstelle von Monad verwenden? Da Applicative weniger leistungsfähig ist, und das kommt mit Vorteilen:

1. Es gibt Dinge, die wir wissen, dass die Monad tun kann, die die Applicative nicht. Wenn wir zum Beispiel die Applicative -Instanz von IO verwenden, um eine zusammengesetzte Aktion aus einfacheren zusammenzusetzen, darf keine der Aktionen, die wir verfassen, die Ergebnisse der anderen verwenden. Alles, was die Anwendung IO tun kann, ist, die Komponentenaktionen auszuführen und ihre Ergebnisse mit reinen Funktionen zu kombinieren.
2. Applicative Typen können geschrieben werden, so dass wir eine mächtige statische Analyse der Aktionen ausführen können, bevor Sie sie ausführen. So können Sie ein Programm schreiben, das vor der Ausführung es eine Applicative Aktion prüft, findet heraus, was es tun wird, und verwendet diese Leistung zu verbessern, sagen Sie dem Benutzer, was getan werden geht usw.

Als Beispiel von der ersten, habe ich gearbeitet, um eine Art von OLAP Berechnungssprache mit Applicative s zu entwerfen. Der Typ gibt eine Monad Instanz, aber ich habe es bewusst vermieden, dass, weil ich möchte, dass die Abfragen weniger leistungsfähiger als was Monad würde erlauben würde. Applicative bedeutet, dass jede Berechnung eine vorhersagbare Anzahl von Abfragen erreicht.

Als Beispiel für letztere, ich werde ein Spielzeugbeispiel von my still-under-development operational Applicative library verwenden. Wenn Sie die Reader Monade als operative Applicative Programm statt zu schreiben, können Sie die resultierenden Reader s untersuchen, um zu zählen, wie oft sie nutzen die ask Betrieb:

{-# LANGUAGE GADTs, RankNTypes, ScopedTypeVariables #-} 

import Control.Applicative.Operational 

-- | A 'Reader' is an 'Applicative' program that uses the 'ReaderI' 
-- instruction set. 
type Reader r a = ProgramAp (ReaderI r) a 

-- | The only 'Reader' instruction is 'Ask', which requires both the 
-- environment and result type to be @r@. 
data ReaderI r a where 
    Ask :: ReaderI r r 

ask :: Reader r r 
ask = singleton Ask 

-- | We run a 'Reader' by translating each instruction in the instruction set 
-- into an @r -> a@ function. In the case of 'Ask' the translation is 'id'. 
runReader :: forall r a. Reader r a -> r -> a 
runReader = interpretAp evalI 
    where evalI :: forall x. ReaderI r x -> r -> x 
      evalI Ask = id 

-- | Count how many times a 'Reader' uses the 'Ask' instruction. The 'viewAp' 
-- function translates a 'ProgramAp' into a syntax tree that we can inspect. 
countAsk :: forall r a. Reader r a -> Int 
countAsk = count . viewAp 
    where count :: forall x. ProgramViewAp (ReaderI r) x -> Int 
      -- Pure :: a -> ProgamViewAp instruction a 
      count (Pure _) = 0 
      -- (:<**>) :: instruction a 
      --   -> ProgramViewAp instruction (a -> b) 
      --   -> ProgramViewAp instruction b 
      count (Ask :<**> k) = succ (count k) 

Wie man am besten wie ich sie verstehe, kann man nicht countAsk schreiben wenn Sie Reader als Monad implementieren. (Mein Verständnis kommt from asking right here in Stack Overflow, ich werde hinzufügen.)

Das gleiche Motiv ist eigentlich eine der Ideen hinter Arrow s.Eines der großen motivierenden Beispiele für Arrow war ein Parser-Kombinator-Design, das "statische Informationen" verwendet, um eine bessere Leistung als monadische Parser zu erhalten. Was sie mit "statischen Informationen" meinen, ist mehr oder weniger dasselbe wie in meinem Reader Beispiel: Es ist möglich, eine Arrow Instanz zu schreiben, wo die Parser genau wie meine Reader s geprüft werden können. Dann kann die Parsing-Bibliothek vor dem Ausführen eines Parsers prüfen, ob sie im Voraus vorhersagen kann, dass ein Fehler auftritt, und sie in diesem Fall überspringen.

In einem der direkten Kommentare zu Ihrer Frage erwähnt Jberryman, dass Pfeile tatsächlich Popularität verlieren können. Ich würde hinzufügen, dass, wie ich es sehe, Applicative ist, was Pfeile Popularität verlieren zu.

---

Referenzen:

• Paolo Capriotti & Ambrus Kaposi, "Free Applicative Functors". Sehr empfehlenswert.
• Gergo Erdi, "Static analysis with Applicatives". Inspirational, aber ich es schwer zu folgen ...