Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Thoughts on higher coinductive types

Slogan: Higher coinductive types should subsume second-countable topological spaces.

При помощи строго-положительного паттерн-матчинга для коиндуктивных типов можно определять замкнутые подтипы. Например определим тип бесконечных двоичных последовательностей:
 coinductive StreamB:
   head: StreamB -> Boolean
   tail: StreamB -> StreamB

Без проблем можно определить элемент top копаттерн-матчингом:
 top: StreamB
 head top = tt
 tail top = top

И свойство
 inductive IsTop (x : StreamB)
   is-top (head x = tt) (IsTop (tail x)) : IsTop x

Коль скоро Boolean разрешимый тип (проверка head x = tt может быть произведена), проверка x на существование IsTop x полуразрешима и IsTop определяет (вычислительно) замкнутое свойство x : StreamB.

Высшие коиндуктивные типы должны быть коиндуктивными типами, имеющими иные конструкторы Id, кроме refl, логично допустить в качестве таковых конструкторы, схлопывающие те или иные замкнутые множества. К примеру, чтобы сделать из StreamB вещественный интервал, нужно просто склеить два разных представления 1/2: 01111(1) и 10000(0). Для этого определим тип
 inductive IsOneHalf (x : StreamB)
   below (head x = ff) (IsTop (tail x)) : IsOneHalf x
   above (head x = tt) (IsBot (tail x)) : IsOneHalf x

где IsTop определено как выше, а IsBot аналогично. Теперь достаточно добавить в StreamB конструктор вида
 glue {x y} (IsOneHalf x) (IsOneHalf y) : (x = y)
и мы получим вещественный интервал RealInterval. Чтобы задать генераторы элементов RealInterval теперь нужно задавать рекурсивно не только какой эффект имеет применение к ним конструкторов, но и то, какой эффект имеет применение к ним конструктора IsOneHalf, т.е. для зависимого генератора чисел из RealInterval (например f(x) = sin(x) ** 2) должно быть указано, к какому предикату на аргументах сводится предикат IsOneHalf на значениях (и их хвостах).

В новом типе данных деструкторы head x и tail x определены однозначно только в том случае, когда не существует IsOneHalf x. Соответственно для того чтобы задать функцию f: RealInterval -> T, нужно задать функцию f*: StreamB -> T, постоянную на схлопнутых замкнутых множествах.
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments