Monada to tylko monoid w kategorii endofunktorów, w czym problem?

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

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

Z nich, RankNTypes jest jedynym, który jest absolutnie niezbędny do poniżej. napisałem kiedyś Wyjaśnienie RankNTypes, które niektórym wydaje się być przydatne , więc odnoszę się do tego.

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

Monada jest...

• endofunktor, T: X - > X
• naturalna przemiana, μ: T × T - > T, gdzie × oznacza skład funktora
• naturalna przemiana, η: I - > T, gdzie I to endofunktor tożsamości na X

...spełnianie tych praw:

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

Jak przetłumaczymy to na kod Haskella? Cóż, zacznijmy od pojęcia transformacja naturalna :

-- | 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 postaci f :-> g jest analogiczny do typu funkcji, ale zamiast myśleć o niej jako o funkcji pomiędzy dwoma typami (rodzaju *), pomyśl o niej jako o morfizmie pomiędzy dwoma {55]} funktorami (każdy 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 pewnego typu f x do innego typu g x, tak że zmienna typu x jest " niedostępna" do rozmówcy. Na przykład, sort :: Ord a => [a] -> [a] nie można przekształcić w naturalną transformację, ponieważ jest "wybredne", o jakich typach możemy utworzyć instancję dla a. Jednym z intuicyjnych sposobów, w jaki często o tym myślę, jest: {]}

• funktor jest sposobem operowania na zawartości czegoś bez dotykania struktury .
• naturalna transformacja jest sposobem operowania na strukturze czegoś bez dotykania i patrzenia na treść .

Teraz, z tym na uboczu, zajmijmy się klauzulami definicji.

Pierwsza klauzula to " endofunktor, T: X - > X."Cóż, każdy Functor w Haskell jest endofunktor w tym, co ludzie nazywają" kategorią Haskella", którego obiekty są typami Haskella (rodzaju *) i których morfizmami są funkcje Haskella. Brzmi to jak skomplikowane stwierdzenie, ale w rzeczywistości jest bardzo trywialne. Wszystko to oznacza, że Functor f :: * -> * daje możliwość konstruowania typu f a :: * dla dowolnego a :: * oraz funkcji fmap f :: f a -> f b z dowolnego f :: a -> b i że są one zgodne z prawami functora.

Druga klauzula: Identity funktor w Haskell (który jest dostarczany wraz z platformą, więc możesz go zaimportować) jest zdefiniowany w ten sposób:

newtype Identity a = Identity { runIdentity :: a }

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

Więc naturalna przemiana η: I - > T Z definicji Toma Crocketta można zapisać w ten sposób dla każdej instancji Monad t:

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

Trzecia klauzula: skład z dwóch funkcji w Haskell można zdefiniować w ten sposób (który również pochodzi z platformy):

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)

Więc naturalna przemiana μ: T × T - > T Z definicji Toma Crocketta można napisać tak:

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

Twierdzenie, że jest to monoid w kategorii endofunktorów oznacza, że Compose (częściowo stosowane tylko do dwóch pierwszych parametrów) jest asocjacyjne, a Identity jest jego elementem tożsamościowym. Tzn., że następujące izomorfizmy trzymać:

• 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ż Compose i Identity są zdefiniowane jako newtype, A Raporty Haskella definiują semantykę newtype jako izomorfizm pomiędzy zdefiniowanym typem a typem argumentu konstruktora danych newtype. 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.

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 kwestii, czy to prawda i jeśli tak, czy mógłbyś podać wyjaśnienie(mam nadzieję, że takie, które może być zrozumiane przez kogoś, kto nie ma zbyt dużego doświadczenia Haskell)?

Sednem sprawy, której tu brakuje, jest odmienne pojęcie "monoidu", tzw. Kategoryzacja dokładniej -- jeden z monoidów w kategorii monoidów. Niestety sama książka Maca Lane ' a sprawia, że jest to bardzo mylące :

Monada w Xjest monoidem w kategorii endofunktorów w X, z produktem × zastąpionym składem endofunktorów i jednostką ustaloną przez endofunktor tożsamości.

Główne zamieszanie

Dlaczego to jest mylące? Ponieważ nie definiuje, co jest "monoidem w kategorii endofunktorów" X. Zamiast tego, to zdanie sugeruje wzięcie monoidu wewnątrz zbioru wszystkich endofunktorów wraz ze składem funktora jako operacji binarnej i funktora tożsamości jako jednostki monoidalnej. Który działa idealnie dobrze i zamienia się w monoid dowolny podzbiór endofunkcji, który zawiera funktor tożsamości i jest zamknięty pod składem funktora.

Nie jest to jednak prawidłowa interpretacja, której książka nie wyjaśnia na tym etapie. Monada f jest stałą endofunktor, a nie podzbiorem z endofunkcji zamkniętych w ramach kompozycji. Powszechnie stosowaną konstrukcją jest użycie f do wygenerowania monoidu poprzez wzięcie ze sobą zbioru wszystkich k-składowych składowych f^k = f(f(...)) z f, łącznie z k=0, który odpowiada tożsamości f^0 = id. I teraz zbiór S wszystkich tych potęg dla wszystkich k>=0 jest rzeczywiście monoidem "z iloczynem × zastąpionym składem endofunktorów i jednostką ustaloną przez endofunktor tożsamości".

A jednak:

• ten monoid S może być zdefiniowany dla dowolnego funktora f lub nawet dosłownie dla dowolnego odwzorowania X. Jest to monoid generowany przez f.
• monoidalna struktura S dana przez skład funktora i funktor tożsamości nie ma nic wspólnego z f byciem lub nie byciem monadą.

I aby uczynić rzeczy bardziej mylące, definicja "monoid w kategorii monoidalnej" pojawia się później w książce, Jak widać zspis treści {76]}. A jednak zrozumienie tego pojęcia jest absolutnie krytyczne dla zrozumienia związku z monadami.

(ścisłe) kategorie monoidalne

Przechodząc do rozdziału VII o Monoidach (który przychodzi później niż Rozdział VI O Monoidach), znajdujemy definicję tak zwanej ścisłej kategorii monoidów jako potrójnej (B, *, e), gdzie B jest kategorią, *: B x B-> B A bifunctor (funktor w odniesieniu do każdego składnika z innym składnikiem ustalonym) i e jest obiektem jednostkowym w B, spełniającym Asocjacja i jednostka prawa:

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

Dla dowolnych obiektów a,b,c z B i tych samych tożsamości dla dowolnych morfizmów a,b,c Z e zastąpionymi przez id_e, morfizmem tożsamościowym e. Warto teraz zauważyć, że w naszym przypadku, gdzie B jest kategorią endofunktorów X z naturalnymi transformacjami jako morfizmami, * składem funktora i e funktorem tożsamości, wszystkie te prawa są spełnione, co można bezpośrednio zweryfikować.

Co przychodzi po w książka jest definicją" zrelaksowanej " kategorii monoidalnej , gdzie prawa posiadają tylko modulo pewne stałe przekształcenia naturalne spełniające tzw. relacje koherencyjne , co jednak nie jest ważne dla naszych przypadków kategorii endofunktorowych.

Monoidy w kategoriach monoidalnych

W rozdziale VII sekcja 3" Monoidy " podaje się faktyczną definicję:]}

Monoid c w kategorii monoidalnej (B, *, e) jest obiektem B z dwiema strzałkami (morfizmy)

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

Wykonanie 3 diagramów. Przypomnijmy, że w naszym przypadku są to morfizmy z kategorii endofunkcji, które są naturalnymi transformacjami odpowiadającymi dokładnie join i return dla monady. Połączenie staje się jeszcze wyraźniejsze, gdy uczynimy kompozycję * bardziej wyraźną, zastępując c * c przez c^2, gdzie c jest naszą monadą.

Na koniec zauważ, że 3 diagramy komutacyjne (w definicji monoidy w Kategoria monoidalna) są zapisywane dla ogólnych (nie ścisłych) kategorii monoidalnych, podczas gdy w naszym przypadku wszystkie naturalne przekształcenia powstające 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.

Podsumowanie

Podsumowując, każda monada jest z definicji endofunktorem, stąd obiekt w kategorii endofunktorów, gdzie operatory monadyczne join i return spełniają definicję monoidu w tej szczególnej (ścisłej) kategorii monoidów . Na odwrót, każda monoid z kategorii monoidalnych endofunktorów jest z definicji potrójną (c, mu, nu) składającą się z obiektu i dwóch strzałek, np. naturalnych przekształceń w naszym przypadku, spełniających te same prawa co monada.

Wreszcie, zauważ kluczową różnicę między (klasycznymi) monoidami a bardziej ogólnymi monoidami w kategoriach monoidalnych. Dwie strzałki mu i nu powyżej nie są już operacja binarna i jednostka w zbiorze. Zamiast tego masz jeden stały endofunktor c. W monadzie nie ma kompletnej struktury, która byłaby potrzebna, pomimo tej mylącej uwagi w książce.

Innym podejściem byłoby porównanie ze standardowym monoidem C wszystkich samo-map zbioru A, gdzie operacja binarna jest składem, który można zobaczyć mapując standardowy iloczyn kartezjański C x C na C. Przechodząc do skategoryzowanej monoidy zamieniamy iloczyn kartezjański x składem funktora *, a operacja binarna zostaje zastąpiona transformacją naturalną mu z c * c do c, czyli zbiór join operatorów

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

Dla każdego obiektu T (wpisz w programowaniu). W 1999 roku w ramach programu "Horyzont 2020" w ramach programu "Horyzont 2020" zrealizowano program ramowy "Horyzont 2020" -program ramowy w zakresie badań naukowych i innowacji (2007-2013) i "Horyzont 2020".]} operatory

return: T->c(T) 

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

Przyszedłem do tego postu, aby lepiej zrozumieć wnioskowanie niesławnego cytatu z teorii kategorii Mac Lane ' A Dla pracującego Matematyka.

W opisywaniu tego, czym coś jest, często równie przydatne jest opisywanie tego, czym nie jest.

Fakt, że Mac Lane używa opisu do opisania monady, może sugerować, że opisuje ona coś unikalnego dla monad. Wytrzymaj ze mną. Aby rozwinąć szersze zrozumienie tego stwierdzenia, uważam, że potrzebuje aby było jasne, że jest on nie opisując coś, co jest unikalne dla monad; stwierdzenie to opisuje równie dobrze m.in. Applicative i Arrows. Z tego samego powodu możemy mieć dwa monoidy na Int( Suma i produkt), możemy mieć kilka monoidów na X w kategorii endofunktorów. Ale jest jeszcze więcej podobieństw.

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

• endo = > Dowolna strzałka, czyli morfizm, który zaczyna się i kończy w tym samym miejsce
• functor = > Dowolna strzałka, czyli morfizm między dwiema kategoriami

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

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

Oświadczenie używa " kategorii..."To określa zakres Oświadczenia. Jako przykład kategoria Functora opisuje zakres f * -> g *, tj. Any functor -> Any functor, np. Tree * -> List * lub Tree * -> Tree *.

Co kategoryczne stwierdzenie nie określa gdzie wszystko i wszystko jest dozwolone .

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

Więc twierdzenie składa się w następujący sposób:

• zakres functora :: f a -> g b (tj. dowolny parametryzowany typ na dowolny parametryzowany Typ)
• endo + functor :: f a -> f b (tzn. dowolny parametryzowany typ do tego samego parametryzowanego typu)... powiedział inaczej,
• monoid w kategorii endofunktor

Gdzie więc jest moc tej konstrukcji? Aby docenić pełną dynamikę, musiałem zobaczyć, że typowe rysunki monoidu (pojedynczego obiektu z czymś, co wygląda jak strzałka tożsamości, :: single object -> single object), nie ilustrują, że mogę używać strzałki parametryzowanej za pomocą dowolnej liczby wartości monoidów, z tego co pamiętam, to jeden obiekt typu dozwolony w monoidzie. Endo, ~ identity arrow definicja równoważności ignoruje wartość typu functora oraz zarówno typ, jak i wartość najbardziej wewnętrznej warstwy "payload". Tak więc równoważność zwraca true w każdej sytuacji, w której typy funkcyjne pasują do siebie (np. {[19] } jest równoważna Just * -> Just * -> Just *, ponieważ oba są Maybe -> Maybe -> Maybe).

Sidebar: ~ Na zewnątrz jest pojęciowy, ale jest lewym symbolem w f a. Opisuje również, co "Haskell" czyta-w pierwszym (duży obrazek); więc typ jest "na zewnątrz" w odniesieniu do wartości typu. Związek między warstwami (łańcuchiem odniesień) w programowaniu nie jest łatwy do odniesienia w kategorii. Kategoria zbioru służy do opisywania typów (Int, Strings, Maybe Int itd.), która obejmuje kategorię funktora (typy parametryzowane). Łańcuch odniesienia: Typ Functora, wartości Functora (elementy zbioru tego Functora, np. nic, Tylko), a z kolei Wszystko inne, na co wskazuje każda wartość functora. W kategorii relacja jest opisana inaczej, np. return :: a -> m a jest uważana za naturalną transformację z jednego funktora do drugiego funktora, różniącą się od wszystkiego, o czym do tej pory wspomniano.

W związku z tym, że tensor nie jest zdefiniowany jako iloczyn tensorowy i wartość neutralna, twierdzenie kończy się opisem niezwykle potężnej konstrukcji obliczeniowej zrodzonej z jej paradoksalnej struktury:]}

Na zewnątrz pojawia się jako pojedynczy obiekt (np.]}); static
• ale wewnątrz, pozwala na wiele dynamiki
  • dowolna liczba wartości tego samego typu (np. Empty / ~NonEmpty) jako źródło funkcji o dowolnej arytmetyce. Iloczyn tensorowy zmniejszy dowolną liczbę wejść do jednej wartości... dla warstwy zewnętrznej (~fold, która nie mówi nic o ładunku)
  • infinite range of both the type and values for the inner most layer

W Haskell, Wyjaśnienie stosowalności stwierdzenia to ważne. Moc i wszechstronność tej konstrukcji nie ma absolutnie nic wspólnego z monadą[40]}per se [41]}. Innymi słowy, konstrukcja nie opiera się na tym, co czyni monadę wyjątkową.

Próbując dowiedzieć się, czy budować Kod ze współdzielonym kontekstem, aby wspierać obliczenia, które zależą od siebie, w porównaniu z obliczeniami, które mogą być uruchamiane równolegle, to niesławne stwierdzenie, w takim stopniu, w jakim opisuje, nie stanowi kontrastu między wyborem aplikacji, strzałek i Monady, ale raczej jest opisem tego, jak bardzo są takie same. W przypadku rozpatrywanej decyzji oświadczenie jest sporne.

To jest często źle rozumiane. Twierdzenie opisuje join :: m (m a) -> m a jako iloczyn tensorowy dla monoidalnego endofunktora. Nie wyjaśnia jednak, w jaki sposób, w kontekście tego stwierdzenia, mógł być również wybrany. To naprawdę jest przykład sześciu / pół tuzina. Logika łączenia wartości jest dokładnie taka sama; to samo wejście generuje to samo wyjście z każdego (w przeciwieństwie do Monoidów sumy i produktu dla Int, ponieważ generują różne wyniki przy łączeniu Int).

Podsumowując: Monoid w kategorii endofunktorów opisuje:

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

(<*>) i (>>=) oba zapewniają jednoczesny dostęp do dwóch wartości m w celu obliczenia pojedynczej wartości zwracanej. Logika używana do obliczania zwracanej wartości jest dokładnie taka sama. Gdyby nie różne kształty funkcji, które parametryzują (f :: a -> b versus k :: a -> m b) i pozycja parametru o tym samym typie zwrotu obliczeń (tj. a -> b -> b versus b -> a -> b dla każdego odpowiednio), podejrzewam, że mogliśmy sparametryzować logikę monoidalną, iloczyn tensorowy, do ponownego użycia w obu definicjach. Jako ćwiczenie do rzeczy, spróbuj zaimplementować ~t, a skończysz z (<*>) i (>>=) w zależności od tego, jak zdecydujesz się go zdefiniować forall a b.

Jeśli mój ostatni punkt jest przynajmniej konceptualnie prawdziwy, to wyjaśnia dokładnie i tylko różnice obliczeniowe między aplikacjami i monadami: funkcje, które parametryzują. 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ł mi świetnego "goto" mema, drogowskazu do odniesienia podczas poruszania się po kategorii, aby lepiej zrozumieć idiomy używane w Haskell. Udaje mu się uchwycić zakres potężnych mocy obliczeniowych wykonanych cudownie dostępne w Haskell.

[39]}jest jednak ironia w tym, jak po raz pierwszy źle zrozumiałam przydatność stwierdzenia poza monadą, i co mam nadzieję, że się tutaj znalazło. Wszystko, co opisuje, okazuje się być tym, co jest podobne między Aplikowcem a monadami (i m.in. strzałkami). To, czego nie mówi, To właśnie małe, ale użyteczne rozróżnienie między nimi.

- E

Uwaga: nie, to nieprawda. W pewnym momencie pojawił się komentarz do tej odpowiedzi od samego dana Piponiego, mówiący, że przyczyna i skutek są dokładnie odwrotne, że napisał swój artykuł w odpowiedzi na quip Jamesa Iry ' ego. Ale wydaje się, że został usunięty, być może przez jakiegoś kompulsywnego sprzątacza.

Poniżej moja oryginalna odpowiedź.

---

Jest to możliwe, że Iry przeczytał od Monoidów do Monad, post w którym Dan Piponi (sigfpe) wywodzi monady z monoidy w Haskell, z wieloma dyskusjami na temat teorii kategorii i wyraźną wzmianką o " kategorii endofunktorów na Hask ". W każdym razie każdy, kto zastanawia się, co to znaczy, że monada jest monoidem w kategorii endofunktorów, może skorzystać z lektury tej pochodnej.