运行时的类型族约束 // 无法匹配类型 '1 <=？n0"与"真"

Question

StackOverflow！

出于我和上帝之间的原因，我目前正在努力将运行时自然语言提升到类型级别。我一直在GHC.TypeLits上采用这种方法，到目前为止效果良好。

然而，在一个例子中，我有一个1 <= n的额外约束，即我的提升自然不是任何自然的，而是至少为1。这也是来自GHC.TypeLits，我不确定是否/如何提取并公布这些信息。

这里有一个最小的非工作示例：

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE RankNTypes #-} 
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeOperators #-}
import Data.Maybe
import Data.Proxy
import GHC.TypeLits
import Numeric.Natural
data AnyNat (n :: Nat) where
AN :: AnyNat n
data AtLeast1Nat (n :: Nat) where
AL1N :: AtLeast1Nat n
promote0 :: Natural -> AnyNat n
promote0 k = case sn of
SomeNat (_ :: Proxy p) -> AN 
where
sn = (fromJust . someNatVal . toInteger) k
promote1 :: (KnownNat n, 1 <= n) => Natural -> AtLeast1Nat n
promote1 k = case sn of
SomeNat (_ :: Proxy p) -> AL1N 
where
sn = (fromJust . someNatVal . toInteger) k
main :: IO ()
main = do nat_in <- getLine
let nat = read nat_in :: Natural
let p0  = promote0 nat
let p1  = promote1 nat
putStrLn "Last statement must be an expression"

这会产生此错误(此处为完整错误，但这是相关部分(：

* Couldn't match type `1 <=? n0' with 'True
arising from a use of `promote1'
The type variable `n0' is ambiguous

老实说，这并不太令人惊讶，我(想我(确实理解为什么会发生这种情况。我们在中给出的Natural可以是它们中的任何一个，那么为什么我们能够推导出1 <= n呢？这就是为什么它适用于promote0而不是promote1。

因此，我的问题是，是否有任何方法也可以检查(并传播到类型级别(此信息，以便我可以按预期使用它，或者我在这里使用了错误的方法？

Answer 1

您使用了错误的方法。

正如在评论中所讨论的，promote0(以及类似的promote1(并没有做你所希望的事情。问题是，对于与术语sn完全无关的一些n，情况右侧的AN具有类型AnyNat n。你本可以写：

promote0 k = case 2+2 of 4 -> AN

并得到了大致相同的效果。请注意您的代码与您链接的另一个Stack Overflow答案之间的关键区别：在该答案中，case仔细检查中的类型变量n用于在case分支中键入某些内容(通过ScopedTypeVariables(。您在监票人中绑定了一个类型变量p，但不将其用于任何用途。

如果我们考虑你的实际问题，假设我们想写这样的东西：

import qualified Data.Vector.Sized as V
main = do
n <- readLn :: IO Int
let Just v  = V.fromList (replicate n 1)
v2 = v V.++ v
print $ v2

这不会进行类型检查。它在V.fromList上给出了一个关于缺少KnownNat约束的错误。问题是v已经被分配了用于某些k :: Nat的类型S.Vector k Int。但是V.fromList执行输入列表的长度(运行时值n(等于类型级别k的运行时检查。为此，必须将k转换为需要KnownNat k的运行时整数。

正如您所猜测的，一般的解决方案是构造一个SomeNat，它基本上包含一个在编译时未知的KnownNat n => n。但是，您不希望尝试将其提升到已知类型级别Nat(即，您不想要promote0(。您希望保持原样，并且case在需要其类型级别值时与其匹配。该类型级别值将在case内可用，但在case外不可用，因此任何依赖于n的类型都不能"使用"；逃逸；案件陈述。

例如，你可以写：

import qualified Data.Vector.Sized as V
import Data.Proxy
import GHC.TypeNats
main = do
n <- readLn :: IO Int
-- keep `sn` as the type-level representation of the runtime `n`
let sn = someNatVal (fromIntegral n)
-- scrutinize it when you need its value at type level
case sn of
-- bind the contained Nat to the type variable `n`
SomeNat (Proxy :: Proxy n) -> do
-- now it's available at the type level
let v  = V.replicate @n 1   -- using type-level "n"
v2 = v V.++ v
print v2

但你不会写：

main :: IO ()
main = do
n <- readLn :: IO Int
let sn = someNatVal (fromIntegral n)
let v2 = case sn of
SomeNat (Proxy :: Proxy n) ->
let v  = V.replicate @n 1
in  v V.++ v
print v2

您将得到一个错误，即类型变量正在转义其作用域。(如果你想让大小的矢量泄漏到case之外，你需要使用V.SomeSized或类似的东西。(

至于你关于处理1 <= n约束的问题的主要部分，处理类型级自然数的不等式是一个令人头疼的问题。我认为你需要发布一个最简单的例子，确切地说明你想如何在大小向量实现的上下文中使用这个约束，以便得到一个不错的答案。