精益编程语言中的循环

Question

我开始学习 Lean 编程语言 https://leanprover.github.io

我发现有函数、结构、if/else和其他常用的编程命令。

但是，我还没有找到任何可以处理的东西 loops。有没有一种方法可以在精益中迭代或重复一段代码？类似于其他语言中的 for 或 while。如果是这样，请添加语法或示例。

提前致谢。

Answer 1

与其他函数式编程语言一样，精益中的循环主要通过递归完成。例如：

-- lean 3
def numbers : ℕ → list ℕ
| 0 := []
| (n+1) := n :: numbers n

如果你不习惯的话，这是一种观念上的转变。参见：Haskell from C: Where are the for Loops?

使事情复杂化的是，精益区分了一般递归和结构递归。上面的例子是在 ℕ 上使用结构递归，所以我们知道它总是会停止。 Non-halting 程序会导致像 lean 这样的 DTT-based 定理证明器不一致，因此必须严格控制。您可以使用 meta 关键字选择一般递归：

-- lean 3
meta def foo : ℕ → ℕ
| n := if n = 100 then 0 else foo (n + 1) + 1

在 lean 4 中，do 块语法包含一个 for 命令，可用于以更命令式的方式编写 for 循环。请注意，它们仍然表示为引擎盖下的 tail-recursive 函数，并且有一些类型类支持脱糖。（您还需要 partial 关键字而不是 meta 来在精益 4 中进行一般递归。）

-- lean 4
partial def foo (n : Nat) : Nat :=
  if n = 100 then 0 else foo (n + 1) + 1

def mySum (n : Nat) : Nat := Id.run do
  let mut acc := 0
  for i in [0:n] do
    acc := acc + i
  pure acc

精益编程语言中的循环

Loops in Lean programming language

loops

lean