无法推断前任 Nat 的 SingI

Question

我正在尝试为有限的整数集编写一个 weaken 函数。我正在使用 singletons 包。我定义并提升了加法、减法和前置函数，并证明了一些方程式以帮助类型检查器。但是我得到的错误与这一切完全无关。

weaken :: forall n m k . (SingI n, SingI m, SingI k, (Minus m n) ~ NatJust k) => Fin n -> Fin m
weaken ZF =  gcastWith (apply Refl $ plus_minus sm sn sk) ZF
  where sn = sing :: SNat n
        sm = sing :: SNat m
        sk = sing :: SNat k
weaken (SF n) = gcastWith (apply Refl $ succ_pred sm) (SF (weaken n))
  where sn = sing :: SNat n
        sm = sing :: SNat m
        sk = sing :: SNat k

我得到的错误是 weaken (SF (weaken n)) 的递归调用，错误如下：Could not deduce (SingI n1)，其中 n1 被正确推断为n 类型的类型级前身。我可以添加一个 SingI (Pred n) 约束，但这只是将问题向下移动了一个级别（GHC 现在说它不能推断出 (SingI (Pred (Pred n))) 的等价物）。

我怎样才能让 GHC 相信 SingI (Pred n) 来自 SingI n（为什么 singletons 包还没有做到这一点）？

Answer 1

GHC.TypeLits，它最终为我们提供了类型级别的非负 Integer-s，不导出任何可以让我们进行单例运行时操作的函数。例如，给定 KnownNat a 和 KnownNat b，没有标准函数可以在运行时生成 KnownNat (a + b)。

singletons 通过不安全地实现 singleton Nat operations 解决了这个问题。

singletons 减法函数会为负结果抛出错误（并且不会像我们希望的那样截断为 0），因此我们不能将其重用于 pred 并且必须实现我们自己：

{-# language TypeApplications #-} -- plus all the usual exts

import Data.Singletons.Prelude
import Data.Singletons.TypeLits
import Unsafe.Coerce

type family Pred (n :: Nat) :: Nat where
  Pred 0 = 0
  Pred n = n :- 1

sPred :: Sing n -> Sing (Pred n)
sPred sn = case fromSing sn of
  0 -> unsafeCoerce (sing @_ @0)
  n -> case toSing @Nat (n - 1) of
    SomeSing sn -> unsafeCoerce sn

您可以使用 sPred 得到 Sing (Pred n)，然后 withSingI 或 singInstance 将其转换为 SingI (Pred n)。

但是，您可能不应该在 weaken 中使用 SingI。 SingI 的目的是在除了将它们转发给其他函数之外不将它们用于任何其他用途的上下文中自动插入单例参数。相反，只需使用 Sing，您就可以避免 sing 和类型注释噪音。根据我的经验，在 singletons 编程的大约 90% 的时间里，Sing 优于 SingI。

无法推断前任 Nat 的 SingI

Could not deduce SingI of predecessor Nat

haskell

curry-howard

dependent-type

singleton-type