Słyszałem kilka razy termin „węgiel kamienny” w programowaniu funkcjonalnym i kręgach PLT, szczególnie gdy dyskusja dotyczy przedmiotów, comonad, soczewek itp. Googlowanie tego terminu daje strony, które zawierają matematyczny opis tych struktur, co jest dla mnie prawie niezrozumiałe. Czy ktoś może wyjaśnić, co oznaczają węgiel drzewny w kontekście programowania, jakie jest ich znaczenie i jak odnoszą się do obiektów i comonad?
scala
haskell
functional-programming
category-theory
recursion-schemes
missingfaktor
źródło
źródło
Odpowiedzi:
Algebry
Myślę, że punktem wyjścia byłoby zrozumienie idei algebry . To tylko uogólnienie struktur algebraicznych, takich jak grupy, pierścienie, monoidy i tak dalej. Przez większość czasu te rzeczy są wprowadzane w postaci zestawów, ale ponieważ jesteśmy wśród przyjaciół, będę rozmawiać o typach Haskell. (Nie mogę się jednak oprzeć użyciu greckich liter - sprawiają, że wszystko wygląda fajniej!)
Algebra jest więc typem
τ
z pewnymi funkcjami i tożsamościami. Funkcje te przyjmują różną liczbę argumentów typuτ
i generująτ
: bez pośpiechu, wszystkie wyglądają(τ, τ,…, τ) → τ
. Mogą również mieć „tożsamość” - elementyτ
, które zachowują się w określony sposób z niektórymi funkcjami.Najprostszym tego przykładem jest monoid. Monoid to dowolny typ
τ
z funkcjąmappend ∷ (τ, τ) → τ
i tożsamościąmzero ∷ τ
. Inne przykłady obejmują takie rzeczy jak grupy (które są jak monoidy, z wyjątkiem dodatkowejinvert ∷ τ → τ
funkcji), pierścienie, siatki i tak dalej.Wszystkie funkcje działają,
τ
ale mogą mieć różne arie. Możemy zapisać je jakoτⁿ → τ
, gdzieτⁿ
mapy do krotkin
τ
. W ten sposób sensowne jest myślenie o tożsamości jako oτ⁰ → τ
miejscu, w którymτ⁰
jest tylko pusta krotka()
. Możemy więc teraz uprościć pomysł algebry: jest to po prostu jakiś typ z pewną liczbą funkcji.Algebra to po prostu powszechny wzorzec w matematyce, który został „wyodrębniony”, tak jak robimy to z kodem. Ludzie zauważyli, że cała masa interesujących rzeczy - wspomniane monoidy, grupy, kraty itd. - wszystkie mają podobny wzór, więc wyodrębnili go. Zaleta robienia tego jest taka sama, jak w przypadku programowania: tworzy dowody wielokrotnego użytku i ułatwia pewne rodzaje rozumowania.
Algebry F.
Jednak jeszcze nie skończyliśmy z faktoringiem. Do tej pory mamy wiele funkcji
τⁿ → τ
. Możemy właściwie zrobić sztuczkę, aby połączyć je wszystkie w jedną funkcję. W szczególności spójrzmy na monoidy: mamymappend ∷ (τ, τ) → τ
imempty ∷ () → τ
. Możemy zamienić je w jedną funkcję za pomocą typu sumy—Either
. Wyglądałoby to tak:Możemy faktycznie korzysta z tej transformacji wielokrotnie łączyć wszystkie te
τⁿ → τ
funkcje w jeden, dla dowolnej algebry. (W rzeczywistości, możemy zrobić to dla dowolnej liczby funkcjia → τ
,b → τ
i tak dalej za każdya, b,…
).To pozwala nam mówić o algebrach jako typach
τ
z jedną funkcją, od pewnego bałaganuEither
s do jednegoτ
. Dla monoids ten bałagan jest:Either (τ, τ) ()
; dla grup (które mają dodatkoweτ → τ
działanie), to jest:Either (Either (τ, τ) τ) ()
. Jest to inny typ dla każdej innej struktury. Co więc mają wspólnego wszystkie te typy? Najbardziej oczywistą rzeczą jest to, że wszystkie są tylko sumami produktów - algebraicznymi typami danych. Na przykład dla monoidów możemy utworzyć argument typu monoid, który działa dla dowolnego monoidu τ:Możemy zrobić to samo dla grup, pierścieni, krat i wszystkich innych możliwych struktur.
Co jeszcze jest specjalnego w tych wszystkich typach? Cóż, oni wszyscy
Functors
! Na przykład:Abyśmy mogli jeszcze bardziej uogólnić naszą ideę algebry. To tylko jakiś typ
τ
z funkcjąf τ → τ
funktoraf
. W rzeczywistości moglibyśmy zapisać to jako klasę:Jest to często nazywane „algebrą F”, ponieważ jest określane przez funktor
F
. Gdybyśmy mogli częściowo zastosować klasy, moglibyśmy zdefiniować coś takiegoclass Monoid = Algebra MonoidArgument
.Coalgebras
Mam nadzieję, że dobrze orientujesz się, czym jest algebra i jak to jest po prostu uogólnienie normalnych struktur algebraicznych. Czym jest F-carbongebra? Cóż, co implikuje, że jest to „dualność” algebry - to znaczy bierzemy algebrę i przerzucamy kilka strzałek. Widzę tylko jedną strzałkę w powyższej definicji, więc po prostu odwrócę to:
I to wszystko! Wniosek ten może wydawać się nieco niepoprawny (heh). Mówi ci, czym jest carbongebra, ale tak naprawdę nie daje wglądu w to, jak jest przydatny i dlaczego nas to obchodzi. Dojdę do tego za chwilę, kiedy znajdę lub wymyślę dobry przykład lub dwa: P.
Klasy i przedmioty
Po krótkiej lekturze wydaje mi się, że mam dobry pomysł, jak używać węgielników do reprezentowania klas i obiektów. Mamy typ,
C
który zawiera wszystkie możliwe wewnętrzne stany obiektów w klasie; sama klasa jest węgielnicą, wC
której określa się metody i właściwości obiektów.Jak pokazano w przykładzie algebry, jeśli mamy kilka funkcji takich jak
a → τ
ib → τ
dla dowolneja, b,…
, możemy połączyć je wszystkie w jedną funkcję zaEither
pomocą typu sumy. Podwójny „pojęcie” będzie łącząc kilka funkcji typuτ → a
,τ → b
i tak dalej. Możemy to zrobić za pomocą dualu typu suma - typ produktu. Biorąc pod uwagę dwie powyższe funkcje (wywołanef
ig
), możemy utworzyć jedną taką:Ten typ
(a, a)
jest funktorem w prosty sposób, więc z pewnością pasuje do naszego pojęcia „F-carbongebra”. Ta szczególna sztuczka pozwala nam spakować kilka różnych funkcji - lub, w przypadku OOP, metod - w jedną funkcję typuτ → f τ
.Elementy naszego typu
C
reprezentują wewnętrzny stan obiektu. Jeśli obiekt ma pewne czytelne właściwości, muszą być w stanie zależeć od stanu. Najbardziej oczywistym sposobem na to jest uczynienie ich funkcjąC
. Więc jeśli chcemy mieć właściwość length (np.object.length
), Mielibyśmy funkcjęC → Int
.Chcemy metod, które mogą przyjmować argument i modyfikować stan. Aby to zrobić, musimy wziąć wszystkie argumenty i stworzyć nowy
C
. Wyobraźmy sobiesetPosition
metodę, która trwax
iy
współrzędnych:object.setPosition(1, 2)
. To będzie wyglądać następująco:C → ((Int, Int) → C)
.Ważnym wzorem jest tutaj to, że „metody” i „właściwości” obiektu przyjmują sam obiekt jako swój pierwszy argument. To jest tak samo jak
self
parametr w Pythonie i jak domniemanethis
wiele innych języków. Coalgebra zasadniczo tylko oddaje zachowanie biorącself
parametr: to właśnie pierwszaC
wC → F C
to.Złóżmy to wszystko razem. Wyobraźmy sobie klasę z
position
właściwością,name
właściwością isetPosition
funkcją:Potrzebujemy dwóch części do reprezentowania tej klasy. Po pierwsze, musimy przedstawić wewnętrzny stan obiektu; w tym przypadku zawiera tylko dwa
Int
si aString
. (To jest nasz typC
.) Następnie musimy wymyślić carbongebra reprezentującą klasę.Mamy dwie właściwości do napisania. Są dość trywialne:
Teraz musimy tylko móc zaktualizować pozycję:
To jest jak klasa Python z wyraźnymi
self
zmiennymi. Teraz, gdy mamy wieleself →
funkcji, musimy połączyć je w jedną funkcję dla funkcji węgla. Możemy to zrobić za pomocą prostej krotki:Typ
((Int, Int), String, (Int, Int) → c)
-dla dowolnyc
-jest funktor, więccoop
ma formę chcemy:Functor f ⇒ C → f C
.Biorąc to pod uwagę,
C
wraz zcoop
formą carbongebra, która określa klasę, którą podałem powyżej. Możesz zobaczyć, w jaki sposób możemy użyć tej samej techniki do określenia dowolnej liczby metod i właściwości dla naszych obiektów.To pozwala nam używać rozumowania węgielgebraicznego do radzenia sobie z klasami. Na przykład możemy wprowadzić pojęcie „homomorfizmu F-carbongebra” do reprezentowania przekształceń między klasami. Jest to przerażająco brzmiący termin, który oznacza po prostu transformację między węgielnicami, która zachowuje strukturę. To znacznie ułatwia myślenie o mapowaniu klas na inne klasy.
Krótko mówiąc, F-węgiel reprezentuje klasę, posiadając szereg właściwości i metod, które wszystkie zależą od
self
parametru zawierającego stan wewnętrzny każdego obiektu.Inne kategorie
Do tej pory mówiliśmy o algebrach i węgielach jako typach Haskella. Algebra jest tylko typem
τ
z funkcją,f τ → τ
a carbongebra jest tylko typemτ
z funkcjąτ → f τ
.Jednak nic tak naprawdę łączy te pomysły Haskell per se . W rzeczywistości są one zwykle wprowadzane w kategoriach zbiorów i funkcji matematycznych, a nie typów i funkcji Haskella. Rzeczywiście, możemy uogólnić te pojęcia na dowolne kategorie!
Możemy zdefiniować algebrę F dla jakiejś kategorii
C
. Po pierwsze, potrzebujemy funktoraF : C → C
- to znaczy endofunkturza . (Wszystko HaskellFunctor
s faktycznie endofunctors zHask → Hask
). Następnie, algebra jest tylko obiektA
odC
z morfizmuF A → A
. Węgiel jest taki sam, z wyjątkiemA → F A
.Co zyskujemy, rozważając inne kategorie? Cóż, możemy wykorzystać te same pomysły w różnych kontekstach. Jak monady. W Haskell monada jest rodzajem
M ∷ ★ → ★
z trzema operacjami:Ta
map
funkcja jest tylko dowodem na to, żeM
jest toFunctor
. Możemy więc powiedzieć, że monada to po prostu funktor z dwiema operacjami:return
ijoin
.Functory same tworzą kategorię, a morfizmy między nimi są tak zwanymi „naturalnymi przemianami”. Naturalna transformacja jest tylko sposobem na przekształcenie jednego funktora w inny, przy jednoczesnym zachowaniu jego struktury. Oto fajny artykuł, który pomaga wyjaśnić ten pomysł. Mówi o tym
concat
, co dotyczy tylkojoin
list.W przypadku funktorów Haskell skład dwóch funktorów jest sam funktorem. W pseudokodzie możemy napisać to:
Pomaga nam to myśleć o
join
mapowaniuf ∘ f → f
. Rodzajjoin
jest∀α. f (f α) → f α
. Intuicyjnie możemy zobaczyć, jak funkcję poprawną dla wszystkich typówα
można traktować jako transformacjęf
.return
jest podobną transformacją. Jego typ to∀α. α → f α
. Wygląda to inaczej - pierwszyα
nie jest funktorem! Na szczęście, możemy rozwiązać ten problem przez dodanie istnieje funktor tożsamości:∀α. Identity α → f α
. Takareturn
jest transformacjaIdentity → f
.Teraz możemy myśleć o monadzie jako o algebrze opartej na funktorze
f
z operacjamif ∘ f → f
iIdentity → f
. Czy to nie wygląda znajomo? Jest bardzo podobny do monoidu, który był po prostu jakimś rodzajemτ
operacjiτ × τ → τ
i() → τ
.Więc monada jest jak monoid, tyle że zamiast typu mamy funktor. To ten sam rodzaj algebry, tylko w innej kategorii. (Z tego, co wiem, wyrażenie „monada jest po prostu monoidą w kategorii endofunkcji”).
Teraz mamy te dwie operacje:
f ∘ f → f
iIdentity → f
. Aby uzyskać odpowiednią węgielnicę, po prostu odwracamy strzałki. To daje nam dwie nowe operacje:f → f ∘ f
if → Identity
. Możemy zamienić je na typy Haskella, dodając zmienne typu jak wyżej, dając nam∀α. f α → f (f α)
i∀α. f α → α
. Wygląda to tak jak definicja comonad:Więc comonad jest wtedy coalgebra w kategorii endofunctors.
źródło
(,)
i funktorem tożsamości()
. Obiekt monoidu w kategorii monoidalnej to obiekt ze strzałkami odpowiadającymi algebrze monoidalnej, który opisuje obiekt monoidalny w Hask o typach produktów jako strukturze monoidalnej. Obiekt monoid w kategorii endofunkcji na C jest monadą na C, więc tak, twoje zrozumienie jest prawidłowe. :]Algebry F i algebry F są strukturami matematycznymi, które odgrywają kluczową rolę w rozumowaniu typów indukcyjnych (lub typów rekurencyjnych ).
Algebry F.
Zaczniemy od algebry F. Spróbuję być tak prosty, jak to możliwe.
Chyba wiesz, co to jest typ rekurencyjny. Na przykład jest to typ listy liczb całkowitych:
Oczywiste jest, że jest rekurencyjne - w rzeczywistości jego definicja odnosi się do samego siebie. Jego definicja składa się z dwóch konstruktorów danych, które mają następujące typy:
Zauważ, że napisałem typ
Nil
jako() -> IntList
, a nie po prostuIntList
. Są to w rzeczywistości typy równoważne z teoretycznego punktu widzenia, ponieważ()
typ ma tylko jednego mieszkańca.Jeśli napiszemy podpisy tych funkcji w bardziej teoretyczny sposób, otrzymamy
gdzie
1
jest zestaw jednostek (zestaw z jednym elementem), aA × B
operacja jest iloczynem krzyżowym dwóch zestawówA
iB
(to znaczy zestawu par, w(a, b)
któryma
przechodzą wszystkie elementyA
ib
przechodzą przez wszystkie elementyB
).Rozłączne połączenie dwóch zbiorów
A
iB
jest zbioremA | B
będącym połączeniem zbiorów{(a, 1) : a in A}
i{(b, 2) : b in B}
. Zasadniczo jest to zestaw wszystkich elementów z obuA
iB
, ale z każdym z tych elementów „oznaczonymi” jako należącymi do jednegoA
lub jednego z nichB
, więc kiedy wybieramy dowolny element zA | B
, od razu będziemy wiedzieć, czy ten element pochodziA
czy zB
.Możemy „połączyć”
Nil
iCons
funkcje, aby utworzyły jedną funkcję działającą na zestawie1 | (Int × IntList)
:Rzeczywiście, jeśli
Nil|Cons
funkcja jest zastosowana do()
wartości (która oczywiście należy do1 | (Int × IntList)
zestawu), zachowuje się tak, jakby byłaNil
; jeśliNil|Cons
jest zastosowany do dowolnej wartości typu(Int, IntList)
(takie wartości są również w zestawie1 | (Int × IntList)
, zachowuje się jakCons
.Teraz rozważ inny typ danych:
Ma następujące konstruktory:
które można również połączyć w jedną funkcję:
Można zauważyć, że obie te
joined
funkcje mają podobny typ: oba wyglądajągdzie
F
jest rodzajem transformacji, która trwa nasz typ i daje bardziej złożony typ, który składa sięx
i|
operacje, zwyczajówT
i ewentualnie inne typy. Na przykład dlaIntList
iIntTree
F
wygląda następująco:Od razu możemy zauważyć, że każdy typ algebraiczny można zapisać w ten sposób. Rzeczywiście dlatego nazywane są „algebraicznymi”: składają się z szeregu „sum” (związków) i „produktów” (produktów krzyżowych) innych typów.
Teraz możemy zdefiniować algebrę F. Algebra F to tylko para
(T, f)
, gdzieT
jest jakiś typ if
jest funkcją typuf :: F T -> T
. W naszych przykładach F-algebrami są(IntList, Nil|Cons)
i(IntTree, Leaf|Branch)
. Zauważ jednak, że pomimo tego typuf
funkcji jest taki sam dla każdego FT
if
same mogą być dowolne. Na przykład(String, g :: 1 | (Int x String) -> String)
lub(Double, h :: Int | (Double, Double) -> Double)
dla niektórychg
ih
są również algebrami F dla odpowiednich F.Następnie możemy wprowadzić homomorfizmy algebry F, a następnie początkowe algebry F , które mają bardzo przydatne właściwości. W rzeczywistości
(IntList, Nil|Cons)
jest to początkowa algebra F1 i(IntTree, Leaf|Branch)
jest to początkowa algebra F2. Nie przedstawię dokładnych definicji tych terminów i właściwości, ponieważ są one bardziej złożone i abstrakcyjne niż jest to konieczne.Niemniej fakt, że powiedzmy,
(IntList, Nil|Cons)
jest algebrą F, pozwala nam zdefiniowaćfold
funkcję podobną do tego typu. Jak wiadomo, fold jest rodzajem operacji, która przekształca niektóre rekurencyjne typy danych w jedną skończoną wartość. Na przykład możemy złożyć listę liczb całkowitych w jedną wartość, która jest sumą wszystkich elementów na liście:Możliwe jest uogólnienie takiej operacji na dowolnym rekurencyjnym typie danych.
Poniżej znajduje się podpis
foldr
funkcji:Zauważ, że użyłem nawiasów klamrowych do oddzielenia dwóch pierwszych argumentów od ostatniego. To nie jest prawdziwa
foldr
funkcja, ale jest z nią izomorficzna (to znaczy, możesz łatwo uzyskać jedną od drugiej i odwrotnie). Częściowo zastosowanyfoldr
będzie miał następujący podpis:Widzimy, że jest to funkcja, która pobiera listę liczb całkowitych i zwraca jedną liczbę całkowitą. Zdefiniujmy taką funkcję w kategoriach naszego
IntList
typu.Widzimy, że ta funkcja składa się z dwóch części: pierwsza część określa zachowanie tej funkcji po
Nil
częściIntList
, a druga część określa zachowanie funkcji poCons
części.Załóżmy teraz, że programujemy nie w języku Haskell, ale w jakimś języku, który pozwala na użycie typów algebraicznych bezpośrednio w podpisach typów (cóż, technicznie Haskell pozwala na użycie typów algebraicznych przez krotki i
Either a b
typy danych, ale doprowadzi to do niepotrzebnej gadatliwości). Rozważ funkcję:Można zauważyć, że
reductor
jest to funkcja typuF1 Int -> Int
, podobnie jak w definicji F-algebry! Rzeczywiście, para(Int, reductor)
jest algebrą F1.Ponieważ
IntList
jest to początkowa algebra F1, dla każdego typuT
i dla każdej funkcjir :: F1 T -> T
istnieje funkcja, zwana katamorfizmem, dlar
której konwertujeIntList
sięT
i taka funkcja jest unikalna. Rzeczywiście, w naszym przykładzie catamorphism zareductor
tosumFold
. Uwaga, jakreductor
isumFold
są podobne: mają prawie taką samą strukturę! Wreductor
definicjis
użycie parametru (którego typ odpowiadaT
) odpowiada wykorzystaniu wyniku obliczeniasumFold xs
wsumFold
definicji.Żeby było jaśniej i pomóc zobaczyć wzór, oto kolejny przykład, a my znów zaczniemy od wynikowej funkcji składania. Rozważ
append
funkcję, która dołącza swój pierwszy argument do drugiego:Tak to wygląda na naszych
IntList
:Ponownie spróbujmy napisać reduktor:
appendFold
to katamorfizm, wappendReductor
który przemieniaIntList
sięIntList
.Zasadniczo algebry F pozwalają nam definiować „fałdy” rekurencyjnych struktur danych, to znaczy operacje, które redukują nasze struktury do pewnej wartości.
F-carbongebras
Węglowodory F to tak zwane „dualne” określenie dla algebr F. Pozwalają nam zdefiniować
unfolds
rekurencyjne typy danych, czyli sposób konstruowania struktur rekurencyjnych z pewnej wartości.Załóżmy, że masz następujący typ:
To jest nieskończony strumień liczb całkowitych. Jego jedyny konstruktor ma następujący typ:
Lub pod względem zestawów
Haskell pozwala na dopasowanie wzorca do konstruktorów danych, dzięki czemu można zdefiniować następujące funkcje działające na
IntStream
s:Możesz oczywiście łączyć te funkcje w jedną funkcję typu
IntStream -> Int × IntStream
:Zauważ, że wynik funkcji pokrywa się z algebraiczną reprezentacją naszego
IntStream
typu. Podobnie można zrobić w przypadku innych typów danych rekurencyjnych. Być może już zauważyłeś wzór. Mam na myśli rodzinę funkcji typugdzie
T
jest jakiś typ. Od teraz będziemy definiowaćTeraz F-węgielgebra jest parą
(T, g)
, w którejT
jest typem ig
jest funkcją typug :: T -> F T
. Na przykład(IntStream, head&tail)
jest węgiel F1. Ponownie, podobnie jak w F-algebrach,g
iT
może być dowolne, na przykład,(String, h :: String -> Int x String)
jest także węglową F1 przez jakiś czas.Wśród wszystkich F-węgli F są takie tak zwane F-węgiel F terminali , które są dualne do początkowych F-algeb. Na przykład
IntStream
jest terminalem F-carbongebra. Oznacza to, że dla każdego typuT
i dla każdej funkcjip :: T -> F1 T
istnieje funkcja zwana anamorfizmem , która przekształcaT
sięIntStream
i taka funkcja jest unikalna.Rozważ następującą funkcję, która generuje strumień kolejnych liczb całkowitych, zaczynając od podanej:
Teraz sprawdźmy funkcję
natsBuilder :: Int -> F1 Int
, to znaczynatsBuilder :: Int -> Int × Int
:Ponownie widzimy pewne podobieństwo między
nats
inatsBuilder
. Jest bardzo podobny do połączenia, które zaobserwowaliśmy wcześniej z reduktorami i fałdami.nats
jest anamorfizmem dlanatsBuilder
.Kolejny przykład: funkcja, która przyjmuje wartość i funkcję i zwraca strumień kolejnych zastosowań funkcji do wartości:
Jego funkcja konstruktora jest następująca:
Potem
iterate
jest anamorfizmiterateBuilder
.Wniosek
Krótko mówiąc, algebry F pozwalają definiować fałdy, to znaczy operacje, które redukują strukturę rekurencyjną do jednej wartości, a algebry F pozwalają robić coś przeciwnego: konstruować [potencjalnie] nieskończoną strukturę z jednej wartości.
W rzeczywistości w Haskell F-algebry i F-carbongebras pokrywają się. Jest to bardzo przyjemna właściwość, która jest konsekwencją obecności „dolnej” wartości w każdym typie. Tak więc w Haskell można tworzyć i rozkładać dla każdego typu rekurencyjnego. Jednak model teoretyczny stojący za tym jest bardziej złożony niż ten, który przedstawiłem powyżej, więc celowo tego uniknąłem.
Mam nadzieję że to pomoże.
źródło
appendReductor
wygląda trochę dziwnie i tak naprawdę nie pomogło mi dostrzec tam wzoru ... :) Czy możesz dokładnie sprawdzić, czy jest poprawny? .. Jak ogólnie powinny wyglądać typy reduktorów? W definicjir
tamF1
określa IntList, czy jest to arbitralne F?Przegląd artykułu z samouczka Samouczek dotyczący (ko) algeb i indukcji (co) powinien dać ci wgląd w koalgebrę w informatyce.
Oto cytat z tego, aby Cię przekonać,
Preludium na temat teorii kategorii. Teorią kategorii powinna być nazwa teorii funktorów. Ponieważ kategorie są tym, co należy zdefiniować, aby zdefiniować funktory. (Ponadto funktory są tym, co należy zdefiniować, aby zdefiniować naturalne przekształcenia).
Co to jest funktor? Jest to transformacja z jednego zestawu do drugiego, który zachowuje ich strukturę. (Aby uzyskać więcej szczegółów, w sieci jest wiele dobrych opisów).
Co to jest algebra F. To algebra funktora. To tylko badanie uniwersalnej właściwości funktora.
Jak można to powiązać z informatyką? Program może być postrzegany jako uporządkowany zestaw informacji. Wykonanie programu odpowiada modyfikacji tego uporządkowanego zestawu informacji. Brzmi dobrze, że wykonanie powinno zachować strukturę programu. Następnie wykonanie można uznać za zastosowanie funktora w stosunku do tego zestawu informacji. (Ten, który definiuje program).
Dlaczego F-co-algebra? Programy są w istocie dualne, ponieważ są opisywane przez informacje i działają na ich podstawie. Wtedy głównie informacje, które składają się na program i powodują ich zmianę, można wyświetlić na dwa sposoby.
Na tym etapie chciałbym powiedzieć,
W trakcie trwania programu dane i państwo współistnieją i się uzupełniają. Są podwójne.
źródło
Zacznę od rzeczy, które są oczywiście związane z programowaniem, a następnie dodam matematykę, aby zachować ją tak konkretną i praktyczną, jak to tylko możliwe.
Przytoczmy kilku informatyków o koindukcji…
http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html
http://adam.chlipala.net/cpdt/html/Coinductive.html
http://www.alexandrasilva.org/#/talks.html
Powiązanie kontekstu matematycznego z otoczeniem ze zwykłymi zadaniami programistycznymi
Co to jest „algebra”?
Struktury algebraiczne ogólnie wyglądają następująco:
Powinno to brzmieć jak obiekty z 1. właściwościami i 2. metodami. Lub jeszcze lepiej, powinno to brzmieć jak podpisy tekstowe.
Standardowe przykłady matematyczne obejmują monoid ⊃ grupę ⊃ przestrzeń wektorową ⊃ „algebrę”. Monoidy są jak automaty: sekwencje czasowników (np
f.g.h.h.nothing.f.g.f
.).git
Dziennika, który zawsze dodaje historii i nigdy nie usuwa to byłoby monoid ale nie grupa. Jeśli dodasz odwrotność (np. Liczby ujemne, ułamki, pierwiastki, usunięcie nagromadzonej historii, nie rozbicie zepsutego lustra), otrzymasz grupę.Grupy zawierają elementy, które można dodawać lub odejmować razem. Na przykład
Duration
można dodać razem. (AleDate
s nie może.) Czasy trwają w przestrzeni wektorowej (nie tylko w grupie), ponieważ można je również skalować według liczb zewnętrznych. (Podpis typuscaling :: (Number,Duration) → Duration
.)Algebry - przestrzenie wektorowe mogą zrobić jeszcze jedną rzecz: jest kilka
m :: (T,T) → T
. Nazwij to „mnożeniem” lub nie, ponieważ kiedy wyjdzieszIntegers
, mniej oczywiste powinno być „mnożenie” (lub „potęgowanie” ).(Jest to dlaczego ludzie patrzą na () Właściwości uniwersalnych kategorii-teoretyczna: im powiedzieć, co mnożenie powinno robić lub być jak :
)
Algebras → Coalgebras
Kombinacja jest łatwiejsza do zdefiniowania w sposób, który wydaje się nieobowiązkowy, niż multiplikacja, ponieważ aby wyjść
T → (T,T)
, możesz po prostu powtórzyć ten sam element. („mapa diagonalna” - podobnie jak diagonalne macierze / operatory w teorii spektralnej)Rzeczownik jest zwykle śladem (sumą przekątnych wpisów), chociaż znowu ważne jest to, co robi Twój rzecz ;
trace
jest po prostu dobrą odpowiedzią na macierze.Powodem, dla którego warto spojrzeć na podwójną przestrzeń , jest to, że łatwiej jest w niej myśleć. Na przykład czasem łatwiej jest pomyśleć o normalnym wektorze niż o płaszczyźnie, do której jest normalny, ale można kontrolować płaszczyzny (w tym hiperpłaszczyzny) za pomocą wektorów (a teraz mówię o znanym wektorze geometrycznym, jak w przypadku promienia świetlnego) .
Oswajanie (nie) ustrukturyzowanych danych
Matematycy mogą modelować coś zabawnego jak TQFT , podczas gdy programiści muszą się zmagać
+ :: (Date,Duration) → Date
),Paris
≠(+48.8567,+2.3508)
! To kształt, nie punkt.),Informatycy, mówiąc o węgielnicach, zwykle mają na myśli ustalone operacje, takie jak produkt kartezjański. Wierzę, że to właśnie ludzie mają na myśli, mówiąc: „Algebry są węgielnicami w Haskell”. Ale w takim stopniu, w jakim programiści muszą modelować złożone typy danych, takie jak
Place
,Date/Time
iCustomer
- i sprawić, aby modele te wyglądały tak bardzo jak świat rzeczywisty (lub przynajmniej widok rzeczywistego świata użytkownika końcowego) - uważam, że dualistyczne, może być użyteczne poza światem zestalonym.źródło