使用 GADT 自动派生类型 class 约束

Question

我正在编写一个库来使用惰性求值处理无限序列。为简洁起见，我使用广义代数数据类型 (GADT) 对序列中每个项的索引断言 Ord 约束。因此进行以下类型检查：

{-# LANGUAGE GADTs #-}

data Term ix cff where
  Term :: (Ord ix) => ix -> cff -> Term ix cff

data Sequence ix cff where
  Seq :: [Term ix cff] -> Sequence ix cff

f (Seq (Term i x:_)) (Seq (Term j y:_)) = i < j

{-
add :: Sequence ix cff -> Sequence ix cff -> Sequence ix cff
add (Seq tms1) (Seq tms2) = Seq (addAlong (<) tms1 tms2)
    where addAlong :: (ix -> ix -> Bool) ->
                      [Term ix cff] -> [Term ix cff] -> [Term ix cff]
          addAlong ord (Term i x : tms1) (Term j y : tms2) = []
-}

不出所料，GHCi 告诉我 f :: Sequence t t1 -> Sequence t t2 -> Bool。进行比较 i < j 需要一个 Ord 实例，但这由 Term.

定义中的约束 (Ord ix) 处理

然而，当下面的块取消注释时，add 函数无法进行类型检查，错误为 No instance for (Ord ix) arising from the use of ``<''。 Sequence的定义中出现的Term ix cff不应该可以算出(Ord ix)吗？

Answer 1

默认情况下，绑定到函数参数的项是单态的（也称为 rank-0 多态），因为 Haskell98 仅支持 rank-1 多态，而多态参数使函数成为 rank-2 多态。

因此，在Seq (addAlong (<) tms1 tms2)中，编译器只能将<视为刚性类型ix上的单态比较。要将 < 视为单态函数，编译器需要解析 Ord 实例。但是，此时 Ord ix 实例不可用，因为它只能匹配 Term!

最接近您的原始代码的解决方案是显式使 addAlong rank-2 多态：

{-# LANGUAGE RankNTypes, UnicodeSyntax #-}

add :: Sequence ix cff -> Sequence ix cff -> Sequence ix cff
add (Seq tms1) (Seq tms2) = Seq (addAlong (<) tms1 tms2)
    where addAlong :: (∀ ix' . Ord ix' -> ix' -> Bool) ->
                      [Term ix cff] -> [Term ix cff] -> [Term ix cff]
          addAlong ord (Term i x : tms1) (Term j y : tms2) = []

这样，< 只是按原样传递（作为多态 Ord => ... 方法），因此编译器不需要在 Seq (addAlong (<) tms1 tms2) 处提供实例，但是稍后可以在 Term 可用时解决它。

你当然应该考虑你是否真的需要它。在每个 Term 中保留一个 Ord 字典对我来说似乎相当浪费——如果您将约束保留在 Seq 中，问题就不会出现：

data Term ix cff where Term :: ix -> cff -> Term ix cff

data Sequence ix cff where
  Seq :: Ord ix => [Term ix cff] -> Sequence ix cff

add :: Sequence ix cff -> Sequence ix cff -> Sequence ix cff
add (Seq tms1) (Seq tms2) = Seq (addAlong (<) tms1 tms2)
    where addAlong :: (ix -> ix -> Bool) ->
                      [Term ix cff] -> [Term ix cff] -> [Term ix cff]
          addAlong ord (Term i x : tms1) (Term j y : tms2) = []

使用 GADT 自动派生类型 class 约束

Automatically deriving type class constraints using GADTs

haskell

types

type-inference

algebraic-data-types

gadt