Coq 的 'fix' 关键字在精益中创建固定点的等效项是什么

Question

我正在尝试将 Coq 术语直译为精益术语，但意识到我不知道如何翻译 Coq 原语 fix，如：

Definition Fac : nat -> nat :=
    fix f (n:nat) : nat :=
        match n with
        | 0     => 1
        | S p   => S p * f p
        end.

我不是在问如何定义归纳类型的递归函数，这在精益文档中有很好的解释，而是如何定义 'recursive lets'，即主体调用自身的 lambda 抽象。我假设精益中存在等效的原语。

谢谢。

Answer 1

有关于此的讨论here。据我所知，没有很好的表示法。

最接近的方法是直接使用 nat 的递归，或者直接使用 well_founded.fix。

例如

def fact (n : ℕ) : ℕ :=
let f : ℕ → ℕ := λ n, nat.rec_on n 1 (λ n fact, (n + 1) * fact) in
f n

或

def fact' (n : ℕ) : ℕ :=
let f : ℕ → ℕ := λ n, well_founded.fix nat.lt_wf 
  (λ n fact, show ℕ, from nat.cases_on n (λ _, 1)
    (λ n fact, (n + 1) * fact n n.lt_succ_self) fact) 
  n in
f n

Coq 的 'fix' 关键字在精益中创建固定点的等效项是什么

What is the equivalent of Coq's 'fix' keyword to create fixpoints in Lean

lean