Monada to po prostu monoid w kategorii endofunkorów, na czym polega problem?

722

Kto pierwszy powiedział, co następuje?

Monada to po prostu monoid w kategorii endofunkorów, na czym polega problem?

A w mniej ważnej sprawie, czy to prawda, a jeśli tak, to czy mógłbyś podać wyjaśnienie (mam nadzieję, że może to być zrozumiałe dla kogoś, kto nie ma dużego doświadczenia Haskell)?

Roman A. Taycher
źródło
14
Zobacz „Kategorie pracującego matematyka”
Don Stewart
18
Nie musisz tego rozumieć, aby używać monad w Haskell. Z praktycznego punktu widzenia są one po prostu sprytnym sposobem na ominięcie „państwa” przez niektóre podziemne instalacje hydrauliczne.
starblue
1
Chciałbym również dodać tutaj ten świetny post na blogu: stephendiehl.com/posts/monads.html Nie odpowiada bezpośrednio na pytanie, ale moim zdaniem Stephen świetnie sobie radzi, łącząc kategorie i monady w Haskell. Jeśli przeczytałeś powyższe odpowiedzi - powinno to pomóc ujednolicić dwa sposoby patrzenia na to.
Ben Ford
3
Dokładniej: „Dla dowolnej kategorii C kategoria [C, C] endofunkcji ma monoidalną strukturę indukowaną przez kompozycję. Obiekt monoidalny w [C, C] jest monadą na C.” - z en.wikipedia.org/wiki/Monoid_%28category_theory%29. Zobacz en.wikipedia.org/wiki/Monad_%28category_theory%29, aby uzyskać definicję monady w teorii kategorii.
1
@Dmitry Funktor jest funkcją między kategoriami, z pewnymi ograniczeniami, które należy zachować. Endofunkcjonariusz w kategorii C jest po prostu funktorem od C do samego siebie. Data.Functor jest typem klasy dla endofunktorów z kategorii Hask . Ponieważ kategoria składa się z obiektów i morfizmów, funktor musi zmapować oba. Dla instancji f Data.Functor, mapa obiektów (typy haskell) to sama f, a mapa morfizmów (funkcje haskell) to fmap.
Matthijs,

Odpowiedzi:

795

To szczególne sformułowanie autorstwa Jamesa Iry'ego z jego bardzo zabawnej Krótkiej, niekompletnej i głównie błędnej historii języków programowania , w której fikcyjnie przypisuje ją Philipowi Wadlerowi.

Oryginalny cytat pochodzi z Saunders Mac Lane w kategorii dla pracującego matematyka , jednego z podstawowych tekstów teorii kategorii. Tutaj jest w kontekście , który jest prawdopodobnie najlepszym miejscem, aby dowiedzieć się dokładnie, co to znaczy.

Ale wezmę dźgnięcie. Oryginalne zdanie jest następujące:

Mówiąc ogólnie, monada w X jest po prostu monoidą w kategorii endofunkcji X, a iloczyn × zastąpiono składem endofunkcji i zestawem jednostek przez endofunkcję tożsamości.

X tutaj jest kategorią. Endofunctors są funktory od kategorii do siebie (co jest zwykle wszystko Functor jest w miarę programiści funkcjonalne są zainteresowane, ponieważ są one głównie do czynienia z tylko jednej kategorii; kategorię rodzajów - ale to dygresja). Ale możesz sobie wyobrazić inną kategorię, którą jest kategoria „endofunkcji na X ”. Jest to kategoria, w której obiekty są endofunkcjami, a morfizmy są naturalnymi przemianami.

A spośród tych endofunkorów niektóre z nich mogą być monadami. Które to monady? Dokładnie te, które są monoidalne w pewnym sensie. Zamiast dokładnego mapowania monad na monoidy (ponieważ Mac Lane robi to o wiele lepiej, niż mogłem się spodziewać), po prostu umieszczę ich odpowiednie definicje obok siebie i pozwolę ci porównać:

Monoid jest ...

  • Zestaw, S
  • Operacja, •: S × S → S
  • Element S , e: 1 → S.

... spełniając te prawa:

  • (A • B) • c = a • (b • C) , dla każdego a , b i c w S
  • e • a = a • e = a , dla wszystkich a w S.

Monada to ...

  • Endofunktor, T: X → X (w Haskell, rodzaj konstruktora rodzaju * -> *z Functorinstancją)
  • Naturalna transformacja, μ: T × T → T , gdzie × oznacza skład funktora ( μ jest znany jak joinw Haskell)
  • Naturalna transformacja, η: I → T , gdzie I jest endofunkcją tożsamości na X ( η jest znane jak returnw Haskell)

... spełniając te prawa:

  • μ ∘ Tμ = μ ∘ μT
  • μ ∘ Tη = μ ∘ ηT = 1 (naturalna transformacja tożsamości)

Przy odrobinie mrużenia oka możesz zauważyć, że obie te definicje są instancjami tej samej abstrakcyjnej koncepcji .

Tom Crockett
źródło
21
dziękuję za wyjaśnienie i dziękuję za krótki, niekompletny i głównie niewłaściwy artykuł dotyczący historii języków programowania. Myślałem, że może być stamtąd. Naprawdę jeden z największych elementów humoru programistycznego.
Roman A. Taycher
6
@Jathanathan: W klasycznym sformułowaniu monoidu × oznacza iloczyn kartezjański zbiorów. Możesz przeczytać więcej na ten temat tutaj: en.wikipedia.org/wiki/Cartesian_product , ale podstawowa idea jest taka, że element S × T jest parą (s, t) , gdzie s ∈ S i T ∈ T . Zatem sygnatura produktu monoidalnego •: S × S -> S w tym kontekście oznacza po prostu funkcję, która przyjmuje 2 elementy S jako dane wejściowe i wytwarza inny element S jako dane wyjściowe.
Tom Crockett,
12
@TahirHassan - W ogólnej teorii kategorii mamy do czynienia z nieprzezroczystymi „obiektami” zamiast zbiorów, a zatem nie ma a priori pojęcia „elementów”. Ale jeśli pomyślisz o kategorii Zestaw, w której obiekty są zestawami, a strzałki są funkcjami, elementy dowolnego zestawu S są w relacji jeden do jednego z funkcjami z dowolnego zestawu jednoelementowego do S. To znaczy, dla dowolnego Element e od S istnieje dokładnie jedna funkcja f: 1 -> S , gdzie 1 jest dowolny zestaw jednego elementu ... (ciąg dalszy)
Tom Crockett
12
@TahirHassan 1-elementowe zestawy same w sobie są specjalizacjami z bardziej ogólnego teoretycznego pojęcia „obiektów końcowych”: obiekt końcowy to dowolny obiekt kategorii, dla którego istnieje dokładnie jedna strzałka od dowolnego innego obiektu (można to sprawdzić dotyczy to zestawów 1-elementowych w zestawie ). W teorii kategorii obiekty końcowe są po prostu określane jako 1 ; są wyjątkowe aż do izomorfizmu, więc nie ma sensu ich rozróżniać. Tak więc teraz mamy czysto teoretyczny opis kategorii „elementów S ” dla dowolnego S : są to tylko strzałki od 1 do S !
Tom Crockett,
7
@TahirHassan - Aby umieścić to w kategoriach Haskell, pomyśl o tym, że jeśli Sjest typem, wszystko, co możesz zrobić, pisząc funkcję, f :: () -> Sto wybierz określony termin typu S(„element”, jeśli chcesz) i wróć to ... nie otrzymałeś żadnej prawdziwej informacji z argumentem, więc nie ma sposobu, aby zmienić zachowanie funkcji. fMusi więc istnieć stała funkcja, która za każdym razem zwraca to samo. ()(„Jednostka”) jest obiektem końcowym kategorii Hask i nie jest przypadkiem, że zamieszkuje ją dokładnie 1 (nie rozbieżna) wartość.
Tom Crockett,
532

Intuicyjnie myślę, że to, co mówi fantazyjne słownictwo matematyczne, brzmi:

Monoid

Monoid jest zbiorem obiektów i sposób ich łączenia. Dobrze znane monoidy to:

  • liczby, które możesz dodać
  • listy, które można połączyć
  • zestawy, które możesz połączyć

Istnieją również bardziej złożone przykłady.

Co więcej, każda monoid ma tożsamość , czyli ten element „no-op”, który nie działa, gdy połączysz go z czymś innym:

  • 0 + 7 == 7 + 0 == 7
  • [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3]
  • {} unia {jabłko} == {jabłko} unia {} == {jabłko}

Wreszcie monoid musi być asocjacyjny . (możesz dowolnie skracać długi ciąg kombinacji, o ile nie zmienisz kolejności obiektów od lewej do prawej) Dodawanie jest OK ((5 + 3) +1 == 5+ (3+ 1)), ale odejmowanie nie jest ((5-3) -1! = 5- (3-1)).

Monada

Rozważmy teraz specjalny rodzaj zestawu i specjalny sposób łączenia obiektów.

Obiekty

Załóżmy, że Twój zestaw zawiera obiekty specjalnego rodzaju: funkcje . Funkcje te mają interesującą sygnaturę: nie przenoszą liczb na liczby ani ciągów znaków na ciągi znaków. Zamiast tego każda funkcja przenosi liczbę na listę liczb w dwuetapowym procesie.

  1. Oblicz 0 lub więcej wyników
  2. Jakoś połącz te wyniki w jedną odpowiedź.

Przykłady:

  • 1 -> [1] (po prostu zawiń dane wejściowe)
  • 1 -> [] (odrzuć dane wejściowe, zawiń nicość na liście)
  • 1 -> [2] (dodaj 1 do wejścia i zawiń wynik)
  • 3 -> [4, 6] (dodaj 1 do danych wejściowych, pomnóż dane wejściowe przez 2 i zawiń wiele wyników )

Łączenie obiektów

Ponadto nasz sposób łączenia funkcji jest wyjątkowy. Prostym sposobem na połączenie funkcji jest kompozycja : weźmy nasze przykłady powyżej i ułóż każdą funkcję ze sobą:

  • 1 -> [1] -> [[1]] (zawiń wejście dwukrotnie)
  • 1 -> [] -> [] (odrzuć dane wejściowe, dwukrotnie zawiń nicość na liście)
  • 1 -> [2] -> [UH-OH! ] (nie możemy „dodać 1” do listy! ”)
  • 3 -> [4, 6] -> [UH-OH! ] (nie możemy dodać 1 listy!)

Nie wnikając zbytnio w teorię typów, chodzi o to, że można połączyć dwie liczby całkowite, aby uzyskać liczbę całkowitą, ale nie zawsze można skomponować dwie funkcje i uzyskać funkcję tego samego typu. (Funkcje typu a -> a utworzą, ale a-> [a] nie.)

Zdefiniujmy więc inny sposób łączenia funkcji. Łącząc dwie z tych funkcji, nie chcemy „podwójnie owijać” wyników.

Oto co robimy. Kiedy chcemy połączyć dwie funkcje F i G, postępujemy zgodnie z tym procesem (zwanym wiązaniem ):

  1. Oblicz „wyniki” z F, ale nie łącz ich.
  2. Oblicz wyniki z zastosowania G do każdego z wyników F osobno, uzyskując kolekcję wyników.
  3. Spłaszcz 2-poziomową kolekcję i połącz wszystkie wyniki.

Wracając do naszych przykładów, połączmy (powiązaj) funkcję ze sobą, korzystając z tego nowego sposobu „wiązania” funkcji:

  • 1 -> [1] -> [1] (dwukrotnie owinąć wejście)
  • 1 -> [] -> [] (odrzuć dane wejściowe, dwukrotnie zawiń nicość na liście)
  • 1 -> [2] -> [3] (dodaj 1, następnie dodaj 1 ponownie i zawiń wynik).
  • 3 -> [4,6] -> [5,8,7,12] (dodaj 1 do danych wejściowych, a także pomnóż dane wejściowe przez 2, zachowując oba wyniki, a następnie zrób to wszystko ponownie dla obu wyników, a następnie zawiń końcowy powoduje powstanie listy).

Ten bardziej wyrafinowany sposób łączenia funkcji jest asocjacyjny ( wynika z tego, jak kompozycja funkcji jest asocjacyjna, gdy nie robisz fantazyjnych rzeczy do pakowania).

Łącząc to wszystko razem,

  • monada to struktura, która określa sposób łączenia (wyników) funkcji,
  • analogicznie do tego, jak monoid jest strukturą, która określa sposób łączenia obiektów,
  • gdzie metoda łączenia jest asocjacyjna,
  • a tam, gdzie istnieje specjalny „brak operacji”, który można połączyć z dowolnym czymś, aby uzyskać coś niezmienionego.

Notatki

Istnieje wiele sposobów „zawijania” wyników. Możesz utworzyć listę, zestaw lub odrzucić wszystkie wyniki oprócz pierwszego, zwracając uwagę, czy nie ma żadnych wyników, dołączyć boczny stan, wydrukować komunikat dziennika itp.

Grałem trochę luźno z definicjami w nadziei, że intuicyjnie zrozumiem niezbędny pomysł.

Uprościłem trochę, nalegając, aby nasza monada działała na funkcjach typu a -> [a] . W rzeczywistości monady działają na funkcjach typu a -> mb , ale uogólnienie jest rodzajem detalu technicznego, który nie jest głównym wglądem.

misterbee
źródło
22
To dobre wyjaśnienie, w jaki sposób każda monada stanowi kategorię ( kategoria Kleisli jest tym, co demonstrujesz - istnieje również kategoria Eilenberg-Moore). Ale z uwagi na fakt, że nie możesz skomponować żadnych dwóch strzał Kleisli a -> [b]i c -> [d](możesz to zrobić tylko, jeśli b= c), to nie całkiem opisuje monoid. Jest to tak naprawdę opisana operacja spłaszczania, a nie kompozycja funkcji, która jest „operatorem monoidu”.
Tom Crockett,
6
To prawda, że ​​jeśli ograniczysz monadę tylko do jednego typu, tzn. Jeśli zezwolisz tylko na strzały Kleisli w formie a -> [a], będzie to monoid (ponieważ ograniczysz kategorię Kleisli do jednego obiektu i dowolnej kategorii tylko jednego obiektu jest z definicji monoidem!), ale nie uchwyciłby pełnej ogólności monady.
Tom Crockett,
5
W ostatniej nucie pomaga pamiętać, że -> [a] jest po prostu -> [] a. ([] to także konstruktor typów). I dlatego można go postrzegać nie tylko jako -> mb, ale [] jest rzeczywiście instancją klasy Monad.
Evi1M4chine
8
Jest to najlepsze i najbardziej zrozumiałe wyjaśnienie monad i ich matematycznych podstaw monoidów, na które natknąłem się dosłownie tygodnie. To jest to, co powinno być wydrukowane w każdej książce Haskell, jeśli chodzi o monady, bez użycia rąk. UPVOTE! Być może dodatkowo zdobędziemy informację, że monady są realizowane jako sparametryzowane instancje typu typowego zawijające wszystko, co jest w nich haskell, do postu. (Przynajmniej tak je teraz rozumiałem. Popraw mnie, jeśli się mylę. Zobacz haskell.org/haskellwiki/What_a_Monad_is_not )
sjas
1
To fantastyczne - to jedyne wyjaśnienie, które zrozumiałem wystarczająco dobrze, aby móc to wytłumaczyć komuś innemu ... Ale wciąż nie rozumiem, dlaczego jest to cenny sposób myślenia o czymkolwiek. :(
Adam Barnes
84

Po pierwsze, rozszerzenia i biblioteki, których będziemy używać:

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

Spośród nich RankNTypesjest jedynym, który jest absolutnie niezbędny dla poniższych. Kiedyś napisałem wyjaśnienieRankNTypes że niektórzy ludzie wydają się przydatni , więc odniosę się do tego.

Cytując doskonałą odpowiedź Toma Crocketta , mamy:

Monada to ...

  • Endofunkor, T: X -> X
  • Naturalna transformacja, μ: T × T -> T , gdzie × oznacza skład funktora
  • Naturalna transformacja, η: I -> T , gdzie I jest endofunkcją tożsamości na X

... spełniając te prawa:

  • μ (μ (T × T) × T)) = μ (T × μ (T × T))
  • μ (η (T)) = T = μ (T (η))

Jak tłumaczymy to na kod Haskell? Zacznijmy od pojęcia naturalnej transformacji :

-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g =
    Natural { eta :: forall x. f x -> g x }

Typ formy f :-> gjest analogiczny do typu funkcji, ale zamiast myśleć o nim jako o funkcji między dwoma typami (rodzaju *), pomyśl o nim jako o morfizmie między dwoma funktorami (każdy z rodzaju* -> * ). Przykłady:

listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse

Zasadniczo w Haskell transformacje naturalne są funkcjami z f xjednego typu do innego typu, g xtak że xzmienna typu jest „niedostępna” dla dzwoniącego. Na przykładsort :: Ord a => [a] -> [a] nie można go przekształcić w naturalną transformację, ponieważ jest „wybredna”, co do tego, dla jakich typów możemy utworzyć instancję a. Jednym z intuicyjnych sposobów myślenia o tym jest:

  • Funktor to sposób działania na treści czegoś bez dotykania struktury .
  • Naturalna transformacja to sposób działania na strukturę czegoś bez dotykania lub patrzenia na treść .

Teraz, nie wspominając o tym, zajmiemy się klauzulami definicji.

Pierwsza klauzula to „endofunkcja, T: X -> X ”. Cóż, każdy Functorw Haskell jest endofunkorem w tym, co ludzie nazywają „kategorią Hask”, którego obiektami są rodzaje Haskell (swego rodzaju *), a morfizmy są funkcjami Haskella. To brzmi jak skomplikowane stwierdzenie, ale w rzeczywistości jest bardzo trywialne. Oznacza to tylko, że a Functor f :: * -> *daje środki do konstruowania typu f a :: *dla dowolnej a :: *i funkcji fmap f :: f a -> f bz dowolnejf :: a -> b , i że są one zgodne z prawami funktorów.

Druga klauzula: Identityfunktor w Haskell (który jest dostarczany z platformą, więc możesz go po prostu zaimportować) jest zdefiniowany w następujący sposób:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

Tak więc naturalną transformację η: I -> T z definicji Toma Crocketta można zapisać w ten sposób dla każdego Monadprzypadku t:

return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)

Trzecia klauzula: Skład dwóch funktorów w Haskell można zdefiniować w ten sposób (który również jest dostarczany z platformą):

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor's is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)

Tak więc naturalną transformację μ: T × T -> T z definicji Toma Crocketta można zapisać w następujący sposób:

join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)

Stwierdzenie, że jest to monoid w kategorii endofunkcji, oznacza zatem, że Compose(częściowo zastosowane tylko do jego pierwszych dwóch parametrów) jest asocjacyjne i to Identityjest jego element tożsamości. Tzn., Że posiadają następujące izomorfizmy:

  • Compose f (Compose g h) ~= Compose (Compose f g) h
  • Compose f Identity ~= f
  • Compose Identity g ~= g

Są one bardzo łatwe do udowodnienia, ponieważ Composei Identityoba są zdefiniowane jako newtype, a Raporty Haskella definiują semantykę newtypejako izomorfizm między definiowanym typem a rodzajem argumentu newtypekonstruktora danych. Na przykład udowodnijmy Compose f Identity ~= f:

Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.
Luis Casillas
źródło
W Naturalnowym typie nie mogę zrozumieć, co (Functor f, Functor g)robi ograniczenie. Czy możesz wytłumaczyć?
dfeuer
@dfeuer To naprawdę nie robi nic istotnego.
Luis Casillas,
1
@LuisCasillas Usunąłem te Functorograniczenia, ponieważ nie wydają się konieczne. Jeśli się nie zgadzasz, możesz je dodać ponownie.
Lambda Fairy
Czy potrafisz wyjaśnić, co to znaczy formalnie, że iloczyn funktorów ma być traktowany jako kompozycja? W szczególności, jakie są morfizmy projekcji dla składu funktorów? Domyślam się, że produkt jest zdefiniowany tylko dla funktora F względem siebie, F x F i tylko wtedy, gdy joinjest zdefiniowany. I to joinjest morfizm projekcyjny. Ale nie jestem pewien.
tksfz
6

Uwaga: Nie, to nie jest prawda. W pewnym momencie do tej odpowiedzi skomentował sam Dan Piponi, mówiąc, że przyczyną i skutkiem jest dokładnie odwrotnie, że napisał swój artykuł w odpowiedzi na żart Jamesa Iry'ego. Ale wydaje się, że został usunięty, być może przez jakiś kompulsywny porządek.

Poniżej moja oryginalna odpowiedź.


Całkiem możliwe, że Iry przeczytał From Monoids to Monads , post, w którym Dan Piponi (sigfpe) wywodzi monady z monoidów w Haskell, z dużą dyskusją na temat teorii kategorii i wyraźną wzmianką o „kategorii endofunkorów na Hask ”. W każdym razie każdy, kto zastanawia się, co to znaczy, że monada jest monoidem w kategorii endofunkcji, może skorzystać z lektury tego wyprowadzenia.

Hobbs
źródło
1
„Być może przez jakiś kompulsywny porządek” - lub, jak to czule nazywamy na tej stronie, moderatora :-).
halfer
6

Doszedłem do tego postu, aby lepiej zrozumieć wniosek o niesławnym cytacie z teorii kategorii Mac Lane'a dla pracującego matematyka .

Opisując, czym jest, często równie przydatne jest opisanie tego, czym nie jest.

Fakt, że Mac Lane używa opisu do opisu Monady, może sugerować, że opisuje on coś unikalnego dla Monad. Zrób ze mną. Aby rozwinąć szersze zrozumienie tego oświadczenia, uważam, że należy wyjaśnić, że tak jest nie opisuje on czegoś, co jest unikalne dla monad; oświadczenie w równym stopniu opisuje między innymi aplikację i strzałki. Z tego samego powodu możemy mieć dwa monoidy na Int (suma i iloczyn), możemy mieć kilka monoidów na X w kategorii endofunkcji. Ale podobieństw jest jeszcze więcej.

Zarówno Monad, jak i Wnioskodawca spełniają kryteria:

  • endo => dowolna strzała lub morfizm, który zaczyna się i kończy w tym samym miejscu
  • funktor => dowolna strzałka lub morfizm między dwiema kategoriami

    (np. z dnia na dzień Tree a -> List b, ale w kategorii Tree -> List)

  • monoid => pojedynczy obiekt; tj. pojedynczy typ, ale w tym kontekście tylko w odniesieniu do warstwy zewnętrznej; więc nie możemy mieć Tree -> Listtylko List -> List.

W instrukcji użyto „Kategoria ...”. Definiuje zakres instrukcji. Jako przykład, funktor Kategoria opisuje zakres f * -> g *, czyli Any functor -> Any functornp Tree * -> List *lubTree * -> Tree * .

To, czego nie określa stwierdzenie kategoryczne, opisuje, gdzie wszystko i wszystko jest dozwolone .

W tym przypadku wewnątrz funktorów * -> *aka a -> bnie jest określona, ​​co oznacza Anything -> Anything including Anything else. Gdy moja wyobraźnia przeskakuje do Int -> String, zawiera także Integer -> Maybe Int, a nawet Maybe Double -> Either String Intgdzie a :: Maybe Double; b :: Either String Int.

Zatem zestawienie składa się w następujący sposób:

  • zakres funktora :: f a -> g b(tj. dowolny sparametryzowany typ do dowolnego sparametryzowanego typu)
  • endo + funktor :: f a -> f b(tj. dowolny sparametryzowany typ do tego samego sparametryzowanego typu) ... powiedział inaczej,
  • monoid w kategorii endofunkcji

Gdzie zatem jest moc tego konstruktu? Aby docenić pełną dynamikę, musiałem zobaczyć, że typowe rysunki monoidu (pojedynczy obiekt z czymś, co wygląda jak strzałka tożsamości :: single object -> single object), nie pokazują, że wolno mi użyć strzałki sparametryzowanej z dowolną liczbą wartości monoidów, z obiektu jednego typu dozwolonego w Monoid. Definicja równoważności strzałki endo ~ ~ ignoruje wartość typu funktora, a także rodzaj i wartość najbardziej wewnętrznej warstwy „ładunku”. Zatem równoważność zwraca się truew każdej sytuacji, w której typy funktorów pasują do siebie (np. Nothing -> Just * -> NothingJest równoważne, Just * -> Just * -> Just *ponieważ oba są oba Maybe -> Maybe -> Maybe).

Pasek boczny: ~ na zewnątrz jest koncepcyjny, ale jest najbardziej lewym symbolem w f a. Opisuje również, co „Haskell” wczytuje jako pierwsze (duży obrazek); więc typ jest „zewnętrzny” w stosunku do wartości typu. Relacja między warstwami (łańcuchem odniesień) w programowaniu nie jest łatwa do odniesienia w kategorii. Kategoria zestawu służy do opisywania typów (Int, Strings, Może Int itp.), Która obejmuje kategorię Functor (typy sparametryzowane). Łańcuch referencyjny: Typ Functora, Wartości Functora (elementy zestawu Functora, np. Nic, Tylko), a z kolei wszystko inne, na co wskazuje każda wartość funktora. W kategorii związek jest opisany inaczej, np. return :: a -> m aJest uważany za naturalną transformację z jednego Functora na inny Functor, różny od wszystkiego, co wspomniano do tej pory.

Wracając do głównego wątku, w sumie, dla dowolnego zdefiniowanego produktu tensorowego i wartości neutralnej, stwierdzenie kończy się niesamowicie potężnym konstruktem obliczeniowym zrodzonym z jego paradoksalnej struktury:

  • na zewnątrz pojawia się jako pojedynczy obiekt (np. :: List); statyczny
  • ale wewnątrz pozwala na dużą dynamikę
    • dowolna liczba wartości tego samego typu (np. Empty | ~ NonEmpty) co pasza dla funkcji dowolnego arsenału. Tensor zredukuje dowolną liczbę danych wejściowych do jednej wartości ... dla warstwy zewnętrznej (~ foldnie mówi nic o ładunku)
    • nieskończony zakres zarówno typu, jak i wartości dla najbardziej wewnętrznej warstwy

W Haskell wyjaśnienie stosowalności oświadczenia jest ważne. Moc i wszechstronność tego konstruktu nie ma absolutnie nic wspólnego z monadą samą w sobie . Innymi słowy, konstrukcja nie opiera się na tym, co czyni monadę wyjątkową.

Próbując dowiedzieć się, czy zbudować kod w kontekście współużytkowanym w celu obsługi obliczeń, które są od siebie zależne, w porównaniu z obliczeniami, które można uruchamiać równolegle, ta niesławna instrukcja, o ile opisuje, nie stanowi kontrastu między wyborem Zastosowanie, strzały i monady, ale raczej opis, jak bardzo są takie same. W przypadku podjętej decyzji stwierdzenie jest dyskusyjne.

Jest to często źle rozumiane. Stwierdzenie to opisuje dalej join :: m (m a) -> m ajako iloczyn tensorowy monoidalnego endofunkcji. Nie precyzuje jednak, jak w kontekście tego oświadczenia (<*>)można było również wybrać. To naprawdę przykład sześciu / pół tuzina. Logika łączenia wartości jest dokładnie taka sama; te same dane wejściowe generują takie same dane wyjściowe z każdego z nich (w przeciwieństwie do monoidów Sum i Produkt dla Int, ponieważ generują różne wyniki podczas łączenia Ints).

Podsumowując: monoid w kategorii endofunkcji opisuje:

   ~t :: m * -> m * -> m *
   and a neutral value for m *

(<*>)i (>>=)oba zapewniają jednoczesny dostęp do dwóch mwartości w celu obliczenia pojedynczej wartości zwracanej. Logika zastosowana do obliczenia wartości zwracanej jest dokładnie taka sama. Gdyby nie to, dla różnych kształtów funkcji ich parametryzacji ( f :: a -> bkontra k :: a -> m b) oraz pozycji parametru tego samego typu zwracanej obliczeń (tj, a -> b -> bw porównaniu b -> a -> bdo siebie odpowiednio), podejrzewam, że nie mogliśmy zostać sparametryzowane w monoidal cyfrowym, produkt tensorowy do ponownego użycia w obu definicjach. Jako ćwiczenie, które ma sens, spróbuj wdrożyć ~t, a skończysz na tym (<*>)iw (>>=)zależności od tego, jak zdecydujesz się go zdefiniować forall a b.

Jeśli mój ostatni punkt jest przynajmniej koncepcyjnie prawdziwy, to wyjaśnia dokładną i jedyną różnicę obliczeniową między Applicative i Monad: funkcje, które sparametryzują. Innymi słowy, różnica jest zewnętrzna w stosunku do implementacji tych klas typów.

Podsumowując, z własnego doświadczenia, niesławny cytat Mac Lane'a dostarczył świetnego memu „goto”, który był dla mnie drogowskazem podczas nawigacji przez kategorię, aby lepiej zrozumieć idiomy używane w Haskell. Udało mu się uchwycić zakres potężnej mocy obliczeniowej, doskonale dostępnej w Haskell.

Jednak ironia polega na tym, że po raz pierwszy źle zrozumiałem zastosowanie tego oświadczenia poza monadą i to, co mam nadzieję tu przekazać. Wszystko, co opisuje, okazuje się być podobne między Applicative a Monadami (i innymi strzałkami). To, czego nie mówi, to dokładnie małe, ale użyteczne rozróżnienie między nimi.

- E

Echo Edmunda
źródło
5

Odpowiedzi tutaj doskonale sprawdzają się w definiowaniu zarówno monoidów, jak i monad, jednak nadal nie wydają się odpowiadać na pytanie:

A w mniej ważnej sprawie, czy to prawda, a jeśli tak, to czy mógłbyś podać wyjaśnienie (mam nadzieję, że może to być zrozumiałe dla kogoś, kto nie ma dużego doświadczenia Haskell)?

Sednem materii, której tu brakuje, jest odmienne pojęcie „monoidu”, a dokładniej tak zwana kategoryzacja - pojęcie monoidu w kategorii monoidalnej. Niestety sama książka Mac Lane sprawia, że ​​jest bardzo myląca :

XMówiąc ogólnie , monada jest tylko monoidem w kategorii endofunkcji X, z produktem ×zastąpionym przez kompozycję endofunkcji i jednostką ustawioną przez endofunkcję tożsamości.

Główne zamieszanie

Dlaczego to jest mylące? Ponieważ nie definiuje, co jest „monoidem w kategorii endofunkcji” X. Zamiast tego zdanie to sugeruje umieszczenie monoidu w zbiorze wszystkich endofunkorów wraz z kompozycją funktorów jako operacją binarną i funktorem tożsamości jako jednostką monoidalną. Który działa idealnie dobrze i zamienia w monoid dowolny podzbiór endofunkorów, który zawiera funktor tożsamości i jest zamknięty w składzie funktora.

Nie jest to jednak poprawna interpretacja, której książka nie wyjaśnia na tym etapie. Monada fjest stałym endofunktorem, a nie podzbiorem endofunkorów zamkniętych w składzie. Wspólna konstrukcja jest użycie fdo wytworzenia się monoid poprzez zbiór wszystkich kkrotnie kompozycji f^k = f(f(...))o fz, w tym, k=0który odpowiada tożsamość f^0 = id. A teraz zestaw Swszystkich tych mocy dla wszystkich k>=0jest rzeczywiście monoidem „z iloczynem × zastąpionym przez skład endofunkcji i zestawem jednostek przez endofunkcję tożsamości”.

I jeszcze:

  • Ten monoid Smożna zdefiniować dla dowolnego funktora flub nawet dosłownie dla dowolnej mapy własnej X. Jest to monoid wygenerowany przez f.
  • Monoidalna struktura Spodana przez skład funktora i funktor tożsamości nie ma nic wspólnego z fbyciem lub nie byciem monadą.

Aby jeszcze bardziej skomplikować sprawę, definicja „monoidu w kategorii monoidalnej” znajduje się w dalszej części książki, jak widać ze spisu treści . A jednak zrozumienie tego pojęcia jest absolutnie niezbędne do zrozumienia związku z monadami.

(Surowe) kategorie monoidalne

Idąc do rozdziału VII na Monoids (co przychodzi później niż rozdziale VI na monady), znajdujemy definicję tzw ścisłym kategorii monoidal jako potrójny (B, *, e), gdzie Bjest to kategoria, *: B x B-> Bdo bifunctor (funktor w odniesieniu do każdego składnika z drugiej składowej stałej ) i ejest przedmiotem jednostkowym B, spełniającym zasady asocjatywności i jednostkowe:

(a * b) * c = a * (b * c)
a * e = e * a = a

dla dowolnych obiektów a,b,cz B, a tym samym tożsamości dla wszelkich morfizmów a,b,cz ewyrazami id_e, z morfizmu tożsamości e. Pouczające jest teraz obserwowanie, że w naszym interesującym przypadku, gdzie Bjest kategoria endofunkcji Xz naturalnymi przekształceniami jak morfizmy, *skład funktora i efunktor tożsamości, wszystkie te prawa są spełnione, co można bezpośrednio zweryfikować.

W książce pojawia się definicja „zrelaksowanej” kategorii monoidalnej , w której prawa utrzymują jedynie modulo pewne ustalone naturalne transformacje spełniające tak zwane relacje koherencji , co jednak nie jest ważne w naszych przypadkach kategorii endofunkcjonalnych.

Monoidy w kategoriach monoidalnych

Wreszcie, w sekcji 3 „Monoidy” rozdziału VII podano rzeczywistą definicję:

Monoid cw kategorii monoidalnej (B, *, e)jest przedmiotem Bz dwoma strzałkami (morfizmami)

mu: c * c -> c
nu: e -> c

dzięki czemu 3 diagramy są przemienne. Przypomnijmy, że w naszym przypadku są to morfizmy w kategorii endofunkcji, które są naturalnymi przekształceniami odpowiadającymi precyzyjnie joini returnmonadzie. Połączenie staje się jeszcze wyraźniejsze, gdy uwydatniamy kompozycję *, zastępując c * cc^2, gdzie cjest nasza monada.

Na koniec zauważ, że 3 diagramy przemienne (w definicji monoidu w kategorii monoidalnej) są napisane dla ogólnych (nie ścisłych) kategorii monoidalnych, podczas gdy w naszym przypadku wszystkie naturalne transformacje powstałe w ramach kategorii monoidalnej są w rzeczywistości tożsamościami. To sprawi, że diagramy będą dokładnie takie same jak te w definicji monady, dzięki czemu korespondencja będzie kompletna.

Wniosek

Podsumowując, każda monada z definicji jest endofunkcją, a zatem przedmiotem w kategorii endofunkcji, gdzie monady joini returnoperatory spełniają definicję monoidu w tej konkretnej (ścisłej) monoidalnej kategorii . Odwrotnie, każda monoid w monoidalnej kategorii endofunkorów jest z definicji potrójnym (c, mu, nu)składającym się z obiektu i dwóch strzałek, np. Naturalnych przekształceń w naszym przypadku, spełniających te same prawa co monada.

Na koniec zwróć uwagę na kluczową różnicę między (klasycznymi) monoidami a bardziej ogólnymi monoidami w kategoriach monoidalnych. Dwie strzałki mui nupowyżej nie są już operacją binarną i jednostką w zestawie. Zamiast tego masz jeden stały endofunkor c. Sam skład funktora *i funktor tożsamości nie zapewniają pełnej struktury potrzebnej monadzie, pomimo tej mylącej uwagi w książce.

Innym rozwiązaniem byłoby porównać ze standardowym monoid Cwszystkich samorządów map zestawu A, gdzie operacja binarna jest skład, który można zobaczyć na mapę standardowy iloczyn kartezjański C x Cdo C. Przechodząc do sklasyfikowanego monoidu, zastępujemy iloczyn kartezjański xskładem funktora *, a operację binarną zastępuje naturalna transformacja muz c * cna c, czyli zbiór joinoperatorów

join: c(c(T))->c(T)

dla każdego obiektu T(wpisz programowanie). A elementy tożsamości w klasycznych monoidach, które można zidentyfikować za pomocą obrazów map ze stałego zestawu jednopunktowego, zostaną zastąpione kolekcją returnoperatorów

return: T->c(T) 

Ale teraz nie ma już produktów kartezjańskich, więc nie ma par elementów, a zatem nie ma operacji binarnych.

Dmitri Zaitsev
źródło
Jaka jest zatem twoja odpowiedź na pytanie „czy to prawda”? Czy to prawda, że ​​monada jest monoidą w kategorii endofunkorów? A jeśli tak, jaki jest związek między pojęciem teorii kategorii monoidu i monoidu algebraicznego (zbioru z mnożeniem asocjacyjnym i jednostką)?
Alexander Belopolsky