Czy wszystkie pojemniki o stałym rozmiarze są silnymi funktorami monoidalnymi i / lub odwrotnie?

Ta Applicativeklisza reprezentuje luźne funktory monoidalne, które zachowują kartezjańską monoidalną strukturę w kategorii typowanych funkcji.

Innymi słowy, biorąc pod uwagę obserwowane kanoniczne izomorfizmy, które (,)tworzą strukturę monoidalną:

-- 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, ())

Typekę i jej prawa można zapisać w następujący sposób:

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

Można się zastanawiać, jak mógłby wyglądać funktor, który jest opoidem monoidalnym w odniesieniu do tej samej struktury:

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

Jeśli pomyślimy o typach zawartych w definicjach i prawach, rozczarowująca prawda zostanie ujawniona; OpApplicativenie jest bardziej szczegółowym ograniczeniem niż Functor:

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

Jednak chociaż każdy Applicativefunktor (naprawdę każdy Functor) jest trywialny OpApplicative, niekoniecznie istnieje przyjemny związek między Applicativewiotkościami i OpApplicativezmętnieniami. Możemy więc poszukać silnych funktorów monoidalnych w kartezjańskiej strukturze monoidalnej:

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

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

Pierwsze powyższe prawo jest trywialne, ponieważ jedynym mieszkańcem tego typu () -> ()jest funkcja tożsamości ().

Jednak pozostałe trzy prawa, a zatem sama podklasa, nie są trywialne. W szczególności nie każdy Applicativejest zgodną z prawem instancją tej klasy.

Oto niektóre Applicativefunktory, dla których możemy zadeklarować legalne przypadki StrongApplicative:

• Identity
• VoidF
• (->) r
• Monoid m => (,) m (Zobacz odpowiedzi)
• Vec (n :: Nat)
• Stream (nieskończony)

A oto kilka Applicatives, dla których nie możemy:

• []
• Either e
• Maybe
• NonEmptyList

Wzór tutaj sugeruje, że StrongApplicativeklasa jest w pewnym sensie FixedSizeklasą, gdzie „ustalony rozmiar” ^* oznacza, że liczebność ^** mieszkańców aw mieszkance f ajest ustalona.

Można to określić jako dwie domysły:

• Każda Applicativereprezentująca kontener „o stałym rozmiarze” elementów argumentu typu jest instancją klasyStrongApplicative
• Nie StrongApplicativeistnieje żaden przypadek , w którym liczba wystąpień amoże się różnić

Czy ktoś może pomyśleć o kontrprzykładach, które obalają te przypuszczenia, lub o przekonującym uzasadnieniu, które pokazuje, dlaczego są one prawdziwe lub fałszywe?

* Zdaję sobie sprawę, że nie zdefiniowałem właściwie przymiotnika „fixed size”. Niestety zadanie jest trochę okrągłe. Nie znam żadnego formalnego opisu kontenera o „stałym rozmiarze” i próbuję go wymyślić. StrongApplicativeto moja najlepsza jak dotąd próba.

Aby jednak ocenić, czy jest to dobra definicja, potrzebuję czegoś do porównania. Biorąc pod uwagę formalną / nieformalną definicję tego, co to znaczy dla funktora mieć określoną wielkość lub krotność w stosunku do mieszkańców tego rodzaju argumentu, pytanie brzmi, czy istnienie StrongApplicativeinstancji dokładnie rozróżnia funktory o stałej i zmiennej wielkości.

Nie zdając sobie sprawy z istniejącej definicji formalnej, odwołuję się do intuicji, posługując się terminem „ustalony rozmiar”. Jeśli jednak ktoś już wie o istniejącym formalizmie dotyczącym wielkości funktora i może go porównać StrongApplicative, tym lepiej.

** Przez „wielokrotność” w luźnym znaczeniu odnoszę się do „ilu” dowolnych elementów typu parametru funktora występuje u mieszkańca typu kodomenu funktora. Jest to bez względu na rodzaj specyficznego funktor jest nakładana, a więc bez uwzględniania jakichkolwiek mieszkańców konkretnych typu parametru.

Nie precyzowanie tego spowodowało pewne zamieszanie w komentarzach, więc oto kilka przykładów tego, co uważam za rozmiar / mnogość różnych funktorów:

• VoidF: naprawiono, 0
• Identity: naprawiono, 1
• Maybe: zmienna, minimum 0, maksimum 1
• []: zmienna, minimum 0, maksymalna nieskończoność
• NonEmptyList: zmienna, minimum 1, maksymalna nieskończoność
• Stream: naprawiony, nieskończony
• Monoid m => (,) m: naprawiono, 1
• data Pair a = Pair a a: naprawiono, 2
• Either x: zmienna, minimum 0, maksimum 1
• data Strange a = L a | R a: naprawiono, 1

• Każda Applicativereprezentująca kontener „o stałym rozmiarze” elementów argumentu typu jest instancją klasyStrongApplicative
• Nie StrongApplicativeistnieje żaden przypadek , w którym liczba wystąpień amoże się różnić

Czy ktoś może pomyśleć o kontrprzykładach, które obalają te przypuszczenia, lub o przekonującym uzasadnieniu, które pokazuje, dlaczego są one prawdziwe lub fałszywe?

Nie jestem pewien tej pierwszej przypuszczenia i na podstawie dyskusji z @AsadSaeeduddin prawdopodobnie trudno będzie ją udowodnić, ale druga hipoteza jest prawdziwa. Aby zobaczyć dlaczego, rozważ StrongApplicativeprawo husk . unhusk == id; to jest dla wszystkich x :: f (), husk (unhusk x) == x. Ale w Haskell, unhusk == const ()tak, że prawo jest równoznaczne ze stwierdzeniem, dla wszystkich x :: f (), husk () == x. Ale to z kolei oznacza, że ​​może istnieć tylko jedna odrębna wartość typu f (): gdyby były dwie wartości x, y :: f (), wtedy x == husk ()i husk () == ytak x == y. Ale jeśli istnieje tylko jedna możliwa f ()wartość, fmusi mieć ustalony kształt. (np. dla data Pair a = Pair a aistnieje tylko jedna wartość typu Pair (), to jest Pair () (), ale istnieje wiele wartości typu Maybe ()lub[()] .) Zatemhusk . unhusk == idoznacza, że fmusi mieć ustalony kształt.

Możemy odpowiedzieć przynajmniej na jedno z poniższych pytań przecząco:

Każdy aplikant reprezentujący kontener „o stałym rozmiarze” elementów argumentu typu jest instancją StrongApplicative

W rzeczywistości jeden z przykładów zgodnych z prawem StrongApplicativew pierwotnym pytaniu jest błędny. Aplikacja pisarzaMonoid => (,) m nie jest StrongApplicative, ponieważ na przykład husk $ unhusk $ ("foo", ()) == ("", ()) /= ("foo", ()).

Podobnie przykład kontenera o stałym rozmiarze:

data Strange a = L a | R a

o stałej krotności 1, nie jest silną aplikacją, ponieważ jeśli zdefiniujemy husk = Leftto,husk $ unhusk $ Right () /= Right () , i vice versa. Równoważnym sposobem na zobaczenie tego jest to, że jest to po prostu aplikacja pisarska do wyboru monoidu Bool.

Istnieją więc aplikacje o ustalonym rozmiarze, które nie są StrongApplicative. Nie wiadomo, czy wszystkie StrongApplicativemają stały rozmiar.

Weźmy reprezentatywne funktory jako naszą definicję „kontenera o stałym rozmiarze”:

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

Rzeczywistość Representablema kilka praw i nadklas, ale do celów tej odpowiedzi potrzebujemy tylko dwóch właściwości:

tabulate . index = id
index . tabulate = id

(Okej, potrzebujemy również prawnie przestrzeganych przepisów instance StrongApplicative ((->) r). Spokojny, już zgadzasz się, że istnieje).

Jeśli weźmiemy tę definicję, mogę potwierdzić tę hipotezę 1:

Każdy Applicativeelement reprezentujący „stały rozmiar” kontenera elementów argumentu typu jest zgodną z prawem instancjąStrongApplicative

jest prawdziwy. Oto jak:

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

Jest wiele praw do udowodnienia, ale skupię się tylko na Wielkiej Czwórce, która StrongApplicativedodaje - prawdopodobnie już wierzysz w wprowadzenie Applicativei OpApplicative, ale jeśli nie, ich dowody wyglądają tak jak te poniżej ( które z kolei wyglądają bardzo podobnie do siebie). Dla jasności, użyję zipf, huskfitp na przykład funkcji, a zipr, huskritp dla przedstawialnym instancji, dzięki czemu można śledzić, który jest który. (I aby łatwo było zweryfikować, że nie bierzemy tego, co próbujemy udowodnić, jako założenie! Można to wykorzystać unhuskf . huskf = idpodczas dowodzenia unhuskr . huskr = id, ale błędne byłoby założenie, żeunhuskr . huskr = id tego samego dowodu.)

Potwierdzenie każdego prawa przebiega w zasadzie w ten sam sposób: rozwinąć definicje, porzucić izomorfizm, który Representabledaje, a następnie zastosować analogiczne prawo dla funkcji.

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)