Co to jest logarytm lub operacja rootowania w przestrzeni typu?

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.

lo.logic pl.programming-languages type-theory algebra efrey
źródło

Odpowiedzi:

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

Sensowna jest praca z gdzie jest funktorem, ilekroć istnieje logarytm, co oznacza $\mathop{log}F$ $F$ . Zauważ, że jeśli $\mathop{log}\!_X(F\:X)$ , wtedy na pewno mamy $F\:X\cong \mathop{log}F\to X$ , więc pojemnik nie mówi nam nic ciekawego poza jego elementami: pojemniki z wyborem kształtów nie mają logarytmów. $F\:1\cong 1$

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

\begin{array}{rcll} l o g (K 1) & = & 0 & no positions in empty container \\ l o g I & = & 1 & container for one, one position \\ l o g (F \times G) & = & l o g F + l o g G & pair of containers, choice of positions \\ l o g (F \cdot G) & = & l o g F \times l o g G & container of containers, pair of positions \end{array}

$\begin{array}{rcl@{\qquad}l} \mathop{log} (\mathop{K}1) &=& 0 & \mbox{no positions in empty container}\\ \mathop{log} I &=& 1 & \mbox{container for one, one position}\\ \mathop{log} (F\times G) &=& \mathop{log}F+\mathop{log}G & \mbox{pair of containers, choice of positions} \\ \mathop{log} (F\cdot G) &=& \mathop{log}F\times\mathop{log}G & \mbox{container of containers, pair of positions} \end{array}$

$\mathop{log}\!_X(\nu Y. T) = \mu Z. \mathop{log}\!_X T$ $Z=\mathop{log}\!_XY$

l o g S t r e a m = l o g_{X} (ν Y . X \times Y) = μ Z . 1 + Z = N a t

$\mathop{log}\mathop{Stream} = \mathop{log}\!_X(\nu Y. X\times Y) = \mu Z. 1 + Z = \mathop{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

F 1 ≅ 1 \Rightarrow l o g F ≅ \partial F 1

$F\:1\cong 1 \;\Rightarrow\; \mathop{log}F\cong \partial F\:1$

$\partial F\:1$ $F$

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

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

Z logarytmami i wykładnikami zastanawiam się ... czego potrzebujemy, aby zbudować obiekt Napiera ? (np. rzekomo wyjątkowy obiekt etaki, że ∂e = e)

Rhymoid

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

x^{y}

$x^y$

y

$y$

x

$x$

x

$x$

y

$y$

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,