如何在不增加索引的情况下增加 `Fin n` 的值？

Question

尝试在 Idris 上实现 mod : Nat -> (m : Nat) -> Fin m 函数时，我注意到明显的算法不起作用，因为在循环和增加结果时，Idris 不会相信它仍在范围内。此片段解释了问题：

-- (M : Nat) is the modulus, doesn't change
-- (r : Fin M) is the result, increases as you recurse
-- (n : Nat) is the dividend, the recursion stops when it is 0
-- (m : Nat) is the modulus index, when it is Zero, the result loops around
modAux : (M : Nat) -> (r : Fin M) -> (n : Nat) -> (m : Nat) -> Nat

-- When `n` is Zero, we're done, so, return result (works!)
modAux M r Z m = r

-- When `n > 0` but `m` iz zero, the result must loop around
-- Problem: `Z` is not a valid `Fin M`!
modAux M r (S n) Z = modAux M Z n M

-- when `n > 0` and `m > 0`, decrease both and increase the result
-- Problem: `(S r)` is not a valid `Fin M`!
modAux M r (S n) (S m) = modAux M (S r) n m

为了实现modAux，我们似乎需要一个循环的suc : Fin n -> Fin n函数。我也很难实现它。在查看 mod 的 Agda 标准库实现时，我注意到它首先证明 mod-lemma : (acc d n : ℕ) → let s = acc + n in mod-helper acc s d n ≤ s，然后使用 Fin.fromℕ≤″ 实现 mod。那看起来很重。有没有其他方法可以在不增加索引的情况下增加 Fin n 值？

Answer 1

这是一个解决方案：

open import Function
open import Data.Nat
open import Data.Fin renaming (zero to fzero; suc to fsuc) using (Fin)

suc-around : ∀ {n} -> Fin n -> Fin n
suc-around {0}     ()
suc-around {suc _} i  = go id i where
  go : ∀ {n m} -> (Fin n -> Fin (suc m)) -> Fin n -> Fin (suc m)
  go {1}           k  fzero   = fzero
  go {suc (suc _)} k  fzero   = k (fsuc fzero)
  go               k (fsuc i) = go (k ∘ fsuc) i

这个想法是你需要在处理Fin n的最后决定是returnFin.suc i还是Fin.zero。 IE。当您进行递归调用时，您不知道计算是否会导致额外的 Fin.suc 或 Fin.zero 将被 returned。只有在您知道 Fin 类型的参数实际上是 Fin.zero 的基本情况下才能做出此选择。这就是这两行的作用：

  go {1}           k  fzero   = fzero
  go {suc (suc _)} k  fzero   = k (fsuc fzero)

如果没有空间容纳另一个 Fin.suc（即参数实际上具有 Fin 1 类型），则只需 return Fin.zero。但是，如果可以在不更改类型的情况下应用另一个 Fin.suc，那么请执行此操作并应用由 Fin.suc 组成的延续，该延续目前在执行递归调用时已收集：

  go               k (fsuc i) = go (k ∘ fsuc) i

所以主要思想是你需要在基本情况下选择要 return 的内容，在递归情况下你只需要确保你不会丢失多少 [=16] 的信息=]s 已被处理。

关于mod本身我喜欢this implementation by András Kovács。

Answer 2

Data.Fin.strengthen 可以胜任繁重的工作。

-- Data.Fin.strengthen : Fin (S n) -> Either (Fin (S n)) (Fin n)
-- conceptually
-- strengthen Data.Fin.last = Left last
-- strengthen n = Right n

就我个人而言，我不喜欢这个函数，因为它的输出是"too big"；它通常不会使用它说可以 return 的所有 Left 值，但它在标准库中并且可以工作。

rotateUp : Fin n -> Fin n
rotateUp {n = Z} _ impossible
rotateUp {n = S k} f = either (const FZ) FS $ strengthen f

不推荐直接写modAux。我宁愿用这个函数来表达mod，它更通用：

toChurchNat : Nat -> (a -> a) -> (a -> a)
toChurchNat Z _ x = x
toChurchNat (S n) f x = toChurchNat n f (f x)

将 Nat 转换为它的 Church 表示（一个函数重复任何内函数多次）。因此：

mod : Nat -> (divisor : Nat) -> {auto prf : IsSucc divisor} -> Fin divisor
mod dividend (S divisor') = toChurchNat dividend rotateUp FZ

如何在不增加索引的情况下增加 `Fin n` 的值？

How to increase the value of a `Fin n` without increasing its index?

agda

idris