Существует ли нетривиальный тип, равный его собственной производной?

Статья под названием «Производный регулярного типа - это тип контекста с одним отверстием» показывает, что «молния» типа - его контексты с одним отверстием - следуют правилам дифференцирования в алгебре типов.

У нас есть:

\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}$

Мы можем использовать эту модель, чтобы получить, что производная единицы является недействительной, что производная списка является произведением двух списков (суффикс префикса и т. Д.) И так далее.

Естественный вопрос: «какой тип является его собственной производной?» Конечно, у нас уже есть $\partial_x 0 \mapsto 0$ , что говорит нам о том, что void (необитаемый тип) является его собственной производной, но это не очень интересно. Это аналог того факта, что в обычном бесконечно малом исчислении производная нуля равна нулю.

Существуют ли другие решения уравнения $\partial_x T \mapsto T$ ? В частности, существует аналог $\partial_x e^x = e^x$ в алгебре типа? Почему или почему нет?

type-theory algebra Мэтью Пизиак
источник

Есть в теории комбинаторных видов, и там это соответствует видам (конечных) множеств, но это не соответствует алгебраическому типу данных.

Дерек Элкинс покинул SE

Что вы подразумеваете под "равным"? В вашем мире

равны? Как насчет

(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})$

Андрей Бауэр

@AndrejBauer Первый да, второй нет.

равно итерированному произведению

в моем уме. Тем не менее, у меня нет строгой модели равенства типов в моей голове, и если у вас есть модель, на которую вы можете указать мне, я был бы рад ее прочитать.

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}$

Мэтью Пизиак

@DerekElkins, как это происходит, другая статья МакБрайда под названием « Клоуны слева от меня», «Джокеры справа» указывают на то, что «Для конечных структур [итерация оператора на молнии] приводит к формулировке степенных рядов типов данных» непосредственно, находя все элементы слева направо ... Таким образом, существует значительная связь с понятием комбинаторных видов ». Поэтому я не удивлюсь, если комбинаторные виды также сыграют какую-то интересную роль в контексте этого вопроса.

Мэтью Пизиак

@MatthewPiziak Они определенно делают. Брент Йорги говорил об этом совсем немного . Смотрите также его тезис .

Дерек Элкинс покинул SE

Ответы:

Рассмотрим конечные мультимножества . Его элементы определяются как $\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$ элементов, но мы не мудрее о том, где. (Это непохоже на списки, где при выборе позиции для отверстия один список разрезается на два раздела, а второй производный разрез выбирает один из этих разделов и разрезает его дальше, как «точка» и «отметка» в редакторе, но я отступаю. ) Контекст с одним отверстием в $n-1$ Таким образом, представляет собой $\mathbf{Bag}\:X$ , и каждый $\mathbf{Bag}\:X$ может возникнуть как таковой. Думая пространственно, производная от $\mathbf{Bag}\:X$ должен быть собой. $\mathbf{Bag}\:X$

Сейчас,

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$

выбор размера кортежа с набором из элементов вплоть до группы перестановок порядка , давая нам в точности расширение степенных рядов . $n$ $n$ $n!$ $e^x$

Наивно, мы можем характеризовать типы контейнеров набором форм и зависящим от формы семейством положений : $S$ $P$ так, чтобы контейнер задавался выбором формы и карты от позиций до элементов. С сумками и тому подобным есть дополнительный поворот.

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

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

«Форма» сумки - это некоторое ; «позиции» - это , конечный набор размера , но отображение позиций на элементы должно быть инвариантным относительно перестановок из . Не должно быть доступа к сумке, которая «обнаруживает» расположение ее элементов. $n\in\mathbb{N}$ $\{1,\ldots,n\}$ $n$ $\mathbf{S}_n$

Контейнерный консорциум East Midlands писал о таких структурах в Построении Полиморфных Программ с Факторными Типами , для Математики Построения Программ 2004. Фактор-контейнеры расширяют наш обычный анализ структур по «формам» и «позициям», позволяя группе автоморфизмов воздействовать на позиции , что позволяет нам рассматривать такие структуры , как неупорядоченный пар , с производной . Неупорядоченный -кратного задается и его производная (когда - неупорядоченное $X^2/2$ $X$ $n$ $X^n/n!$ $n>0$ $n-1$ кортеж). Сумки принимают сумму этих. Мы можем играть в подобные игры с циклическими кортежами, , где выбор позиции для отверстия приводит к вращению на одну точку, в результате чего , кортеж на один меньше, без перестановок. $n$ $X^n/n$ $X^{n-1}$

«Типовое деление» вообще трудно понять, но отношение по группам перестановок (как у комбинаторных видов) имеет смысл, и с ним интересно играть. (Упражнение: сформулировать структурный принцип индукции для неупорядоченных пар чисел, , и использовать его для выполнения сложения и умножения так , что они коммутативный по построению.) $\mathbb{N}^2/2$

Характеристика контейнеров по формам и позициям не ограничивает конечность. Комбинаторные виды, как правило, организованы по размеру , а не по форме, что составляет сбор терминов и вычисление коэффициента для каждого показателя степени. Фактор-контейнеры-с-конечными позициями-множествами и комбинаторные виды - это в основном разные спины на одном и том же веществе.

pigworker
источник

Оригинальный автор появляется! Спасибо, что заглянули, чтобы показать нам этот прекрасный результат.

Мэтью Пизиак,

Как насчет бесконечной суммы Производная

\underset{я, J \in N}{Σ} {Икс}^{я} ?

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

что по оригиналу по ассоциативности и коммутативности сумм равно оригиналу.

\underset{я, J \in N}{Σ} \underset{я + 1}{\underset{⏟}{{Икс}^{я} + \dots + {Икс}^{я}}}

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

Кроме того , бесконечная сумма равна ), так что мы могли бы попытаться вычислить производную , используя списки. $\sum_{j \in \mathbb{N}} \mathsf{List}(X)$

Андрей Бауэр
источник

Производная списка - это пара списков (суффикс префикса и времен). По правилу сумм производная списка списков представляет собой список пар списков. Является ли список пар списков изоморфным списку списков?

Мэтью Пизиак

@ MatthewPiziak Возможно, проще представить первую формулировку как

. Взяв производную, получаем

(с очевидным значением для

). Теперь нам нужно только

. Для меня это выглядит немного похоже (очень неформально)

за исключением того, что коэффициенты степенного ряда выбираются

\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}$

Чи

@MatthewPiziak К сожалению, я написал

вместо

, но я думаю, ясно , что я имел в виду.

n

$n$

i

$i$

Чи