Co to jest logarytm lub operacja rootowania w przestrzeni typu?

27

Niedawno czytałem Dwie dualności obliczeń: typy ujemne i ułamkowe . Artykuł rozwija typy sum i typy produktów, nadając semantykę typom a - bi a/b.

W przeciwieństwie do dodawania i mnożenia, nie ma jednego, lecz dwa odwrotności potęgowania, logarytmów i rootowania. Jeśli typy funkcji (a → b) są potęgowaniem teoretycznym, biorąc pod uwagę typ a → b(lub b^a), co to znaczy mieć typ logb(c)lub typ a√c?

Czy w ogóle sens ma rozszerzanie logarytmów i pierwiastków na typy?

Jeśli tak, to czy były jakieś prace w tym obszarze i jakie są dobre wskazówki, jak zrozumieć konsekwencje?

Próbowałem znaleźć informacje na ten temat za pomocą logiki, mając nadzieję, że korespondencja Curry-Howarda może mi pomóc, ale bezskutecznie.

efrey
źródło

Odpowiedzi:

40

Typ posiada logarytm oprzeć X w P , kiedy dokładnie C P X . Oznacza to, C mogą być postrzegane jako pojemnika X elementów pozycjach określonych przez P . Rzeczywiście, jest to kwestia z prośbą o jaką moc P musimy podnieść X uzyskanie C .CXPCPXCXPPXC

Sensowna jest praca z gdzie F jest funktorem, ilekroć istnieje logarytm, co oznacza l o glogFF . Zauważ, że jeśli FlogX(FX) , wtedy na pewno mamy FFXlogFX , więc pojemnik nie mówi nam nic ciekawego poza jego elementami: pojemniki z wyborem kształtów nie mają logarytmów.F11

Znane prawa logarytmów mają sens, gdy myślisz o zestawach pozycji

log(K1)=0no positions in empty containerlogI=1container for one, one positionlog(F×G)=logF+logGpair of containers, choice of positionslog(FG)=logF×logGcontainer of containers, pair of positions

logX(νY.T)=μZ.logXTZ=logXY

logStream=logX(νY.X×Y)=μZ.1+Z=Nat

Biorąc pod uwagę, że pochodna mówi nam o typie w kontekstach z jednym dołkiem, a logarytm mówi nam o pozycjach, powinniśmy spodziewać się związku, i rzeczywiście

F11logFF1

F1F

Obawiam się, że mam mniej do powiedzenia na temat korzeni, ale można zacząć od podobnej definicji i podążać za nosem. Aby uzyskać więcej zastosowań logarytmów typów, sprawdź „Funkcje memo, wieltypowo!” Ralfa Hinze. Muszę biec ...

świniarz
źródło
3
Odpowiedź samego Da Mana. Witaj Conor!
Andrej Bauer,
Hmm, jestem zainteresowany, aby zobaczyć, jakie są typy korzeni, ponieważ wymagałyby typów mających wyimaginowaną liczbę mieszkańców. Chyba że się mylę. Przyjmuję twoją odpowiedź, ale jeśli będziesz miał czas na opracowanie korzeni, byłoby to bardzo mile widziane.
efrey
Czy można to w jakiś sposób powiązać z serią ln (1 + x) Taylora?
yatima2975
2
Z logarytmami i wykładnikami zastanawiam się ... czego potrzebujemy, aby zbudować obiekt Napiera ? (np. rzekomo wyjątkowy obiekt etaki, że ∂e = e)
Rhymoid
1

Nie znam żadnej pracy, która podąża za tą linią, ale kilka chwil przemyślenia doprowadziło mnie do tej hipotezy: czy „pierwiastek wykładniczego typu nie byłby po prostu kodomeną i„ logarytmem wykładniczym ” tylko domena?

Marc Hamann
źródło
Racja, więc myślę, że twoja intuicja jest dobra, ale twoje wnioski są nieaktualne. Operacja rootowania i operacja logarytmiczna są tym, co dostajesz, gdy „odwracasz” odpowiednio domenę kodową lub domenę, a nie samą (współ) domenę. Pytanie brzmi: co rozumiemy przez inwersję i jaką operację binarną wywołuje?
efrey
xyyxxy
Przepraszam, nie jestem całkowicie jasny w mojej terminologii. Nie chcę pytać „co to jest rdzeń, co jest wynikiem zastosowania funkcji logarytmicznej”. Zastanawiam się, na czym polega operacja rootowania. Jaka jest operacja znalezienia logarytmu. Jeśli jest to wydatek, jakie są dwa typy operacji root. Co to są dwa typy operacji logarytmicznej. To, co rozumiem przez „odwrócenie argumentu”, jest czymś, czego nie ma tutaj czasu na wyjaśnienie. Wyjaśnię moje pytanie, dzięki.
efrey,
Artykuł, który połączyłem, przedstawia semantykę dla typu a - bi typu a / b. Nie interesuje mnie wynik zmniejszenia logarytmu operacji i rootowania, ale rozumienie ich semantyki jako operatorów typu binarnego.
efrey,