Sind alle Behälter mit fester Größe starke monoidale Funktoren und / oder umgekehrt?

Das Applicative Typklasse repräsentiert laxe monoidale Funktoren, die die kartesische monoidale Struktur in der Kategorie der typisierten Funktionen beibehalten.

Mit anderen Worten, angesichts der kanonischen Isomorphismen, (,)die eine monoidale Struktur bilden:

-- Implementations left to the motivated reader
assoc_fwd :: ((a, b), c) -> (a, (b, c))
assoc_bwd :: (a, (b, c)) -> ((a, b), c)

lunit_fwd :: ((), a) -> a
lunit_bwd :: a -> ((), a)

runit_fwd :: (a, ()) -> a
runit_bwd :: a -> (a, ())

Die Typklasse und ihre Gesetze können äquivalent so geschrieben werden:

class Functor f => Applicative f
  where
  zip :: (f a, f b) -> f (a, b)
  husk :: () -> f ()

-- Laws:

-- assoc_fwd >>> bimap id zip >>> zip
-- =
-- bimap zip id >>> zip >>> fmap assoc_fwd

-- lunit_fwd
-- =
-- bimap husk id >>> zip >>> fmap lunit_fwd

-- runit_fwd
-- =
-- bimap id husk >>> zip >>> fmap runit_fwd

Man könnte sich fragen, wie ein Funktor aussehen könnte, der in Bezug auf dieselbe Struktur oplax monoidal ist:

class Functor f => OpApplicative f
  where
  unzip :: f (a, b) -> (f a, f b)
  unhusk :: f () -> ()

-- Laws:

-- assoc_bwd <<< bimap id unzip <<< unzip
-- =
-- bimap unzip id <<< unzip <<< fmap assoc_bwd

-- lunit_bwd
-- =
-- bimap unhusk id <<< unzip <<< fmap lunit_bwd

-- runit_bwd
-- =
-- bimap id unhusk <<< unzip <<< fmap runit_bwd

Wenn wir über die Typen nachdenken, die an den Definitionen und Gesetzen beteiligt sind, wird die enttäuschende Wahrheit offenbart; OpApplicativeist keine spezifischere Einschränkung als Functor:

instance Functor f => OpApplicative f
  where
  unzip fab = (fst <$> fab, snd <$> fab)
  unhusk = const ()

Obwohl jeder ApplicativeFunktor (wirklich jeder Functor) trivial ist OpApplicative, gibt es nicht unbedingt eine schöne Beziehung zwischen den ApplicativeNachlässigkeiten und OpApplicativeOplaxitäten. So können wir nach starken monoidalen Funktoren für die kartesische monoidale Struktur suchen :

class (Applicative f, OpApplicative f) => StrongApplicative f

-- Laws:
-- unhusk . husk = id
-- husk . unhusk = id
-- zip . unzip = id
-- unzip . zip = id

Das erste Gesetz oben ist trivial, da der einzige Bewohner des Typs () -> ()die Identitätsfunktion ist ().

Die verbleibenden drei Gesetze und damit die Unterklasse selbst sind jedoch nicht trivial. Insbesondere ist nicht jeder Applicativeeine rechtmäßige Instanz dieser Klasse.

Hier sind einige ApplicativeFunktoren, für die wir rechtmäßige Fälle deklarieren können StrongApplicative:

• Identity
• VoidF
• (->) r
• Monoid m => (,) m (siehe Antworten)
• Vec (n :: Nat)
• Stream (unendlich)

Und hier sind einige Applicatives, für die wir nicht können:

• []
• Either e
• Maybe
• NonEmptyList

Das Muster hier legt nahe, dass die StrongApplicativeKlasse in gewissem Sinne die FixedSizeKlasse ist, wobei "feste Größe" ^* bedeutet, dass die Vielzahl ^** der Einwohner aeines Bewohners vonf a festgelegt ist.

Dies kann als zwei Vermutungen angegeben werden:

• Jeder, Applicativeder einen Container "fester Größe" von Elementen seines Typarguments darstellt, ist eine Instanz vonStrongApplicative
• Es StrongApplicativegibt keine Instanz von , in der die Anzahl der Vorkommen avariieren kann

Kann sich jemand Gegenbeispiele vorstellen, die diese Vermutungen widerlegen, oder überzeugende Argumente, die zeigen, warum sie wahr oder falsch sind?

* Mir ist klar, dass ich das Adjektiv "feste Größe" nicht richtig definiert habe. Leider ist die Aufgabe etwas kreisförmig. Ich kenne keine formale Beschreibung eines Containers mit "fester Größe" und versuche, einen zu finden. StrongApplicativeist mein bisher bester Versuch.

Um zu beurteilen, ob dies eine gute Definition ist, brauche ich etwas, mit dem ich sie vergleichen kann. Angesichts einer formellen / informellen Definition dessen, was es für einen Funktor bedeutet, eine bestimmte Größe oder Vielfalt in Bezug auf Einwohner seines Typarguments zu haben, stellt sich die Frage, ob die Existenz einer StrongApplicativeInstanz Funktoren fester und unterschiedlicher Größe genau unterscheidet.

Da mir eine bestehende formale Definition nicht bekannt ist, appelliere ich an die Intuition, wenn ich den Begriff "feste Größe" verwende. Allerdings, wenn jemand bereits einen bestehenden Formalismus für die Größe eines Funktors kennt und vergleichen kannStrongApplicative besser.

** Mit "Multiplizität" beziehe ich mich in einem losen Sinne auf "wie viele" beliebige Elemente des Parametertyps des Funktors in einem Bewohner des Codomänen-Typs des Funktors vorkommen. Dies ist ohne Rücksicht auf den speziellen Typ der Funktor auf, angewendet wird und daher ohne Rücksicht auf irgendwelche spezifischen Bewohner des Parametertyps.

Nicht genau zu sein, hat einige Verwirrung in den Kommentaren verursacht. Hier sind einige Beispiele dafür, was ich für die Größe / Vielzahl verschiedener Funktoren halten würde:

• VoidF: fest, 0
• Identity: fest, 1
• Maybe: variabel, Minimum 0, Maximum 1
• []: variabel, Minimum 0, Maximum unendlich
• NonEmptyList: variabel, Minimum 1, Maximum unendlich
• Stream: fest, unendlich
• Monoid m => (,) m: fest, 1
• data Pair a = Pair a a: fest, 2
• Either x: variabel, Minimum 0, Maximum 1
• data Strange a = L a | R a: fest, 1

• Jeder, Applicativeder einen Container "fester Größe" von Elementen seines Typarguments darstellt, ist eine Instanz vonStrongApplicative
• Es StrongApplicativegibt keine Instanz von , in der die Anzahl der Vorkommen avariieren kann

Kann sich jemand Gegenbeispiele vorstellen, die diese Vermutungen widerlegen, oder überzeugende Argumente, die zeigen, warum sie wahr oder falsch sind?

Ich bin mir bei dieser ersten Vermutung nicht sicher und aufgrund von Diskussionen mit @AsadSaeeduddin ist es wahrscheinlich schwierig zu beweisen, aber die zweite Vermutung ist wahr. Um zu sehen warum, betrachten Sie das StrongApplicativeGesetz husk . unhusk == id; das heißt für alle x :: f (), husk (unhusk x) == x. Aber in Haskell, unhusk == const ()so ist das Gesetz für alle gleichwertig zu sagen x :: f (), husk () == x. Dies impliziert jedoch wiederum, dass es nur einen bestimmten Wert vom Typ geben kann f (): Wenn es zwei Werte gäbe x, y :: f (), dann x == husk ()und husk () == yso x == y. Wenn es jedoch nur einen möglichen f ()Wert gibt, fmuss er eine feste Form haben. (zB für data Pair a = Pair a agibt es nur einen Wert vom Typ Pair (), dies ist Pair () (), aber es gibt mehrere Werte vom Typ Maybe ()oder [()].) Alsohusk . unhusk == idimpliziert, dass fdie Form fest sein muss.

Wir können mindestens eine dieser Fragen verneinen:

Jeder Applikative, der einen Container mit "fester Größe" von Elementen seines Typarguments darstellt, ist eine Instanz von StrongApplicative

In der Tat ist eines der Beispiele für ein Gesetz StrongApplicativein der ursprünglichen Frage falsch. Der Schriftsteller Monoid => (,) mist nicht anwendbar StrongApplicative, weil zum Beispiel husk $ unhusk $ ("foo", ()) == ("", ()) /= ("foo", ()).

Ebenso das Beispiel eines Containers mit fester Größe:

data Strange a = L a | R a

der festen Multiplizität 1 ist keine starke Anwendung, denn wenn wir husk = Leftdann definieren husk $ unhusk $ Right () /= Right ()und umgekehrt. Eine äquivalente Möglichkeit, dies anzuzeigen, besteht darin, dass dies nur der Autor ist, der für Ihre Wahl des Monoids auf anwendbar ist Bool.

Es gibt also Anwendungen mit "fester Größe", die dies nicht sind StrongApplicative. Ob alle StrongApplicatives eine feste Größe haben, bleibt abzuwarten.

Nehmen wir darstellbare Funktoren als unsere Definition von "Container mit fester Größe":

class Representable f where
    type Rep f
    tabulate :: (Rep f -> a) -> f a
    index :: f a -> Rep f -> a

Der Real Representablehat ein paar Gesetze und Oberklassen, aber für die Zwecke dieser Antwort benötigen wir tatsächlich nur zwei Eigenschaften:

tabulate . index = id
index . tabulate = id

(Okay, wir brauchen auch eine gesetzestreue instance StrongApplicative ((->) r). Einfach peasy, Sie stimmen bereits zu, dass es existiert.)

Wenn wir diese Definition nehmen, kann ich diese Vermutung 1 bestätigen:

Jeder, Applicativeder einen Container "fester Größe" von Elementen seines Typarguments darstellt, ist eine [gesetzestreue] Instanz vonStrongApplicative

ist wahr. Hier ist wie:

instance Representable f => Applicative f where
    zip (fa, fb) = tabulate (zip (index fa, index fb))
    husk = tabulate . husk

instance Representable f => OpApplicative f where
    unzip fab = let (fa, fb) = unzip (index fab) in (tabulate fa, tabulate fb)
    unhusk = unhusk . index

instance Representable f => StrongApplicative f

Es gibt eine Menge Gesetze zu beweisen, aber ich werde mich nur auf die Big Four konzentrieren, die StrongApplicativehinzufügen - Sie glauben wahrscheinlich bereits an die führenden Gesetze für Applicativeund OpApplicative, wenn Sie dies nicht tun, sehen ihre Beweise genauso aus wie die folgenden ( die wiederum ziemlich ähnlich aussehen). Aus Gründen der Klarheit werde ich verwenden zipf, huskfetc. für die Funktionsinstanz, und zipr, huskretc. für die darstellbare Instanz, so dass Sie verfolgen, welche zu halten ist , welche. (Und damit es einfach ist zu überprüfen, ob wir das, was wir zu beweisen versuchen, nicht als Annahme nehmen! Es ist in Ordnung, es unhuskf . huskf = idbeim Beweisen zu verwenden unhuskr . huskr = id, aber es wäre falsch unhuskr . huskr = id, denselben Beweis anzunehmen .)

Der Beweis für jedes Gesetz erfolgt im Wesentlichen auf die gleiche Weise: Entrollen Sie Definitionen, lassen Sie den Isomorphismus fallen, Representableden Sie erhalten, und verwenden Sie dann das analoge Gesetz für Funktionen.

unhuskr . huskr
= { def. of unhuskr and huskr }
(unhuskf . index) . (tabulate . huskf)
= { index . tabulate = id }
unhuskf . huskf
= { unhuskf . huskf = id }
id

huskr . unhuskr
= { def. of huskr and unhuskr }
(tabulate . huskf) . (unhuskf . index)
= { huskf . unhuskf = id }
tabulate . index
= { tabulate . index = id }
id

zipr (unzipr fab)
= { def. of unzipr }
zipr (let (fa, fb) = unzipf (index fab) in (tabulate fa, tabulate fb))
= { def. of zipr }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (index (tabulate fa), index (tabulate fb)))
= { index . tabulate = id }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (fa, fb))
= { def. of (fa, fb) }
tabulate (zipf (unzipf (index fab)))
= { zipf . unzipf = id }
tabulate (index fab)
= { tabulate . index = id }
fab

unzipr (zipr (fa, fb))
= { def. of zipr }
unzipr (tabulate (zipf (index fa, index fb)))
= { def. of unzipr }
let (fa', fb') = unzipf (index (tabulate (zipf (index fa, index fb))))
in (tabulate fa', tabulate fb')
= { index . tabulate = id }
let (fa', fb') = unzipf (zipf (index fa, index fb))
in (tabulate fa', tabulate fb')
= { unzipf . zipf = id }
let (fa', fb') = (index fa, index fb)
in (tabulate fa', tabulate fb')
= { def. of fa' and fb' }
(tabulate (index fa), tabulate (index fb))
= { tabulate . index = id }
(fa, fb)