Hilfe beim Schreiben der "Colist Monad" (Übung aus einem Idioms Intro-Papier)

Hm. Ich kann nicht anders, als zu denken, dass diese Übung ein bisschen unfair ist, wie dargestellt.

  

Übung 4 (die colist Monade)

     

Obwohl repeat und zapp nicht die return und ap der normalen Monad [] Instanz sind,   Sie sind nichtsdestoweniger die return und ap einer alternativen Monade, besser geeignet für   die koinduktive Interpretation von [] . Was ist die join :: [[x]] → [x] dieser Monade?

     

Kommentieren Sie die relative Effizienz der ap dieser Monade und unserer zapp .

Erstens bin ich ziemlich sicher, dass die fragliche Monad-Instanz nicht gültig ist für [] im Allgemeinen . Wenn sie "die koinduktive Interpretation" sagen, nehme ich an, dass sich dies auf unendliche Listen bezieht. Die Instanz ist zwar in bestimmten Fällen für endliche Listen gültig, nicht aber für beliebige Listen im Allgemeinen.

Also das ist dein erster, sehr allgemeiner Hinweis - warum würde eine Monaden-Instanz nur für bestimmte Listen gültig sein, besonders für unendliche Listen?

Hier ist Ihr zweiter Hinweis: fmap und return sind trivial angesichts anderer Definitionen, die früher in der Arbeit erwähnt wurden. Du hast bereits return ; fmap ist nur geringfügig weniger offensichtlich.

Darüber hinaus hat (>>=) eine einfache Implementierung in Bezug auf die anderen Funktionen, wie bei jedem Monad , was join als den Kern der Sache übrig lässt. In den meisten Fällen ist (>>=) natürlicher für die Programmierung mit, aber join ist eher konzeptionell fundamental und in diesem Fall, denke ich, einfacher zu analysieren. Also empfehle ich, daran zu arbeiten und vergiss (>>=) für jetzt. Sobald Sie eine Implementierung haben, können Sie (>>=) rekonstruieren und die Monad-Gesetze überprüfen, um sicherzustellen, dass alles ordnungsgemäß funktioniert.

Nehmen wir einmal an, Sie hätten fmap zur Verfügung, aber sonst nichts. Mit Werten vom Typ [a -> b] und [a] können Sie sie kombinieren, um etwas vom Typ [[b]] zu erhalten. Der Typ von join ist hier [[a]] -> [a] . Wie könnten Sie join schreiben, so dass Sie hier das gleiche Ergebnis erhalten, als würden Sie zapp für die ursprünglichen Werte verwenden? Beachten Sie, dass die Frage nach der relativen Effizienz ebenso wie eine Frage ein Hinweis auf die Implementierung ist.

Ich dachte nur, ich sollte klarstellen, dass die Version mit Übungen und "Idiomen" im Titel ein eher früherer Entwurf der Arbeit ist, der schließlich in JFP erschien. Zu dieser Zeit dachte ich fälschlicherweise, dass Colisten (worunter ich möglicherweise unendliche, möglicherweise endliche Listen verstehe) eine Monade in einer Weise sind, die zapp entspricht: Es gibt einen plausiblen Kandidaten für den Join (auf den in anderen Antworten angespielt wird), aber Jeremy Gibbons war so freundlich, uns darauf hinzuweisen, dass es die Monadengesetze nicht erfüllt. Die Gegenbeispiele umfassen "zerlumpte" Listen von Listen mit unterschiedlichen endlichen Längen. Dementsprechend haben wir im JFP-Artikel korrigiert. (Wir waren ziemlich glücklich darüber, weil wir gerne anwendungsbezogene Funktoren finden, deren (& lt; * & gt;) nicht der Ap einer Monade ist.)

Die notwendigerweise unendlichen Listen (d. h. streams ) bilden tatsächlich durch Ausschließen der zerlumpten Fälle eine Monade, deren Ap sich wie zapp verhält. Für einen Hinweis, beachte, dass Stream x isomorph zu Nat ist - & gt; x.

Ich entschuldige mich für die Verwirrung. Es ist manchmal gefährlich, alte, unvollständige Entwürfe (voller Fehler) im Web liegen zu lassen (ha ha).

Die minimale vollständige Definition einer Monade ist entweder fmap + return + join oder return + (>>=) . Sie können das eine mit dem anderen implementieren:

Nun kann die Implementierung von ap in join und fmap umgeschrieben werden:

In der Übung wird die Semantik von fmap und return und ap angegeben. Der Rest wird offensichtlich, sobald Sie ein Beispiel untersuchen: