`a:〜:b`和`(a:== b):〜:true`之间是否有任何联系

Question

在命题和晋升平等之间是否有任何连接？

假设我有

prf :: x :~: y

在某些Symbol s的范围中；通过将其模式匹配为Refl，我可以将其转换为

prf' :: (x :== y) :~: True

这样：

fromProp :: (KnownSymbol x, KnownSymbol y) => x :~: y -> (x :== y) :~: True
fromProp Refl = Refl

但是另一个方向呢？如果我尝试

toProp :: (KnownSymbol x, KnownSymbol y) => (x :== y) :~: True -> x :~: y
toProp Refl = Refl

然后我得到的是

• Could not deduce: x ~ y
  from the context: 'True ~ (x :== y)

Answer 1

是的，可以在两个表示之间进行（假设:==的实现是正确的），但是它需要计算。

布尔本身中不存在您需要的信息（已将其删除至一点点）；您必须恢复它。这涉及询问原始布尔相等测试的两个参与者（这意味着您必须在运行时保持它们），并利用您对结果的了解来消除不可能的情况。重新执行您已经知道答案的计算非常乏味！

在AGDA工作，使用自然而不是字符串（因为它们更简单）：

open import Data.Nat
open import Relation.Binary.PropositionalEquality
open import Data.Bool
_==_ : ℕ -> ℕ -> Bool
zero == zero = true
suc n == suc m = n == m
_ == _ = false
==-refl : forall n -> (n == n) ≡ true
==-refl zero = refl
==-refl (suc n) = ==-refl n

fromProp : forall {n m} -> n ≡ m -> (n == m) ≡ true
fromProp {n} refl = ==-refl n
-- we have ways of making you talk
toProp : forall {n m} -> (n == m) ≡ true -> n ≡ m
toProp {zero} {zero} refl = refl
toProp {zero} {suc m} ()
toProp {suc n} {zero} ()
toProp {suc n} {suc m} p = cong suc (toProp {n}{m} p)

原则上，我认为您可以在Haskell中使用Singletons进行这项工作，但是为什么要打扰呢？不要使用布尔！