¿Existe un tipo no trivial que sea igual a su propia derivada?

Un artículo llamado La derivada de un tipo regular es su tipo de contextos de un agujero muestra que la "cremallera" de un tipo, sus contextos de un agujero, siguen las reglas de diferenciación en álgebra de tipos.

Tenemos:

\begin{aligned} \partial_{x} x & \mapsto 1 \\ \partial_{x} 0 & \mapsto 0 \\ \partial_{x} 1 & \mapsto 0 \\ \partial_{x} (S + T) & \mapsto \partial_{x} S + \partial_{x} T \\ \partial_{x} (S \times T) & \mapsto \partial_{x} S \times T + S \times \partial_{x} T \end{aligned}

$\begin{align} \partial_x x &\mapsto 1 \\ \partial_x 0 &\mapsto 0 \\ \partial_x 1 &\mapsto 0 \\ \partial_x (S + T) &\mapsto \partial_x S + \partial_x T \\ \partial_x (S\times T) &\mapsto \partial_xS \times T + S \times \partial_x T \end{align}$

Podemos usar este modelo para deducir que la derivada de la unidad es nula, que la derivada de la lista es un producto de dos listas (prefijo por sufijo), y así sucesivamente.

Una pregunta natural es "¿de qué tipo es su propia derivada?" Por supuesto, ya tenemos $\partial_x 0 \mapsto 0$ , que nos dice que void (el tipo deshabitado) es su propia derivada, pero eso no es muy interesante. Es el análogo del hecho de que la derivada de cero es cero en el cálculo infinitesimal ordinario.

¿Hay otras soluciones a la ecuación $\partial_x T \mapsto T$ ? En particular, ¿hay un análogo de $\partial_x e^x = e^x$ en álgebra de tipo? ¿Por qué o por qué no?

type-theory algebra Matthew Piziak
fuente

Existe en la teoría de las especies combinatorias, y allí corresponde a las especies de conjuntos (finitos), pero eso no corresponde a un tipo de datos algebraicos.

Derek Elkins dejó SE

¿Qué quieres decir con "igual"? En su mundo, ¿son

iguales? ¿Qué tal

(S + T) \to U

$(S + T) \to U$

(S \to U) \times (T \to U)

$(S \to U) \times (T \to U)$

N

$\mathbb{N}$

L i s t (N)

$\mathsf{List}(\mathbb{N})$

Andrej Bauer,

@AndrejBauer El primero sí, el último no.

es igual al producto iterado

en mi mente. Dicho esto, no tengo un modelo riguroso de igualdad de tipos en mi mente, y si tiene un modelo al que pueda apuntar, estaré encantado de leerlo.

L i s t (N)

$\mathsf{List}(\mathbb{N})$

1 + N + N \times N + N \times N \times N + \dots = \sum_{n = 0}^{\infty} N^{n}

$1 + \mathbb{N} + \mathbb{N} \times \mathbb{N} + \mathbb{N} \times \mathbb{N} \times \mathbb{N} + \ldots = \sum_{n=0}^{\infty} \mathbb{N}^{n}$

Matthew Piziak

@DerekElkins, como sucede, otro artículo de McBride, llamado Payasos a mi izquierda, Jokers a la derecha señala que, "Para estructuras finitas, [la iteración de un operador en las cremalleras] da lugar a una formulación de series de datos de tipos de datos directamente, encontrando todos los elementos de izquierda a derecha ... Por lo tanto, existe una conexión significativa con la noción de especie combinatoria ". Por lo tanto, no me sorprendería si las especies combinatorias también tienen un papel interesante en el contexto de esta pregunta.

Matthew Piziak

@MatthewPiziak Definitivamente lo hacen. Brent Yorgey ha hablado bastante sobre esto . Ver también su tesis .

Derek Elkins dejó SE

Respuestas:

Considere los conjuntos múltiples finitos . Sus elementos están dados por cociente por permutaciones, de modo que para cualquier . ¿Cuál es el contexto de un agujero para un elemento en tal cosa? Bueno, debemos haber tenido para seleccionar una posición para el hoyo, por lo que nos queda el $\mathbf{Bag}\:X$ $\{x_1,\ldots,x_n\}$ $\{x_1,\ldots,x_n\}=\{x_{\pi 1},\ldots,x_{\pi n}\}$ $\pi\in\mathbf{S}_n$ $n>0$ elementos, pero no sabemos cuál es dónde. (Eso es diferente a las listas, donde elegir una posición para el agujero corta una lista en dos secciones, y el segundo corte derivado selecciona una de esas secciones y la corta más, como "punto" y "marca" en un editor, pero estoy divagando. ) Un contexto de un agujero en a $n-1$ es, pues, a $\mathbf{Bag}\:X$ , y cada $\mathbf{Bag}\:X$ puede surgir como tal. Pensando espacialmente, la derivada de $\mathbf{Bag}\:X$ debería ser él mismo. $\mathbf{Bag}\:X$

Ahora,

B a g X = \sum_{n \in N} X^{n} / S_{n}

$\mathbf{Bag}\:X = \sum\limits_{n\in\mathbb{N}}X^n/\mathbf{S}_n$

¡una elección del tamaño de tupla , con una tupla de elementos hasta un grupo de permutación de orden , dándonos exactamente la expansión de la serie de potencia de . $n$ $n$ $n!$ $e^x$

Ingenuamente, podemos caracterizar los tipos de contenedor mediante un conjunto de formas y una familia de posiciones dependiente de la forma : $S$ $P$ para que un contenedor esté dado por una elección de forma y un mapa de posiciones a elementos. Con bolsos y similares, hay un giro extra.

\sum_{s : S} X^{(P s)}

$\sum\limits_{s:S}X^{(P\,s)}$

La "forma" de una bolsa es algo ; las "posiciones" son , el conjunto finito de tamaño , pero el mapa de posiciones a elementos debe ser invariable bajo permutaciones de . No debería haber forma de acceder a una bolsa que "detecta" la disposición de sus elementos. $n\in\mathbb{N}$ $\{1,\ldots,n\}$ $n$ $\mathbf{S}_n$

El Consorcio de Contenedores de East Midlands escribió sobre tales estructuras en Construyendo programas polimórficos con tipos de cociente , para Matemáticas de la construcción de programas 2004. Los contenedores de cociente amplían nuestro análisis habitual de estructuras por "formas" y "posiciones" al permitir que un grupo de automorfismo actúe sobre las posiciones , lo que nos permite considerar estructuras tales como pares no ordenadas , con derivado . ¡ da una -tupla desordenada , y su derivada (cuando es un desordenado $X^2/2$ $X$ $n$ $X^n/n!$ $n>0$ $n-1$ tupla) Las bolsas toman la suma de estos. Podemos jugar juegos similares con tuplas cíclicas , , donde elegir una posición para el agujero clava la rotación en un punto, dejando , una tupla más pequeña sin permutación. $n$ $X^n/n$ $X^{n-1}$

La "división de tipos" es difícil de entender en general, pero el cociente por grupos de permutación (como en las especies combinatorias) tiene sentido, y es divertido jugar con él. (Ejercicio: formular un principio de inducción estructural para pares no ordenados de números, , y lo utilizan para implementar adición y multiplicación para que estén conmutativa por la construcción.) $\mathbb{N}^2/2$

La caracterización de "formas y posiciones" de los contenedores no impone finitud a ninguno de los dos. Las especies combinatorias tienden a organizarse por tamaño , en lugar de forma, lo que equivale a recopilar términos y calcular el coeficiente de cada exponente. Los conjuntos de recipientes de cociente con posiciones finitas y las especies combinatorias son básicamente giros diferentes en la misma sustancia.

trabajador porcino
fuente

¡Aparece el autor original! Gracias por visitarnos para mostrarnos este hermoso resultado.

Matthew Piziak

¿Qué tal la suma infinita La derivada es que es igual al original por asociatividad y conmutatividad de sumas.

\sum_{i, j \in N} X^{i} ?

$\sum_{i, j \in \mathbb{N}} X^i ?$

\sum_{i, j \in N} \underset{i + 1}{\underset{⏟}{X^{i} + \dots + X^{i}}}

$\sum_{i, j \in \mathbb{N}} \underbrace{X^i + \cdots + X^i}_{i+1}$

Además, la suma infinita es igual a ), por lo que podríamos intentar calcular la derivada usando listas. $\sum_{j \in \mathbb{N}} \mathsf{List}(X)$

Andrej Bauer
fuente

La derivada de una lista es un par de listas (prefijo multiplicado por sufijo). Por la regla de la suma, la derivada de una lista de listas es una lista de pares de listas. ¿Es una lista de pares de listas isomorfa a una lista de listas?

Matthew Piziak

\sum_{i \in N} N \times X^{i}

$\sum_{i\in \mathbb{N}} \mathbb{N}\times X^i$

\sum_{i \in N} i \times N \times X^{i}

$\sum_{i\in \mathbb{N}} i\times \mathbb{N}\times X^i$

i

$i$

N ≃ i \times N

$\mathbb{N}\simeq i\times \mathbb{N}$

e^{x} = \sum_{i} x^{i} / n!

$e^x = \sum_i x^i/n!$

+ \infty

$+\infty$

N

$\mathbb{N}$

a_{n} = (n + 1) \cdot a_{n + 1}

$a_{n} = (n+1) \cdot a_{n+1}$

n

$n$

i

$i$