В конце раздела "5. Full OTT" В отношении теории типов наблюдений авторы показывают, как определять индексированные типы данных с коэрцибел-под-конструкторами в OTT, Идея состоит в том, чтобы превратить индексированные типы данных в параметры следующим образом:
data IFin : ℕ -> Set where
zero : ∀ {n} -> IFin (suc n)
suc : ∀ {n} -> IFin n -> IFin (suc n)
data PFin (m : ℕ) : Set where
zero : ∀ {n} -> suc n ≡ m -> PFin m
suc : ∀ {n} -> suc n ≡ m -> PFin n -> PFin m
Конор также упоминает этот метод в нижней части теории наблюдательного типа (доставка):
Исправить, конечно же, сделать то, что сделали люди GADT, и определить индуктивных семейств явно до пропозиционального равенства. И затем конечно, вы можете их транспортировать, с помощью транзитивности.
Однако проверка типа в Haskell знает о ограничениях равенства в области видимости и фактически использует их во время проверки типов. Например. мы можем написать
f :: a ~ b => a -> b
f x = x
Это не работает так в теории типов, так как недостаточно иметь доказательство a ~ b
в области возможностей, чтобы иметь возможность переписать это уравнение: это доказательство также должно быть refl
, поскольку в присутствии проверка типа ложных гипотез становится неразрешимой из-за проблем с завершением (что-то вроде this). Поэтому, когда совпадение шаблона на Fin m
в Haskell m
переписывается на suc n
в каждой ветки, но этого не может быть в теории типов, вместо этого вы получите явное доказательство suc n ~ m
. В OTT вообще невозможно сопоставить совпадение на доказательствах, поэтому вы не можете притворяться, что доказательство refl
и не требует этого. Это возможно только для доказательства coerce
или просто игнорировать его.
Это очень затрудняет запись всего, что связано с индексированными типами данных. Например. обычными тремя строками (включая сигнатуру типа) lookup
для векторов становится этот зверь:
vlookupₑ : ∀ {n m a} {α : Level a} {A : Univ α} -> ⟦ n ≅ m ⇒ fin n ⇒ vec A m ⇒ A ⟧
vlookupₑ p (fzeroₑ q) (vconsₑ r x xs) = x
vlookupₑ {n} {m} p (fsucₑ {n′} q i) (vconsₑ {m′} r x xs) =
vlookupₑ (left (suc n′) {m} {suc m′} (trans (suc n′) {n} {m} q p) r) i xs
vlookupₑ {n} {m} p (fzeroₑ {n′} q) (vnilₑ r) =
⊥-elim $ left (suc n′) {m} {0} (trans (suc n′) {n} {m} q p) r
vlookupₑ {n} {m} p (fsucₑ {n′} q i) (vnilₑ r) =
⊥-elim $ left (suc n′) {m} {0} (trans (suc n′) {n} {m} q p) r
vlookup : ∀ {n a} {α : Level a} {A : Univ α} -> Fin n -> Vec A n -> ⟦ A ⟧
vlookup {n} = vlookupₑ (refl n)
Это может быть немного упрощено, так как если два элемента типа данных, которые имеют разрешимое равенство, наблюдаются равными, то они также равны в обычном интенсиональном смысле, а натуральные числа имеют разрешимое равенство, поэтому мы можем принуждать всех уравнения к их интенсиональным аналогам и шаблону соответствуют им, но это нарушит некоторые вычислительные свойства vlookup
и в любом случае является подробным. Практически невозможно заниматься более сложными делами с индексами, решение которых невозможно решить.
Я правильно ли рассуждаю? Как должно выполняться сопоставление шаблонов в OTT? Если это действительно проблема, есть ли способы смягчить ее?