如何在 Haskell 中实现部分单射类型族？

Question

我正在 Haskell 中实现各种需要类型安全自然数的函数，并且最近需要一个指数类型来表示新类型。

下面是我整理的三个类型族，方便大家参考。

type family Add n m where
  Add 'One n = 'Succ n
  Add ('Succ n) m = 'Succ (Add n m)

-- Multiplication, allowing ever more powerful operators
type family Mul n m where
  Mul 'One m = m
  Mul ('Succ n) m = Add m (Mul n m)

-- Exponentiation, allowing even even more powerful operators
type family Exp n m where
  Exp n 'One = n
  Exp n ('Succ m) = Mul n (Exp n m)

但是，在使用这种类型时，我遇到了一个问题，它不是单射的；这意味着我有点想要的一些类型推断并不存在。（错误是 NB: ‘Exp’ is a non-injective type family）。我可以使用 -XAllowAmbiguousTypes 忽略这个问题，但我不想使用这个扩展，所以所有类型都可以检查函数定义的位置。

我认为当 m 为常量时 Exp n m 应该是单射的，所以我想尝试实现它，但经过大量试验和错误后我不确定如何做到这一点。即使它目前不能解决我的问题，但将来可能会有用。或者，Exp n m 对于给定的 n 是单射的，其中 m 发生变化，而 n 不是 One.

在询问其他人后，他们建议像 type family Exp n m = inj | inj, n -> m where 这样的东西，但这不起作用，如果逗号存在则给出语法错误，最后的 n 则给出解析错误它不是。这旨在允许 inj 和 n 唯一标识给定的 m.

我正在尝试实现但目前遇到问题的函数具有如下签名。

tensorPower :: forall i a n m . (Num a, KnownNat i) => Matrix n m a -> Matrix (Exp n i) (Exp m i) a

可以使用 tensorPower @Three a 调用此函数（当设置了 -XAllowAmbiguousTypes 时），但我希望 GHC 能够在可能的情况下自行确定 i 值。出于这个问题的目的，可以假设给定的 a 矩阵不是多态的。

将约束调整为以下也不起作用；这是在上述函数的类型而不是定义类型族的地方创建单射性的尝试

forall i a n m
   . ( Num a
     , KnownNat i
     , Exp n ( 'Succ i) ~ Mul n (Exp n i)
     , Exp m ( 'Succ i) ~ Mul m (Exp m i)
     , Exp n One ~ n
     , Exp m One ~ m
     )

那么，这个函数是否可以实现单射性，如果可以，我该如何实现？

（要查看更多代码，请访问 repository。src 文件夹包含大部分代码源，主要区域在此属于 Lib.hs 和 Quantum.hs 的问题。所使用的扩展可以（大部分）在 package.yaml)

中找到

Answer 1

实际上有一种非常简单的方法可以至少以一种方式让它工作；以下 type family，当在约束中适当使用时，允许在没有注释的情况下使用 tensorPower。

-- Reverse the exponent - if it can't match then it goes infinitely
type family RLog n m x c where
  RLog m n n i = i
  RLog m n x i = RLog m n (Mul m x) ('Succ i)

type ReverseLog n m = RLog n m n 'One
type GetExp n i = ReverseLog n (Exp n i)
----------------
-- adjusted constraint for tensorPower
forall i a n m . (Num a, KnownNat i, i ~ GetExp n i, i ~ GetExp m i)

例如，现在可以键入 (tensorPower hadamard) *.* (zero .*. zero .*. one)（其中 hadamard 是 Matrix Two Two Double，zero 和 one 都是 Matrix Two One Double， (*.*)是矩阵乘法，(.*.)是张量积，i的类型完全推断出来了）。

这个类型族的工作方式是它有四个参数：基数、目标、累加器和当前指数。如果目标和累加器相等，则“返回”当前指数。如果它们不相等，我们通过将当前累加器乘以基数递归，并递增当前指数。

我发现此解决方案存在一个问题：如果它无法匹配“基数”，它会出现非常长的错误消息，因为它会尽可能深入地递归到类型中。这可以通过做一些其他类型的技巧来解决，这超出了这个问题的范围，但可以在我的项目存储库的 this commit 中看到。

总而言之：引入一些抽象的单射性似乎是行不通的，但是实现一种指数的反转会产生干净、简单和有效的代码——这实际上是单射性，通过证明存在Exp.

的可逆函数

（需要注意的是，此解决方案需要更多操作才能充分发挥作用，因为 GetExp n i 不适用于 n=='One；我通过从未使用 GetExp ('One) i 首先）

如何在 Haskell 中实现部分单射类型族？

How do I implement a partially injective type family in Haskell?

haskell

type-families

type-level-computation