CoNat: доказательство того, что 0 нейтрален слева

Question

Я экспериментирую с определением CoNatвзято из этой статьи Джеспера Кокса и Андреаса Абеля:

open import Data.Bool
open import Relation.Binary.PropositionalEquality

record CoNat : Set where
  coinductive
  field iszero : Bool
        pred : .(iszero ≡ false) -> CoNat

open CoNat public

Я определяю zero а также plus:

zero : CoNat
iszero zero = true
pred zero ()

plus : CoNat -> CoNat -> CoNat
iszero (plus m n)                                  = iszero m ∧ iszero n
pred (plus m n) _ with iszero m | inspect iszero m | iszero n | inspect iszero n
...                | false | [ p ] | _     | _     = plus (pred m p) n
...                | true  | _     | false | [ p ] = plus m (pred n p)
pred (plus _ _) () | true  | _     | true  | _

И я определяю двойное сходство:

record _≈_ (m n : CoNat) : Set where
  coinductive
  field
    iszero-≈ : iszero m ≡ iszero n
    pred-≈ : ∀ p q -> pred m p ≈ pred n q

open _≈_ public

Но я застрял с доказательством того, что plus zero n близок к n. Я предполагаю, что в доказательстве я должен иметь (по крайней мере) предложение with дляiszero n:

plus-zero-l : ∀ n -> plus zero n ≈ n
iszero-≈ (plus-zero-l _)   = refl
pred-≈ (plus-zero-l n) p q with iszero n
... | _ = ?

Но Agda жалуется на следующее сообщение об ошибке:

iszero n != w of type Bool
when checking that the type
(n : CoNat) (w : Bool) (p q : w ≡ false) →
(pred (plus zero n) _ | true | [ refl ] | w | [ refl ]) ≈ pred n _
of the generated with function is well-formed

Как я могу представить это доказательство?

Answer 1

Мне не сразу удалось доказать лемму с вашим определением plus, но вот альтернативное определение, которое позволяет пройти доказательство:

open import Data.Bool
open import Relation.Binary.PropositionalEquality

record CoNat : Set where
  coinductive
  field iszero : Bool
        pred : .(iszero ≡ false) -> CoNat

open CoNat public

zero : CoNat
zero .iszero = true
zero .pred ()

record _≈_ (m n : CoNat) : Set where
  coinductive
  field
    iszero-≈ : iszero m ≡ iszero n
    pred-≈ : ∀ p q → pred m p ≈ pred n q

open _≈_ public

plus′ : (n m : CoNat) → CoNat
plus′ n m .iszero = n .iszero ∧ m .iszero
plus′ n m .pred eq with n .iszero | m .iszero | n .pred | m .pred
plus′ n m .pred eq | false | _      | pn | pm = plus′ (pn refl) m
plus′ n m .pred eq | true  | false  | pn | pm = plus′ n (pm refl)
plus′ n m .pred () | true  | true   | pn | pm

plus′-zero-l : ∀ n → plus′ zero n ≈ n
plus′-zero-l n .iszero-≈ = refl
plus′-zero-l n .pred-≈ p q with n .iszero | n .pred
plus′-zero-l n .pred-≈ () _ | true  | pn
plus′-zero-l n .pred-≈ p q  | false | pn = plus′-zero-l (pn _)

---

FWIW, учитывая, что плюс требует таких усилий, я не вижу, чтобы это представление конатов было особенно приятным для работы. Возможно, вы захотите рассмотреть эти альтернативы:

• Два взаимно определенных типа данных, один индуктивный и один коиндуктивный, как в Нормализации оценкой в ​​Монаде задержки.
• Вариант стандартной библиотеки предыдущего подхода, в котором используетсяThunk тип данных.
• CoNat′ = ℕ ⊎ ⊤, который не совсем conat, но может служить аналогичным целям.