Haskell 类型级别文字 Nat：状态？

Question

GHC 具有类型级别文字 Nats。我可以阅读一些关于它们的信息，例如，在这里：

https://ghc.haskell.org/trac/ghc/wiki/TypeNats

不幸的是，关于它们的文档似乎很少，而且我尝试用它们做的几乎没有任何实际效果。

来自 this page 的评论 18 提到了这个大小参数化 Vecs 的简单示例（我添加了 LANGUAGE pragmas 和导入语句）：

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeOperators #-}

import GHC.TypeLits

data Vec :: Nat -> * -> * where
  Nil  :: Vec 0 a
  (:>) :: a -> Vec n a -> Vec (n+1) a

(+++) :: Vec n a -> Vec m a -> Vec (n+m) a
Nil       +++ bs = bs
(a :> as) +++ bs = a :> (as +++ bs)

它当时不工作，但后来据称修改了实现，以便它工作。那是 5 年前的事了……但它在我的 GHC 7.10.1 上不起作用：

trash.hs:15:20:
    Could not deduce ((n + m) ~ ((n1 + m) + 1))
    from the context (n ~ (n1 + 1))
      bound by a pattern with constructor
                 :> :: forall a (n :: Nat). a -> Vec n a -> Vec (n + 1) a,
               in an equation for ‘+++’
      at trash.hs:15:2-8
    NB: ‘+’ is a type function, and may not be injective
    Expected type: Vec (n + m) a
      Actual type: Vec ((n1 + m) + 1) a
    Relevant bindings include
      bs :: Vec m a (bound at trash.hs:15:15)
      as :: Vec n1 a (bound at trash.hs:15:7)
      (+++) :: Vec n a -> Vec m a -> Vec (n + m) a
        (bound at trash.hs:14:1)
    In the expression: a :> (as +++ bs)
    In an equation for ‘+++’: (a :> as) +++ bs = a :> (as +++ bs)

这是怎么回事？类型级别的文字 Nats 应该可用于这种事情吗？如果是这样，我如何实现 (+++) 功能？如果不是，他们的用例是什么？

Answer 1

正如评论者所提到的，类型检查器目前无法解除这种等式，因为它们需要代数。尽管你我都知道 n + m = n1 + m + 1 给定 n = n1 + 1，但没有人教过 GHC 类型检查器如何执行那种算术。在像 Ada、Idris 或 Coq 这样的语言中，您可以教编译器这些规则，或者算术规则可能会在库中提供给您，但在 Haskell 中，类型检查器更加严格（但在我看来，这对现实世界的编程更友好），不幸的是你不得不求助于类型检查器插件。

据我所知，在这个问题上最积极的人是 Iavor Diatchki. That paper is behind the dumb ACM paywall, but you can find his Haskell Symposium 2015 talk here on YouTube — it's very well-explained!. His talk uses the same example as yours, the ever-popular vector. His branch in the GHC repository works on merging it into mainline GHC, but as far as I know there are no dates set. For now you have to use the typechecker plugin, which is not so bad. After all, the original goal of Plugins/Typechecker 是为了启用这样有趣的工作，而不必将所有内容合并到源代码中。模块化有话要说！

Haskell 类型级别文字 Nat：状态？

Haskell type level literal Nat: status?

haskell

dependent-type