Warum werden Instanzen nur von ihren Köpfen abgeglichen?

Question

Ich werde mit der Einführung eines konkreten Problems (StackOverflow Jungs wie folgt) beginnen. Sagen Sie bitte einen einfachen Typ definieren

data T a = T a 

Dieser Typ ist ein Functor, Applicative und ein Monad. Ignorieren automatische Ableitung, um diese Instanzen zu bekommen, müssen Sie jede von ihnen zu schreiben, auch wenn Applicative bedeutet Functor. Mehr als das, könnte ich eine ziemlich starke Bedingung definiert eine Klasse wie diese

class Wrapper f where 
    wrap :: a -> f a 
    unwrap :: f a -> a 

Dies ist und es bedeutet, auf jeden Fall Monad, aber ich kann

instance Wrapper f => Monad f where 
    return = wrap 
    fa >>= f = f $ unwrap fa 

weil dies nicht schreiben, aus irgendeinem Grunde bedeutet "alles ist ein Monad (alle f), nur wenn es ein Wrapper ist", anstatt "alles das ist ein Wrapper ist ein Monad".

Ebenso können Sie die Monad a => Applicative a und Applicative a => Functor a Instanzen nicht definieren.

Eine andere Sache, die Sie nicht tun können (die nur wahrscheinlich verwandt ist, weiß ich wirklich nicht) ist eine Klasse eine Oberklasse von einer anderen Klasse zu sein und eine Standardimplementierung der Unterklasse bereitzustellen. Sicher, es ist großartig, dass class Applicative a => Monad a, aber es ist viel weniger groß, dass ich noch dieInstanz definieren muss, bevor ich die Monad eine definieren kann.

Dies ist keine Tirade. Ich habe viel geschrieben, weil sonst das schnell als "zu breit" oder "unklar" markiert würde. Die Frage läuft auf den Titel hinaus. Ich weiß (zumindest bin ich mir ziemlich sicher), dass es einen theoretischen Grund dafür gibt, also frage ich mich, was genau die Vorteile hier sind.

Als eine Unterfrage möchte ich fragen, ob es praktikable Alternativen gibt, die immer noch alle (oder die meisten) dieser Vorteile behalten, aber erlauben, was ich geschrieben habe.

Zusatz: Ich vermute, eine der Antworten könnte etwas entlang der Linien sein „Was ist, wenn mein Typ ein Wrapper ist, aber ich will nicht die Monad Instanz verwenden, dass das bedeutet?“. Dazu frage ich, warum konnte der Compiler nicht einfach den spezifischsten auswählen? Wenn es einen instance Monad MyType gibt, ist es sicherlich spezifischer als instance Wrapper a => Monad a.

Answer 1

Hier werden viele Fragen zusammengefasst. Aber nehmen wir sie nacheinander.

Erstens: Warum betrachtet der Compiler bei der Auswahl der zu verwendenden Instanz nicht Instanzkontexte? Dies dient dazu, die Instanzsuche effizient zu halten. Wenn der Compiler nur Instanzen berücksichtigen soll, deren Instanz-Heads erfüllt sind, müssen Sie Ihren Compiler im Wesentlichen dazu veranlassen, eine Back-Tracking-Suche zwischen allen möglichen Instanzen durchzuführen. An diesem Punkt haben Sie 90% von Prolog implementiert. Wenn Sie andererseits die Haltung einnehmen (wie Haskell), dass Sie nur bei der Auswahl der zu verwendenden Instanz nur Instanzköpfe betrachten und dann einfach den Instanzkontext erzwingen, gibt es kein Backtracking: in jedem Moment gibt es nur Eine Wahl, die Sie treffen können.

Weiter: Warum können Sie nicht eine Klasse eine Oberklasse von einer anderen Klasse haben und eine Standardimplementierung der Unterklasse bereitstellen? Für diese Einschränkung gibt es keinen grundlegenden Grund, daher bietet GHC diese Funktion als Erweiterung an.Man könnte so etwas schreiben:

{-# LANGUAGE DefaultSignatures #-} 
class Applicative f where 
    pure :: a -> f a 
    (<*>) :: f (a -> b) -> f a -> f b 

    default pure :: Monad f => a -> f a 
    default (<*>) :: Monad f => f (a -> b) -> f a -> f b 
    pure = return 
    (<*>) = ap 

Dann, wenn Sie einen instance Monad M where ... zur Verfügung gestellt hatte, man einfach instance Applicative M ohne where Klausel schreiben könnte und haben es einfach zu arbeiten. Ich weiß nicht wirklich, warum das in der Standardbibliothek nicht gemacht wurde.

Last: Warum kann der Compiler nicht viele Instanzen zulassen und nur die spezifischste auswählen? Die Antwort auf diese Frage ist eine Mischung aus den beiden vorherigen: Es gibt sehr gute Gründe, warum dies nicht gut funktioniert, aber GHC bietet trotzdem eine Erweiterung, die das tut. Der Grund, warum dies nicht gut funktioniert, ist, dass die spezifischste Instanz für einen gegebenen Wert nicht vor der Laufzeit bekannt sein kann. Die Antwort von GHC ist für polymorphe Werte, die spezifischste zu wählen, die mit dem gesamten verfügbaren Polymorphismus kompatibel ist. Wenn später das Ding Ding monomorphisiert wird, gut, schade für dich. Das hat zur Folge, dass einige Funktionen bei einigen Daten mit einer Instanz arbeiten und andere bei denselben Daten mit einer anderen Instanz arbeiten können. Dies kann zu sehr kleinen Fehlern führen. Wenn Sie nach all dieser Diskussion immer noch denken, dass das eine gute Idee ist, und sich weigern, aus den Fehlern anderer zu lernen, können Sie IncoherentInstances einschalten.

Ich denke, das deckt alle Fragen ab.

Answer 2

Konsistenz und separate Kompilierung.

Wenn wir zwei Instanzen, deren Köpfe beiden Spiele haben, aber haben unterschiedliche Einschränkungen, sagen:

-- File: Foo.hs 

instance Monad m => Applicative m 
instance   Applicative Foo 

Dann entweder das gilt Code eine Applicative Instanz für Foo produzieren, oder es ist ein Fehler produziert zwei verschiedene Applicative Instanzen für Foo. Welcher ist es hängt davon ab, ob eine Monad-Instanz für Foo existiert. Das ist ein Problem, weil es schwierig ist zu garantieren, dass das Wissen darüber, ob Monad Foo gilt, es zum Compiler schaffen wird, wenn es dieses Modul kompiliert. Ein anderes Modul (zB Bar.hs) kann eine Monad Instanz für Foo erzeugen Wenn Foo.hs dieses Modul nicht importiert (auch nicht indirekt), wie soll der Compiler dann wissen? Schlimmer noch, wir können ändern, ob dies ein Fehler oder eine gültige Definition ist, indem Sie ändern, ob wir später Bar.hs in das endgültige Programm oder nicht!

Damit dies funktioniert, müssen wir wissen, dass alle im finalen kompilierten Programm vorhandenen Instanzen in jedem Modul sichtbar sind, was zu der Schlussfolgerung führt, dass jedes Modul eine Abhängigkeit von jedem anderen Modul ist Das Modul importiert die anderen. Man müsste ziemlich weit gehen, um eine vollständige Programmanalyse zu benötigen, um ein solches System zu unterstützen, was das Verbreiten vorkompilierter Bibliotheken schwierig bis unmöglich macht.

Die einzige Möglichkeit, dies zu vermeiden, ist, dass GHC niemals Entscheidungen auf der Basis negativer Informationen trifft. Sie können keine Instanz basierend auf der nicht -Erfahrung einer anderen Instanz auswählen.

Das bedeutet, dass die Einschränkungen für eine Instanz für die Instanzauflösung ignoriert werden müssen.Sie müssen eine Instanz auswählen, unabhängig davon, ob die Einschränkungen gelten. Wenn dies mehr als eine möglicherweise anwendbare Instanz übrig lässt, dann würden Sie negative Informationen benötigen (nämlich dass alle außer einer von ihnen Einschränkungen erfordern, die nicht gelten), um den Code als gültig zu akzeptieren.

Wenn Sie nur eine Instanz haben, die sogar ein Kandidat ist, und Sie können keinen Beweis für seine Einschränkungen sehen, können Sie den Code akzeptieren, indem Sie die Einschränkungen an die Stelle der Instanz übergeben (wir können uns darauf verlassen diese Information zu anderen Modulen, weil sie diese importieren müssen, wenn auch nur indirekt); Wenn diese Positionen eine erforderliche Instanz auch nicht sehen können, werden sie einen entsprechenden Fehler bezüglich einer nicht erfüllten Einschränkung erzeugen.

Indem wir die Einschränkungen ignorieren, stellen wir sicher, dass ein Compiler korrekte Entscheidungen über Instanzen treffen kann, auch wenn er nur von anderen Modulen weiß, die er importiert (transitiv); es muss nicht über alles wissen, was in jedem anderen Modul definiert ist, um zu wissen, welche Einschränkungen nicht halten.