如何证明复杂表达式与“真”之间的命题相等？

How to prove propositional equality between a complicated expression and `True`?

我有一些代码如下所示：

allLessThan : Ord t => (v1 : Vect n t) -> (v2 : Vect n t) -> Bool
allLessThan v1 v2 = all (\(x,y) => x < y) (zip v1 v2)

unravelIndexUnsafe : (order : ArrayOrder) ->
                     (shape : ArrayShape (S n)) ->
                     (position : Vect (S n) Nat) ->
                     Nat
unravelIndexUnsafe order shape position = ?someImplementation

unravelIndexSafe : (order : ArrayOrder) ->
                   (shape : ArrayShape (S n)) ->
                   (position : Vect (S n) Nat) ->
                   {auto 0 prfPositionValid : (allLessThan position shape) = True} ->
                   Nat
unravelIndexSafe order shape position = unravelIndexUnsafe order shape position

unravelIndex : (order : ArrayOrder) ->
               (shape : ArrayShape (S n)) ->
               (position : Vect (S n) Nat) ->
               Maybe Nat
unravelIndex order shape position =
  case allLessThan position shape of
    True => Just $ unravelIndexSafe order shape position
    False => Nothing

我省略了我认为与问题无关的unravelIndexUnsafe的实现。

我在 unravelIndex 的定义中遇到类型错误，说它找不到 prfPositionValid 的实现以与 unravelIndexSafe*.

一起使用

这让我感到惊讶，因为我在 allLessThan position shape 上明确区分大小写，并且只在 True 分支中调用 unravelIndexSafe。我希望 Idris 能够从这些信息中推断出命题 (allLessThan position shape) = True 成立。

有没有直接解决问题的方法？也许我可以为 prfPositionValid 隐式参数显式构造和传递一些东西？或者我应该在这里使用完全不同的方法吗？我需要用不同的方式表达 prfPositionValid 或 allLessThan 吗？我需要 rewrite 什么吗？

* 更准确地说，它找不到这个可怕的“完全扩展”版本的 prfPositionValid:

的实现 
foldl (\acc, elem => acc && Delay (case block in allLessThan (S n) Nat (MkOrd (\{arg:354}, {arg:355} => compare arg arg) (\{arg:356}, {arg:357} => == (compare arg arg) LT) (\{arg:358}, {arg:359} => == (compare arg arg) GT) (\{arg:360}, {arg:361} => not (== (compare arg arg) GT)) (\{arg:362}, {arg:363} => not (== (compare arg arg) LT)) (\{arg:364}, {arg:365} => if == (compare arg arg) GT then x else y) (\{arg:366}, {arg:367} => if == (compare arg arg) LT then x else y)) shape position elem)) True (zipWith (\{__leftTupleSection:0}, {__infixTupleSection:0} => (__leftTupleSection, __infixTupleSection)) position shape) = True

解决方案：使用可判定相等性

答案是使用“可判定相等性”，因为伊德里斯没有人类聪明。

请注意，特殊的 = 语法等同于内置运算符 (===)，后者等同于类型 Equal。 Equal 的构造函数是 Refl。为了证明 Equal a b 形式的命题，伊德里斯必须能够弄清楚 a 和 b 实际上是同一事物（称之为 c）。如果你可以用类型 Equal a b 调用 Refl c，那么你就证明了 Equal a b。相反，获取 Equal a b 实例的 only 方法是调用 Refl c.

Idris 2 无法通过区分大小写来推断命题相等性。我，一个人，知道我们试图证明 allLessThan position shape 在命题上等于 True。在 Idris 中，这意味着我们希望能够编写 Refl True。 allLessThan position shape 上的大小写拆分确实会导致 Bool，但这本身并不构成对类型 Equal (allLessThan position shape) True 的 Refl True 的调用。因此，原始代码中的大小写拆分不足以让 Idris 推断出 Equal (allLessThan position shape) True.

的证明

我们知道allLessThan position shape是一个decidable谓词，所以我们可以用decEq得到我们需要的proof/implementation。因此我们可以将 unravelIndex 写成：

unravelIndex : (order : ArrayOrder) ->
               (shape : ArrayShape (S n)) ->
               (position : Vect (S n) Nat) ->
               Maybe Nat
unravelIndex order shape position =
  case decEq (allLessThan position shape) True of
    Yes proof => Just $ unravelIndexSafe order shape position
    No contra => Nothing

Yes proof中的proof正是我们要找的Refl True，它实现了Equal (allLessThan position shape) True。因此 Idris 将能够为 prfPositionValid 自动隐式推断出一个值，因为正确类型的值在范围内可用。

您也可以写 _ 而不是 proof 和 contra，因为代码中的任何地方都没有明确使用证明，所以它们不需要名称。

重构

请注意，此 allLessThan position shape 有点特别。特别是，陈述 属性 的条件需要程序员记住特定的表达式。但是我们想写一个整洁的 API，程序员可以在其中调用一个函数 isPositionValidForShape 来检查有效性，并使用类型 IndexValidForShape 来表示“有效”状态。

allLessThan : Ord t => (v1 : Vect n t) -> (v2 : Vect n t) -> Bool
allLessThan v1 v2 = all (\(x,y) => x < y) (zip v1 v2)

IndexValidForShape : (shape : ArrayShape ndim) ->
                     (position : ArrayIndex ndim) ->
                     Type
IndexValidForShape shape position =
  let isValid = allLessThan position shape
  in Equal isValid True

isIndexValidForShape : (shape : ArrayShape (S n)) ->
                       (position : ArrayIndex (S n)) ->
                       Dec (IndexValidForShape shape position)
isIndexValidForShape shape position =
  decEq (allLessThan position shape) True

unravelIndexUnsafe : (order : ArrayOrder) ->
                     (shape : ArrayShape (S n)) ->
                     (position : ArrayIndex (S n)) ->
                     Nat
unravelIndexUnsafe order shape position =
  sum $ zipWith (*) (strides order shape) position

unravelIndexSafe : (order : ArrayOrder) ->
                   (shape : ArrayShape (S n)) ->
                   (position : ArrayIndex (S n)) ->
                   {auto 0 prfIndexValid : IndexValidForShape shape position} ->
                   Nat
unravelIndexSafe order shape position =
  unravelIndexUnsafe order shape position

unravelIndex : (order : ArrayOrder) ->
               (shape : ArrayShape (S n)) ->
               (position : ArrayIndex (S n)) ->
               Maybe Nat
unravelIndex order shape position =
  case isIndexValidForShape shape position of
    Yes _ => Just $ unravelIndexSafe order shape position
    No _ => Nothing

现在，最终用户不必知道或关心 IndexValidForShape 究竟意味着什么，或者您需要使用 allLessThan 来检查它。

事实上，我们现在可以改变索引“有效”的含义，主要是在不影响下游代码用户的情况下；也许我想进行额外的检查，只有在发现逻辑错误后我才会了解这些检查。

或者，应该可以将 IndexValidForShape 重新设计为更“结构化”，其中您可以归纳定义表示所需 属性 的数据类型。例如参考Data.Vect.Elem及其在Type-Driven Development第9章的描述。

词汇表

  • 可判定：“如果您总是可以说 属性 是否适用于某些特定值，则 属性 是可判定的”（引自类型驱动开发，第 245 页）。
  • Dec：表示可判定属性有效性的类型。它的构造函数是：
    • Yes : property -> Dec property - property 成立。
    • No : (property -> Void) -> Dec property - property 是矛盾的。
  • DecEq：数据类型的接口，其相等性可以确定为可判定的属性。
  • decEq：DecEq 的方法，用于确定两个事物是否可判定地相等。它的类型是 DecEq t => (x1 : t) -> (x2 : t) -> Dec (Equal x1 x2).

参考资料和进一步阅读