通过重复除法进行有根据的递归

Question

假设我有一些自然数 d ≥ 2 和 n > 0；在这种情况下，我可以从 n 中分离出 d 并得到 n = m * d^k，其中 m 不能被 d.

整除

；所以我想我会为 Steps 创建一个数据类型，导致 m:

import Data.Nat.DivMod

data Steps: (d : Nat) -> {auto dValid: d `GTE` 2} -> (n : Nat) -> Type where
  Base: (rem: Nat) -> (rem `GT` 0) -> (rem `LT` d) -> (quot : Nat) -> Steps d {dValid} (rem + quot * d)
  Step: Steps d {dValid} n -> Steps d {dValid} (n * d)

并编写一个递归函数，为给定的一对 d 和 n:

计算 Steps

total lemma: x * y `GT` 0 -> x `GT` 0
lemma {x = Z} LTEZero impossible
lemma {x = Z} (LTESucc _) impossible
lemma {x = (S k)} prf = LTESucc LTEZero

steps : (d : Nat) -> {auto dValid: d `GTE` 2} -> (n : Nat) -> {auto nValid: n `GT` 0} -> Steps d {dValid} n
steps Z {dValid = LTEZero} _ impossible
steps Z {dValid = (LTESucc _)} _ impossible
steps (S d) {dValid} n {nValid} with (divMod n d)
  steps (S d) (q * S d) {nValid} | MkDivMod q Z _ = Step (steps (S d) {dValid} q {nValid = lemma nValid})
  steps (S d) (S rem + q * S d) | MkDivMod q (S rem) remSmall = Base (S rem) (LTESucc LTEZero) remSmall q

但是，steps 不被接受为总数，因为没有明显的理由说明递归调用是有根据的（q 和 n 之间没有结构关系）。

不过我还有一个功能

total wf : (S x) `LT` (S x) * S (S y)

用无聊的证明。

我可以在 steps 的定义中使用 wf 来向 Idris 解释 steps 是总数吗？

Answer 1

这是一种使用有根据的递归来完成您所要求的方法。不过，我敢肯定，有更好的方法。在接下来的内容中，我将使用标准 LT 函数，这使我们能够实现我们的目标，但是我们需要解决一些障碍。

不幸的是，LT是一个函数，不是类型构造函数或数据构造函数，这意味着我们不能定义 WellFounded LT 的类型类。以下代码是针对这种情况的解决方法：

total
accIndLt : {P : Nat -> Type} ->
         (step : (x : Nat) -> ((y : Nat) -> LT y x -> P y) -> P x) ->
         (z : Nat) -> Accessible LT z -> P z
accIndLt {P} step z (Access f) =
  step z $ \y, lt => accIndLt {P} step y (f y lt)

total
wfIndLt : {P : Nat -> Type} ->
        (step : (x : Nat) -> ((y : Nat) -> LT y x -> P y) -> P x) ->
        (x : Nat) -> P x
wfIndLt step x = accIndLt step x (ltAccessible x)

我们需要一些辅助引理来处理小于关系，引理可以在 this 要点（Order 模块）中找到。这是我最近开始的个人图书馆的一个子集。我确信辅助引理的证明可以最小化，但这不是我的目标。

引入Order模块后，问题就解决了（我对原来的代码稍作修改，修改或者写个wrapper来保持原来的类型都不难）：

total
steps : (n : Nat) -> {auto nValid : 0 `LT` n} -> (d : Nat) -> Steps (S (S d)) n
steps n {nValid} d = wfIndLt {P = P} step n d nValid
  where
    P : (n : Nat) -> Type
    P n = (d : Nat) -> (nV : 0 `LT` n) -> Steps (S (S d)) n

    step : (n : Nat) -> (rec : (q : Nat) -> q `LT` n -> P q) -> P n
    step n rec d nV with (divMod n (S d))
      step (S r + q * S (S d)) rec d nV | (MkDivMod q (S r) prf) =
        Base (S r) (LTESucc LTEZero) prf q
      step (Z + q * S (S d))       rec d nV | (MkDivMod q Z     _) =
        let qGt0 = multLtNonZeroArgumentsLeft nV in
        let lt = multLtSelfRight (S (S d)) qGt0 (LTESucc (LTESucc LTEZero)) in
        Step (rec q lt d qGt0)

我根据 divMod function from the contrib/Data/Nat/DivMod/IteratedSubtraction.idr 模块建模 steps。

完整代码可用 here。

警告：完整性检查器（从 Idris 0.99 开始，发布版本）不接受 steps 作为总数。它最近已修复并适用于我们的问题（我使用 Idris 0.99-git:17f0899c 对其进行了测试）。

通过重复除法进行有根据的递归

Well-founded recursion by repeated division

recursion

induction

idris

totality