如何使用单例库中的依赖对类型 Sigma？

Question

如何使用依赖对类型Sigma from the singletons库？

假设存在以下类型索引列表和复制函数：

data Vect :: Nat -> Type -> Type where
  VNil :: Vect 0 a
  VCons :: a -> Vect n a -> Vect (n + 1) a

replicateVec :: forall n a. Sing n -> a -> Vect n a

（您可以在中找到 replicateVec 的几个不同实现）。

我想创建一个函数 replicateVecSigma，在依赖对中 returns 和 Vect。理想情况下应该像下面这样：

replicateVecSigma :: Natural -> Sigma Nat (\n -> Vect n String)

怎么用Sigma写这个函数呢？还有函数的类型怎么写？

实际上，我可以按如下方式实现 replicateVecSigma，但它看起来不是很干净：

data Foo a b (m :: TyFun Nat Type)

type instance Apply (Foo a b) (n :: Nat) = a n b

replicateVecSigma :: Natural -> Sigma Nat (Foo Vect String)
replicateVecSigma i =
  case toSing i of
    SomeSing snat -> snat :&: replicateVec snat "hello"

似乎很不幸，我必须声明这个 Foo 类型和 Apply 实例才能使用 Sigma。 singletons 库是否提供任何方法使 Sigma 的工作更容易？

你可以找到我的完整代码here。

为了完整起见，这里是 Sigma 的定义：

data Sigma (s :: Type) :: (s ~> Type) -> Type where
  (:&:) :: forall s t fst. Sing (fst :: s) -> t @@ fst -> Sigma s t

这里是~>:

type a ~> b = TyFun a b -> *

data TyFun :: * -> * -> *

instance (SingKind k1, SingKind k2) => SingKind (k1 ~> k2)

type instance Demote (k1 ~> k2) = Demote k1 -> Demote k2

class SingKind k where
  type family Demote k :: * = r | r -> k
  fromSing :: forall (a :: k). Sing a -> Demote k
  toSing :: Demote k -> SomeSing k

这里是@@:

type a @@ b = Apply a b

type family Apply (f :: k1 ~> k2) (x :: k1) :: k2

singletons 为 Apply.

定义了一堆实例

TyFun and Apply 是如何工作的？

下面是上面的三个问题：

如何使用Sigma写出像replicateVecSigma :: Natural -> Sigma Nat (\n -> Vect n String)这样的函数？
我可以使用上面的 Foo 类型编写 replicateVecSigma，但似乎额外工作太多。有没有更简单的方法？
TyFun 和 Apply 是如何工作的？

Answer 1

在这种特定情况下，我们要计算类型级别的 lambda

\n -> Vect n String

不幸的是，我们没有类型级别的 lambda。最多，我们可以像 OP 那样定义类型族。但是，我们可以用 pointfree 风格重写 lambda：

\n -> flip Vect String n    -- pseudocode
flip Vect String

我们可以使用 singletons 类型级 Flip 类型函数将这个想法转化为实际类型。在这里，我们想部分应用带有两个参数的 Flip（在饱和调用中需要三个参数），因此我们使用 "defunctionalized" FlipSym2 变体。

这样编译：

replicateVecSigma :: Natural -> Sigma Nat (FlipSym2 (TyCon Vect) String)
replicateVecSigma i =
  case toSing i of
    SomeSing snat -> snat :&: replicateVec snat "hello"

如果我们从一开始就在最后一个位置设置 n 参数，我们就可以避免 Flip.

data Vect2 :: Type -> Nat -> Type where
  VNil2 :: Vect2 a 0
  VCons2 :: a -> Vect2 a n -> Vect2 a (n + 1)

replicateVec2 :: forall n a. Sing n -> a -> Vect2 a n
replicateVec2 = undefined

replicateVecSigma2 :: Natural -> Sigma Nat (TyCon (Vect2 String))
replicateVecSigma2 i =
  case toSing i of
    SomeSing snat -> snat :&: replicateVec2 snat "hello"

（TyCon Vect2 @@ String 也适用于此，在非功能化级别使用显式应用程序 @@，而不是实际类型应用程序。）

非常粗略地说，您可以将 FlipSym0, FlipSym1, FlipSym2 等去功能化变体视为基本标签（不是函数！），除了 Apply 让您使用他们假装他们是函数。通过这种方式，我们可以像处理函数一样处理非函数 ("tags")。这是必需的，因为在 Haskell 中，我们没有类型级别的函数，所以我们必须使用这些 "pretend" 版本。

该方法很通用，但它确实需要程序员做更多的工作。

我不知道有任何模板 Haskell 实用程序可以自动将类型级 lambda 转换为无点形式，然后使它们失去功能。那会很有用。

Answer 2

去功能化 是解决缺少 first-class 函数的通用方法（事实上，它最初被发现是作为一种编译技术来摆脱那些），将它们编码为符号，由单个一阶Apply函数解释。

例如，你的Foo a b是一个编码函数\n -> a n b的符号。

获得等效符号的另一种方法是遵循 (\n -> a n b) = flip a b.

的直觉

注意像Vec这样的类型构造函数本身不是可以传递给Apply的符号，而是必须包裹在"symbol constructors"中：TyCon2 Vec是\n -> \b -> Vec n b.

singletons有一个符号为flip，FlipSym0（符号可以通过将其他符号作为参数来表示高阶函数）。

Foo a b = Apply (Apply FlipSym0 (TyCon2 a)) b

请注意，部分应用程序会缩减为其他符号：

        = Apply (FlipSym1 (TyCon2 a)) b
        = FlipSym2 (TyCon2 a) b

TyFun 类型是一种为非功能化符号赋予类型的方法。我看到的主要好处是类型推断；没有它，类型族可能会陷入混乱。

另请参阅 Richard Eisenberg 关于 Haskell 类型去功能化的博文：https://typesandkinds.wordpress.com/2013/04/01/defunctionalization-for-the-win/

如何使用单例库中的依赖对类型 Sigma？

How to use the dependent pair type Sigma from the singletons library?

haskell

types

dependent-type

singleton-type