使用采用非零自然数的函数

Question

我正在尝试在 Idris 中定义一个函数 (congruentialMethod)，除其他外，该函数对提供给我的函数的一些参数应用模数运算。模数运算要求第二个参数为非零，因此我尝试使用 modNatNZ 并向我的函数类型签名添加证明。但是，我觉得我的尝试很笨拙。

首先，当我定义最终成为模数函数 (let m : Nat = 2147483647) 的第二个参数的值时，-我必须执行一些笨拙的大小写匹配以说服 Idris 该值更大比零。如果我不这样做，那么类型检查将永远进行。

其次，我不太明白为什么我在调用我的函数时必须提供证明(congruentialMethod)。我在函数签名中将证明指定为 auto，认为 Idris 能够推断出它。

module Random

%default total

getUnixEpoch : IO Nat
getUnixEpoch = do time <- foreign FFI_C "#(unsigned long)time(NULL)" (IO Int)
                  pure $ fromInteger $ cast time

congruentialMethod : (seed : Nat) -> (a : Nat) -> (b : Nat) -> (m : Nat) -> {auto prf : (m = Z) -> Void} -> Stream Double
congruentialMethod seed a b m {prf} =
  (cast seed) / (cast m) :: loop seed
  where
    loop : (prev : Nat) -> Stream Double
    loop prev = let n = modNatNZ (a * prev + b) m prf
                in (cast n) / (cast m) :: loop n

main : IO ()
main = do time <- getUnixEpoch
          putStrLn $ "seed: " ++ (cast time)
          let a : Nat = 16807
          let b : Nat = 0
          let m : Nat = 2147483647
          case m of
               Z => ?shouldnt_happen
               S m' => do let random_number_stream = congruentialMethod time a b (S m') {prf = SIsNotZ}
                          ?continue

我能否以某种方式避免将证明传递给我的 congruentialMethod 函数？有没有更简单的方法让 Idris 相信 let m : Nat = 2147483647 大于零 （而不是使用大小写匹配）?

编辑：此代码的另一个问题似乎是使用 Nat 执行计算非常慢。使用 Int、mod 并将函数更改为 partial 可以快速生成数字。显然被迫将函数定义为 partial 很糟糕。但也许这是 material 另一个问题....

Answer 1

Idris 很难推断 Not 证明，因为它们是函数，而 Idris 只是不尝试推断函数，因为函数非常复杂。标准库已经想到了你的情况。我们有 Prelude.Nat.IsSucc:

data IsSucc : Nat -> Type where
  ItIsSucc : IsSucc (S n)

这适用于 auto，但现有的 Nat 功能与其不兼容，因此我们使用了一些胶水。

isSuccNotZero : IsSucc n -> Not (n = Z)
isSuccNotZero {n = S _} ItIsSucc Refl impossible

就是这样：

congruentialMethod : (seed : Nat) -> (a : Nat) -> (b : Nat) ->
                     (m : Nat) -> {auto prf : IsSucc m} -> Stream Double
congruentialMethod seed a b m {prf} =
  (cast seed / cast m) :: (congruentialMethod (modNatNZ (a * seed + b) m $ isSuccNotZero prf) a b m)

使用站点现在将推断 prf。然而，对于这么大的数字，编译器仍然会阻塞，正如您在编辑中看到的那样。它最终会做对，但这需要一段时间。我没有解决方案。

使用采用非零自然数的函数

working with functions that takes non-zero natural numbers

idris