我可以从枚举表达式中提取边界证明吗？

Question

考虑这个简单的程序：

module Study

g : Nat -> Nat -> Nat
g x y = x - y

f : Nat -> List Nat
f x = map (g x) [1, 2 .. x]

它给出了一个明显的错误：

  |
4 | g x y = x - y
  |           ^
When checking right hand side of g with expected type
        Nat

When checking argument smaller to function Prelude.Nat.-:
        Can't find a value of type 
                LTE y x

— 说我应该提供一些证据证明这个减法是安全的。

当然，在给定的上下文中，g 总是被安全地调用。这是从枚举的行为方式得出的。我如何提取该事实的证明，以便我可以将其提供给 g?

的调用

我知道我可以使用isLTE来获得证明：

g : Nat -> Nat -> Nat
g x y = case y `isLTE` x of
             (Yes prf)   => x - y
             (No contra) => ?s_2

这实际上是我所知道的唯一方法，在我看来，在我们这里的情况下，x ≥ y 通过构造，应该有一种方法可以避免多余的 case 语句。有吗？

Answer 1

对于 map (\y = x - y) [1, 2 .. x] [1, 2 .. x] 的每个元素都需要证明 \y => LTE y x。为此有 Data.List.Quantifiers.All：All (\y => LTE y x) [1, 2 .. x].

但是构建和应用这个证明并不是那么简单。您可以构建关于范围函数 lteRange : (x : Nat) -> All (\y => LTE y x) (natRange x) 的证明，或者定义一个 returns 范围及其证明 lteRange : (x : Nat) -> (xs : List Nat ** All (\y => LTE y x) xs) 的函数。为简单起见，我将展示第二种类型的示例。

import Data.List.Quantifiers

(++) : All p xs -> All p ys -> All p (xs ++ ys)
(++) []        ys = ys
(++) (x :: xs) ys = x :: (xs ++ ys)

lteRange : (x : Nat) -> (xs : List Nat ** All (\y => LTE y x) xs)
lteRange Z = ([] ** [])
lteRange (S k) = let (xs ** ps) = lteRange k in
  (xs ++ [S k] ** weakenRange ps ++ [lteRefl])
  where
    weakenRange : All (\y => LTE y x) xs -> All (\y => LTE y (S x)) xs
    weakenRange []       = []
    weakenRange (y :: z) = lteSuccRight y :: weakenRange z

此外，map只适用一个论证，但(-)也需要证明。所以有了一点辅助功能……

all_map : (xs : List a) -> All p xs -> (f : (x : a) -> p x -> b) -> List b
all_map [] [] f = []
all_map (x :: xs) (p :: ps) f = f x p :: all_map xs ps f

我们可以粗略地做你想做的事，而无需在运行时间内检查 LTE:

f : Nat -> List Nat
f x = let (xs ** prfs) = lteRange x in all_map xs prfs (\y, p => x - y)

我可以从枚举表达式中提取边界证明吗？

Can I extract a proof of bounds from an enumeration expression?

proof

idris