为什么 Haskell 不能推断出这种类型是正确的？

Question

我有一个 Nat 的简单定义和一个由 Nat 索引的类型的定义，Natty。

data Nat :: * where 
    Zero :: Nat
    Suc  :: Nat -> Nat

data Natty :: Nat -> * where
    Zy :: Natty Zero
    Sy :: Natty n -> Natty (Suc n)

我的目标是创建一个函数，给定一个由 Nat n 索引的类型和一个由 Nat m 索引的类型，将生成一个由类型 Nat n + m 索引的类型。

例如，foo (Sy Zy) (Sy $ Sy Zy) = Sy $ Sy $ Sy Zy

Nat加法很简单，定义如下：

nAdd :: Nat -> Nat -> Nat
nAdd x  Zero    = x
nAdd x (Suc y)  = Suc $ nAdd x y

我原以为 foo 会按以下方式类似地定义：

foo :: Natty n -> Natty m -> Natty (nAdd n m)
foo x  Zy    = x
foo x (Sy y) = Sy $ foo x y

但这会导致一个有趣的错误：

Could not deduce: n ~ nAdd n 'Zero
from the context: m ~ 'Zero

为什么不能haskell推导出n ~ nAdd n '0？有没有简单的方法来解决这个问题，还是需要其他方法？

谢谢，如有任何意见，我们将不胜感激。还使用了以下扩展名。

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

Answer 1

正如@AlexisKing 所指出的，foo 的类型签名中的 nAdd 只是被视为另一个类型变量（如 m 或 n）和 Haskell 没有将它与函数 nAdd.

的定义联系起来

在 Haskell 中，您不能将术语级函数（如 nAdd）应用于类型。相反，您需要使用类型族。如果将类型级别 "function" NAdd 定义为类型系列：

type family NAdd (a :: Nat) (b :: Nat) :: Nat
type instance NAdd n Zero = n
type instance NAdd n (Suc m) = Suc (NAdd n m)

那么你就可以在你的foo签名中使用这个函数了：

foo :: Natty n -> Natty m -> Natty (NAdd n m)
foo x  Zy    = x
foo x (Sy y) = Sy $ foo x y

这需要一些额外的扩展才能工作，完整的工作示例（运行在 GHC 8.2.2 下）如下所示：

{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeInType #-}

import Data.Kind

data Nat :: * where 
    Zero :: Nat
    Suc  :: Nat -> Nat

data Natty :: Nat -> * where
    Zy :: Natty Zero
    Sy :: Natty n -> Natty (Suc n)

type family NAdd (a :: Nat) (b :: Nat) :: Nat
type instance NAdd n Zero = n
type instance NAdd n (Suc m) = Suc (NAdd n m)

nAdd :: Nat -> Nat -> Nat
nAdd x  Zero    = x
nAdd x (Suc y)  = Suc $ nAdd x y

foo :: Natty n -> Natty m -> Natty (NAdd n m)
foo x  Zy    = x
foo x (Sy y) = Sy $ foo x y 

test1 = foo (Sy Zy) (Sy $ Sy Zy)
test2 = Sy $ Sy $ Sy Zy

为什么 Haskell 不能推断出这种类型是正确的？

Why can't Haskell deduce that this type is correct?

haskell

types

gadt