程序固定点：`let` 中的递归调用和义务假设

Question

假设我有以下 Program Fixpoint:

From Coq Require Import List Program.
Import ListNotations.

Program Fixpoint f l {measure (length l)}: list nat :=
let f_rec := (f (tl l) ) in
match hd_error l with
| Some n => n :: f_rec
| None => []
end.

（这个例子基本上 returns l 以一种非常愚蠢的方式，为了有一个简单的例子）。

在这里，我对 f（存储在 f_rec 中）进行了递归调用，仅当 l 包含一个元素时才使用它，这确保了当我使用 f_rec, length (tl l)确实小于length l.

但是，当我要解决义务时

Next Obligation.

我没有我需要的假设hd_error l = Some n。

（不知为何，我的印象是理解为"compute f (tl l) at the let in place"，而不是"delay the computation until it is actually used"）。

为了说明区别，如果我 "inline" let ... in 语句：

Program Fixpoint f l {measure (length l)}: list nat :=
match hd_error l with
| Some n => n ::  (f (tl l) )
| None => []
end.

Next Obligation.
destruct l.

这里我的环境里有Heq_anonymous : Some n = hd_error []

我的问题如下：是否可以得到我需要的假设，即由 match ... with 语句生成的假设？

N.B.: 移动 let 是一个解决方案，但我很想知道不这样做是否可行。例如，它可能在 f_rec 用于各种上下文的情况下很有用，以避免重复 f (tl l).

Answer 1

一个技巧是明确询问你需要的假设（我最近在 by Joachim Breitner 中看到）：

let f_rec := fun pf : length (tl l) < length l => f (tl l) in

这样您就可以仅在需要时使用 f_rec。

Program Fixpoint f l {measure (length l)}: list nat :=
  let f_rec := fun pf : length (tl l) < length l => f (tl l) in
  match hd_error l with
  | Some n => n :: f_rec _
  | None => []
  end.
Next Obligation. destruct l; [discriminate | auto]. Qed.

程序固定点：`let` 中的递归调用和义务假设

Program Fixpoint: recursive call in `let` and hypothesis of the obligation

coq

totality