Что такое логарифм или корневая операция в пространстве типов?

27

Недавно я читал «Две дуальности вычислений: отрицательные и дробные типы» . В статье рассматриваются типы сумм и типы товаров, в которых даны семантика для типов a - bи a/b.

В отличие от сложения и умножения, существует не одна, а две инверсии возведения в степень, логарифмы и корни. Если типы функций (a → b) являются теоретико-типовым возведением в степень, учитывая тип a → b(или b^a), что означает иметь тип logb(c)или тип a√c?

Имеет ли смысл вообще распространять логарифмы и корни на типы?

Если так, была ли какая-либо работа в этой области, и каковы некоторые хорошие указания о том, как понять последствия?

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

efrey
источник

Ответы:

40

Тип имеет логарифм по основанию из точно , когда . То есть, можно рассматривать как контейнер элементов в позициях , заданных . На самом деле, это вопрос с просьбой к тому , что мощность мы должны поднять , чтобы получить .X P C P X C X P P X CСИкспСпИксСИксппИксС

Имеет смысл работать с где - функтор, всякий раз, когда существует логарифм, что означает . Обратите внимание, что если , то у нас, конечно, есть , поэтому контейнер не говорит нам ничего интересного, кроме его элементов: контейнеры с выбором форм делают не имеют логарифмов.ф л о гLогFFFLогИкс(FИкс)FFИксLогFИксF11

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

Lог(К1)знак равно0нет позиций в пустом контейнереLогязнак равно1контейнер на одну, одну позициюLог(F×г)знак равноLогF+Lоггпара контейнеров, выбор позицийLог(Fг)знак равноLогF×Lоггконтейнер контейнеров, пара позиций

Мы также где под связывателем. То есть путь к каждому элементу в некоторых кодатах определяется индуктивно путем итерации логарифма. Например,Z = л о гLогИкс(νY,T)знак равноμZ,LогИксTZзнак равноLогИксY

logStream=logX(νY.X×Y)=μZ,1+Zзнак равноNaT

Учитывая, что производная сообщает нам тип в контекстах с одним отверстием, а логарифм сообщает нам позиции, мы должны ожидать соединение, и действительно

F11LогFF1

Там, где нет выбора формы, позиция - это то же самое, что и контекст с одним отверстием, когда элементы стираются. В более общем смысле всегда представляет выбор формы вместе с позицией элемента в этой форме.F1F

Я боюсь, что могу сказать меньше о корнях, но можно начать с аналогичного определения и следовать своему носу. Для более широкого использования логарифмов типов, проверьте «Памятные функции, политипически!» Ральфа Хинце. Надо бежать...

pigworker
источник
3
Ответ от самого Да Мана. Добро пожаловать, Конор!
Андрей Бауэр
Хм, мне интересно посмотреть, что такое корневые типы, так как для них потребуются типы с мнимым числом жителей. Если я не ошибаюсь. Я приму ваш ответ, но если у вас есть время, чтобы уточнить корни, это будет высоко ценится.
Эфри
Может ли это быть как-то связано с рядом Тейлора ln (1 + x)?
yatima2975
2
Интересно, с логарифмами и экспонентами ... что нам нужно для создания объекта Нейпира ? (например, предположительно уникальный объект, eтакой, что ∂e = e)
Рифмовая
1

Я не знаю ни одной работы, которая преследует эту линию, но несколько минут размышлений об этом привели меня к этой гипотезе: не будет ли «корень» экспоненциального типа просто кодоменом, а «логарифмом» экспоненты просто домен?

Марк Хаманн
источник
Правильно, поэтому я думаю, что ваша интуиция хороша, но ваш вывод неверен. Операция root и логарифм - это то, что вы получаете, когда вы «инвертируете» кодомен или домен соответственно, а не сами (со) домены. Вопрос в том, что мы подразумеваем под инвертированием и какую операцию двоичного типа он производит?
Эфри
ИксYYИксИксY
Извините, я не совсем понял свою терминологию. Я не хочу спрашивать, «что является корнем, каков результат применения функции логарифма». Мне интересно, что такое операция рутирования. Что такое операция нахождения логарифма. Если есть расходование, то, что является двумя типами под корневой операцией. Что такое два типа в логарифмической операции. То, что я подразумеваю под «инвертировать аргумент», - это то, что здесь не время объяснять. Я уточню свой вопрос, спасибо.
Эфри
В статье, на которую я ссылаюсь, приводится семантика для типа a - bи типа a / b. Меня не интересует результат сокращения операций логарифм и корень, а понимание их семантики как операторов двоичного типа.
Эфри