Idris

Question

我想编写一个函数，该函数接受两个自然参数和 returns 可能证明它们相等。

我正在尝试

equal : (a: Nat) -> (b: Nat) -> Maybe ((a == b) = True)
equal a b = case (a == b) of
    True => Just Refl
    False => Nothing

但我收到以下错误

When checking argument x to constructor Prelude.Maybe.Just:
        Type mismatch between
                True = True (Type of Refl)
        and
                Prelude.Nat.Nat implementation of Prelude.Interfaces.Eq, method == a
                                                                                   b =
                True (Expected type)

        Specifically:
                Type mismatch between
                        True
                and
                        Prelude.Nat.Nat implementation of Prelude.Interfaces.Eq, method == a
                                                                                           b

执行此操作的正确方法是什么？

此外，作为奖励问题，如果我这样做

equal : (a: Nat) -> (b: Nat) -> Maybe ((a == b) = True)
equal a b = case (a == b) of
    True => proof search
    False => Nothing

我明白了

INTERNAL ERROR: Proof done, nothing to run tactic on: Solve
pat {a_504} : Prelude.Nat.Nat. pat {b_505} : Prelude.Nat.Nat. Prelude.Maybe.Nothing (= Prelude.Bool.Bool Prelude.Bool.Bool (Prelude.Interfaces.Prelude.Nat.Nat implementation of Prelude.Interfaces.Eq, method == {a_504} {b_505}) Prelude.Bool.True)
This is probably a bug, or a missing error message.
Please consider reporting at https://github.com/idris-lang/Idris-dev/issues

这是一个已知问题还是我应该报告它？

Answer 1

让我们看一下Eq接口对Nat的实现：

Eq Nat where
  Z == Z         = True
  (S l) == (S r) = l == r
  _ == _         = False

您只需按照 (==) 函数的结构即可解决问题，如下所示：

total
equal : (a: Nat) -> (b: Nat) -> Maybe ((a == b) = True)
equal Z Z = Just Refl
equal (S l) (S r) = equal l r
equal _ _ = Nothing

Answer 2

您可以使用 with 而不是 case（依赖模式匹配）来实现：

equal : (a: Nat) -> (b: Nat) -> Maybe ((a == b) = True)
equal a b with (a == b)
  | True = Just Refl
  | False = Nothing

请注意，正如 Anton 指出的那样，这只是布尔测试结果的见证，比适当的相等更弱。它可能有助于推进关于 if a==b then ... 的证明，但它不允许您用 a 代替 b。

Idris - 证明两个数相等

Idris - proving equality of two numbers

theorem-proving