Die Kategorie der Mengen ist sowohl kartesisch monoidal als auch kokartesisch monoidal. Die Arten der kanonischen Isomorphismen, die diese beiden monoidalen Strukturen bezeugen, sind nachstehend aufgeführt:
type x + y = Either x y
type x × y = (x, y)
data Iso a b = Iso { fwd :: a -> b, bwd :: b -> a }
eassoc :: Iso ((x + y) + z) (x + (y + z))
elunit :: Iso (Void + x) x
erunit :: Iso (x + Void) x
tassoc :: Iso ((x × y) × z) (x × (y × z))
tlunit :: Iso (() × x) x
trunit :: Iso (x × ()) x
Für die Zwecke dieser Frage definiere Alternative
ich einen laxen monoidalen Funktor von Hask unter dem Either
Tensor zu Hask unter dem (,)
Tensor (und nicht mehr):
class Functor f => Alt f
where
union :: f a × f b -> f (a + b)
class Alt f => Alternative f
where
nil :: () -> f Void
Die Gesetze sind nur die für einen laxen monoidalen Funktor.
Assoziativität:
fwd tassoc >>> bimap id union >>> union
=
bimap union id >>> union >>> fmap (fwd eassoc)
Linke Einheit:
fwd tlunit
=
bimap nil id >>> union >>> fmap (fwd elunit)
Rechte Einheit:
fwd trunit
=
bimap id nil >>> union >>> fmap (fwd erunit)
Hier Alternative
erfahren Sie, wie Sie die bekannteren Operationen für die Typklasse in Bezug auf die Kohärenzkarten der laxen monoidalen Funktorkodierung wiederherstellen können:
(<|>) :: Alt f => f a -> f a -> f a
x <|> y = either id id <$> union (Left <$> x, Right <$> y)
empty :: Alternative f => f a
empty = absurd <$> nil ()
Ich definiere Filterable
Funktoren als Oplax-Monoid- Funktoren von Hask unter dem Either
Tensor bis Hask unter dem (,)
Tensor:
class Functor f => Filter f
where
partition :: f (a + b) -> f a × f b
class Filter f => Filterable f
where
trivial :: f Void -> ()
trivial = const ()
Für seine Gesetze nur rückwärts laxe monoidale Funktorgesetze zu haben:
Assoziativität:
bwd tassoc <<< bimap id partition <<< partition
=
bimap partition id <<< partition <<< fmap (bwd eassoc)
Linke Einheit:
bwd tlunit
=
bimap trivial id <<< partition <<< fmap (bwd elunit)
Rechte Einheit:
bwd trunit
=
bimap id trivial <<< partition <<< fmap (bwd erunit)
Definieren von Standardfilter-y-Funktionen wie mapMaybe
und filter
in Bezug auf die oplaxe monoidale Funktorkodierung, die dem interessierten Leser als Übung überlassen werden:
mapMaybe :: Filterable f => (a -> Maybe b) -> f a -> f b
mapMaybe = _
filter :: Filterable f => (a -> Bool) -> f a -> f a
filter = _
Die Frage ist: Ist jeder Alternative
Monad
auch Filterable
?
Wir können tetris auf dem Weg zu einer Implementierung eingeben:
instance (Alternative f, Monad f) => Filter f
where
partition fab = (fab >>= either return (const empty), fab >>= either (const empty) return)
Aber ist diese Implementierung immer rechtmäßig? Ist es manchmal rechtmäßig (für eine formale Definition von "manchmal")? Beweise, Gegenbeispiele und / oder informelle Argumente wären alle sehr nützlich. Vielen Dank.
Filterable
Gesetze ziemlich schwach sind). @AsadSaeeduddin Erwägen Sie, einige interaktive Theorem-Beweisfähigkeiten zu erlernen, damit Sie die Mentalität "Verwendungstypen, nicht Ihr Gehirn" auch auf Beweise ausweiten können!Antworten:
Hier ein Argument, das Ihre schöne Idee weitgehend unterstützt.
Teil eins: mapMaybe
Mein Plan hier ist es, das Problem in Bezug auf neu zu formulieren, in der
mapMaybe
Hoffnung, dass dies uns zu einem vertrauten Boden bringt. Zu diesemEither
Zweck werde ich einige Dienstprogramme zum Jonglieren verwenden:(Ich habe die ersten drei Namen von relude und die vierte von Fehlern . Übrigens, Fehler Angebote
maybeToRight
undrightToMaybe
wienote
undhush
jeweils inControl.Error.Util
.)Wie Sie bemerkt haben,
mapMaybe
kann definiert werden in Bezug aufpartition
:Entscheidend ist, dass wir auch umgekehrt vorgehen können:
Dies legt nahe, dass es sinnvoll ist, Ihre Gesetze in Bezug auf neu zu formulieren
mapMaybe
. Mit den Identitätsgesetzen gibt uns dies eine gute Entschuldigung, um ganz zu vergessentrivial
:Was die Assoziativität betrifft, können wir das Gesetz verwenden
rightToMaybe
undleftToMaybe
in drei Gleichungen aufteilen, eine für jede Komponente, die wir aus den aufeinanderfolgenden Partitionen erhalten:Parametrizitätsmittel
mapMaybe
sind in Bezug auf dieEither
Werte, mit denen wir uns hier befassen, agnostisch . Unter diesen Umständen können wir unser kleines Arsenal anEither
Isomorphismen verwenden, um Dinge zu mischen und zu zeigen, dass [I] gleich [II] und [III] gleich [V] ist. Wir haben jetzt drei Gleichungen:Die Parametrizität ermöglicht es uns, das
fmap
in [I] zu schlucken :Das ist jedoch einfach ...
... , die zur Erhaltung / Identität Gesetz von entspricht witherable ‚s
Filterable
:Das
Filterable
hat auch ein Kompositionsgesetz:Können wir dies auch aus unseren Gesetzen ableiten? Beginnen wir mit [III] und lassen wir noch einmal die Parametrizität ihre Arbeit machen. Dieser ist kniffliger, also schreibe ich ihn vollständig auf:
In die andere Richtung:
(Hinweis: Während dies
maybeToRight () . rightToMaybe :: Either a b -> Either () b
nichtid
der Fall ist , werden in der obigen Ableitung die linken Werte ohnehin verworfen. Es ist also fair, sie so zu streichen, als ob sie es wärenid
.)Somit [III] ist äquivalent zu der Zusammensetzung Gesetz witherable ist
Filterable
.An dieser Stelle können wir das Kompositionsgesetz verwenden, um mit [IV] umzugehen:
Dies reicht aus, um zu zeigen, dass Ihre Klassenmengen eine gut etablierte Formulierung von sind
Filterable
, was ein sehr schönes Ergebnis ist. Hier ist eine Zusammenfassung der Gesetze:Wie die verwelkten Dokumente vermerken, sind dies Funktorgesetze für einen Funktor von Kleisli Vielleicht bis Hask .
Teil zwei: Alternative und Monade
Jetzt können wir Ihre eigentliche Frage beantworten, die sich mit alternativen Monaden befasste. Ihre vorgeschlagene Implementierung von
partition
war:Nach meinem breiteren Plan werde ich zur
mapMaybe
Präsentation wechseln :Und so können wir definieren:
Oder in einer punktfreien Schreibweise:
Ein paar Absätze oben habe ich bemerkt
Filterable
, dass die Gesetze besagen, dass diesmapMaybe
die Morphismus-Zuordnung eines Funktors von Kleisli Vielleicht zu Hask ist . Da die Zusammensetzung von functors ist ein Funktors, und(=<<)
ist die morphism Abbildung eines Funktors von Kleisli f zu Hask ,(maybe empty return .)
die morphism Abbildung eines Funktors entfernt, Vielleicht Kleisli bis f Kleisli reicht fürmapMaybeAM
rechtmäßig. Die relevanten Funktorgesetze sind:Dieses Identitätsgesetz gilt, also konzentrieren wir uns auf die Komposition:
Daher
mapMaybeAM
ist rechtmäßig, wennmaybe empty return . g =<< empty = empty
für jedeng
. Wenn nunempty
definiert istabsurd <$> nil ()
, wie Sie es hier getan haben, können wir diesf =<< empty = empty
für jeden beweisenf
:Wenn
empty
es wirklich leer ist (wie es sein muss, angesichts der Definition, die wir hier verwenden), gibt es intuitiv keine Werte,f
auf die angewendet werden kann, undf =<< empty
kann daher nur zu etwas führenempty
.Ein anderer Ansatz wäre hier die Untersuchung der Interaktion von
Alternative
undMonad
Klassen. Zufällig gibt es eine Klasse für alternative Monaden :MonadPlus
. DementsprechendmapMaybe
könnte ein neu gestaltetes so aussehen:Zwar gibt es unterschiedliche Meinungen darüber, für welche Gesetze am besten geeignet ist
MonadPlus
, aber eines der Gesetze, gegen die niemand Einwände zu erheben scheint, ist ...... was genau die Eigenschaft ist, über die
empty
wir oben einige Absätze besprochen haben. Die Rechtmäßigkeit vonmmapMaybe
folgt unmittelbar aus dem linken Nullgesetz.(Übrigens
Control.Monad
liefertmfilter :: MonadPlus m => (a -> Bool) -> m a -> m a
, was mit dem übereinstimmt, wasfilter
wir mit definieren könnenmmapMaybe
.)Zusammenfassend:
Ja, die Implementierung ist rechtmäßig. Diese Schlussfolgerung hängt davon ab
empty
, ob es tatsächlich leer ist, wie es sollte, oder von der relevanten alternativen Monade, die demMonadPlus
Gesetz des linken Nullpunkts folgt , was auf fast dasselbe hinausläuft.Hervorzuheben ist, dass dies
Filterable
nicht subsumiert wirdMonadPlus
, wie wir anhand der folgenden Gegenbeispiele veranschaulichen können:ZipList
: filterbar, aber keine Monade. DieFilterable
Instanz ist dieselbe wie die für Listen, auch wenn dieAlternative
andere unterschiedlich ist.Map
: filtrierbar, aber weder monad noch anwendbar. In der TatMap
kann nicht einmal anwendbar sein, weil es keine vernünftige Implementierung von gibtpure
. Es hat jedoch seine eigenenempty
.MaybeT f
: Während seineMonad
undAlternative
Instanzenf
eine Monade sein müssen und eine isolierteempty
Definition zumindest eine Instanz erfordern würdeApplicative
,Filterable
erfordert die Instanz nurFunctor f
(alles wird filterbar, wenn Sie eineMaybe
Ebene hineinschieben).Teil drei: leer
An diesem Punkt könnte man sich noch fragen, wie groß die Rolle
empty
ist odernil
wirklich spieltFilterable
. Es ist keine Klassenmethode, und dennoch scheinen die meisten Instanzen eine vernünftige Version davon zu haben.Das eine, dessen wir uns sicher sein können, ist, dass, wenn der filterbare Typ überhaupt Einwohner hat, mindestens einer von ihnen eine leere Struktur ist, weil wir immer jeden Einwohner nehmen und alles herausfiltern können:
Die Existenz von
chop
bedeutet jedoch nicht, dass es einen einzelnennil
leeren Wert gibt, oder dass dieschop
immer das gleiche Ergebnis ergibt. Stellen Sie sich zum Beispiel vor,MaybeT IO
wessenFilterable
Instanz als eine Möglichkeit angesehen werden könnte, Ergebnisse vonIO
Berechnungen zu zensieren . Die Instanz ist vollkommen rechtmäßig, obwohlchop
sie unterschiedlicheMaybeT IO Void
Werte erzeugen kann , die willkürlicheIO
Auswirkungen haben.Abschließend haben Sie auf die Möglichkeit hingewiesen, mit starken monoidalen Funktoren zu arbeiten, so dass
Alternative
undFilterable
durch Herstellung vonunion
/partition
undnil
/trivial
Isomorphismen verbunden sind. Das Habenunion
undpartition
als gegenseitige Umkehrung ist denkbar, aber ziemlich einschränkend, daunion . partition
einige Informationen über die Anordnung der Elemente für einen großen Teil der Instanzen verworfen werden. Der andere Isomorphismustrivial . nil
ist trivial, abernil . trivial
insofern interessant, als er impliziert, dass es nur einen einzigenf Void
Wert gibt, der für einen beträchtlichen Anteil vonFilterable
Instanzen gilt. Es kommt vor, dass es eineMonadPlus
Version dieser Bedingung gibt. Wenn wir das verlangen, für jedenu
...... und dann ersetzen Sie die
mmapMaybe
aus Teil zwei, wir bekommen:Diese Eigenschaft ist als das Recht auf Recht Null bekannt
MonadPlus
, obwohl es gute Gründe gibt, ihren Status als Gesetz dieser bestimmten Klasse anzufechten.quelle
Monad
undAlternative
Instanzen"?MonadPlus
(möglicherweise durch die nahezu semirische Charakterisierung gesehen ) stellt eine Verbindung zwischenAlternative
undMonad
der schmucklosen "monoidalen Funktor von Hask-mit-(,)
zu-Hask-mit-Either
" Charakterisierung nicht her. Auf jeden Fall frage ich mich immer noch, ob hier etwas Tieferes auftauchtempty
, das der bloßenFilterable
Definition fremd erscheint und sich dennoch recht passend anfühlt.empty
ist Teil der Definition vonAlternative
. DasAlternative
undFilterable
kann enger miteinander verbunden werden, indem verlangt wird, dassunion
das Gegenteil vonpartition
(und umgekehrt) undtrivial
das Gegenteil vonnil
(und umgekehrt) ist. Dies wird als "starker monoidaler Funktor" bezeichnet.Filterable
Fälle wäre diese Eigenschaft zu stark, dapartition
sie verlustbehaftet sein kann. Zum Beispiel(union . partition) [L 7, R 2, L 1, R 6]
ist[L 7, L 1, R 2, R 6]
. Dertrivial
/nil
Teil würde letztendlich darauf hinauslaufen, nur einenf Void
Wert zu haben, was zugänglicher erscheint. InMonadPlus
Begriffen entspricht es dem umstrittenen Recht-Null-Gesetz,m >> mzero = mzero
das beispielsweise für Listen gilt, nicht jedoch für Parser.empty
. Dies ist möglicherweise das letzte Update :)