类型级约束编码

Question

所以我有一个数据构造函数，我只在包含 Nat 的类型级别使用。通常，如果我在类型级别传递它并且我想将 Nat 反映到术语级别，我需要一个 KnownNat 约束。我想要做的是将此 KnownNat 约束编码到类型本身中，因此如果此类型出现在某处的签名中，则会在函数主体中推断出 KnownNat 约束。这意味着我将不再需要在使用站点编写 KnownNat 约束。我只需要确保在构建时满足 KnownNat 约束。

我想为此使用 GADT 并做到了这一点：

data Foo = Foo Nat Nat

type family GetA (f :: Foo) :: Nat where
  GetA ('Foo a _) = a

type family GetB (f :: Foo) :: Nat where
  GetB ('Foo _ b) = b

data KnownFoo (f :: Foo) where
  KnownFoo :: (KnownNat (GetA f), KnownNat (GetB f)) => KnownFoo f

foo :: forall (f :: Foo) (kf :: KnownFoo f). Proxy kf -> Integer
foo _ = natVal $ Proxy @(GetA f)

但这不起作用，因为类型检查器不理解 GetA f 是 KnownNat，即使传入了 KnownFoo。有没有办法让像这样的作品？

我还尝试将 f :: Foo 完全移动到 KnownFoo 约束中，如下所示：

data Foo = Foo Nat Nat

type family GetA (f :: Foo) :: Nat where
  GetA ('Foo a _) = a

type family GetB (f :: Foo) :: Nat where
  GetB ('Foo _ b) = b

data KnownFoo where
  KnownFoo :: forall f. (KnownNat (GetA f), KnownNat (GetB f)) => Proxy f -> KnownFoo

type family GetFoo (kf :: KnownFoo) :: Foo where
  GetFoo ('KnownFoo (Proxy f)) = f

但是我没有办法写 GetFoo 类型族，因为它抱怨 KnownNat 无法推广。

感谢任何帮助！

Answer 1

我不确定我是否完全理解您的需求，但如果您想存储 KnownNat 约束，则必须有一些运行时表示。也许这样的事情对你有用：

{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE RankNTypes #-}

import GHC.TypeLits

data FooC a b where
    FooR :: (KnownNat a, KnownNat b) => FooC a b

type family GetA x where GetA (FooC a b) = a
type family GetB x where GetB (FooC a b) = b

withKnowledge :: FooC a b -> ((KnownNat a, KnownNat b) => r) -> r
withKnowledge FooR r = r

请注意 DataKinds 甚至不在这里：我们直接定义我们想要的新类型，而不是间接定义它的降低形式。我想你可以为此制作一个类似的 Known class。

class KnownFoo f where witness :: f
instance (KnownNat a, KnownNat b) => KnownFoo (FooC a b) where witness = FooR

withKnownFoo :: forall f a b r. (KnownFoo f, f ~ FooC a b) => ((KnownNat (GetA f), KnownNat (GetB f)) => r) -> r
withKnownFoo = withKnowledge (witness @f)

虽然它似乎不是很有用。任何时候你可以写 withKnownFoo x，你已经在范围内有适当的 KnownNat 实例来写 x 并且无论如何都满足它的约束。

类型级约束编码

type level constraint encoding

haskell

ghc

gadt

type-level-computation