haskell - 是否可以通过另一个类型构造函数派生 Traversable 实例？

Question

假设我们有一些类 Foo这样 Foo f 的实例为我们提供实现 Functor f 所需的一切, Foldable f和 Traversable f .为避免重复实例，可以见证 Foo 之间的这种关系和 Functor, Foldable, Traversable在新类型包装下:

type Foo :: (Type -> Type) -> Constraint
class Foo f
  where
  {- ... -}

type FoonessOf :: (Type -> Type) -> Type -> Type
newtype FoonessOf f a = FoonessOf (f a)

instance Foo f => Functor (FoonessOf f)
  where
  fmap = _

instance Foo f => Foldable (FoonessOf f)
  where
  foldMap = _

instance Foo f => Traversable (FoonessOf f)
  where
  traverse = _

现在假设我们有一些类型构造函数:

data Bar a = Bar {- ... -}

这样有一个:

instance Foo Bar
  where
  {- ... -}

我们想装备 Bar其“ Foo -ness”所暗示的实例。由于 Bar a是 Coercible至 FoonessOf Bar a ，我们希望能够导出实例 via FoonessOf Bar :

deriving via (FoonessOf Bar) instance Functor Bar
deriving via (FoonessOf Bar) instance Foldable Bar

这对于诸如 Functor 之类的类型类很有效。和 Foldable不幸的是，当我们尝试对 Traversable 做同样的事情时，事情出错了:

[typecheck -Wdeferred-type-errors] [E] • Couldn't match representation of type ‘f1 (Foo Bar a1)’
                           with that of ‘f1 (Bar a1)’
    arising from a use of ‘ghc-prim-0.6.1:GHC.Prim.coerce’
  NB: We cannot know what roles the parameters to ‘f1’ have;
    we must assume that the role is nominal
• In the expression:
      ghc-prim-0.6.1:GHC.Prim.coerce
        @(Foo Bar (f a) -> f (Foo Bar a)) @(Bar (f a) -> f (Bar a))
        (sequenceA @(Foo Bar)) ::
        forall (f :: TYPE ghc-prim-0.6.1:GHC.Types.LiftedRep
                     -> TYPE ghc-prim-0.6.1:GHC.Types.LiftedRep)
               (a :: TYPE ghc-prim-0.6.1:GHC.Types.LiftedRep).
        Applicative f => Bar (f a) -> f (Bar a)
  In an equation for ‘sequenceA’:
      sequenceA
        = ghc-prim-0.6.1:GHC.Prim.coerce
            @(Foo Bar (f a) -> f (Foo Bar a)) @(Bar (f a) -> f (Bar a))
            (sequenceA @(Foo Bar)) ::
            forall (f :: TYPE ghc-prim-0.6.1:GHC.Types.LiftedRep
                         -> TYPE ghc-prim-0.6.1:GHC.Types.LiftedRep)
                   (a :: TYPE ghc-prim-0.6.1:GHC.Types.LiftedRep).
            Applicative f => Bar (f a) -> f (Bar a)
  When typechecking the code for ‘sequenceA’
    in a derived instance for ‘Traversable Bar’:
    To see the code I am typechecking, use -ddump-deriv
  In the instance declaration for ‘Traversable Bar’
——————————————————————————————————————————————————————————————————————————————
...

所以我的问题是:

是否可以通过实例 Traversable Bar 提出其他一些派生方案？ ?

是否可以对 Traversable 进行一些修改？可以通过新类型派生的类？

Answer 1

我怀疑1.的答案是:不，情况无法挽救，不可能获得Traversable的实例。使用 DerivingVia .

就 2. 而言，尝试在更简单的上下文中重现问题很有用。考虑以下:

-- Remember to turn on ScopedTypeVariables!

data A = A
newtype B = B A

a :: forall f. f A -> f A
a = id

b :: forall f. f B -> f B
b = coerce $ a @f

看起来这应该可行，但是唉:

[typecheck -Wdeferred-type-errors] [E] • Couldn't match representation of type ‘f A’ with that of ‘f B’
    arising from a use of ‘coerce’
  NB: We cannot know what roles the parameters to ‘f’ have;
    we must assume that the role is nominal
• In the expression: coerce $ a @f
  In an equation for ‘b’: b = coerce $ a @f
• Relevant bindings include
    b :: f B -> f B

问题与类型构造函数参数的“角色”以及角色推断的工作方式有关。出于我们的目的，角色有两种类型:“代表性”和“非代表性”。同样出于我们的目的，两者之间的差异可以近似为以下内容:类型构造函数 F :: Type -> Type如果有 Representational F 的实例，则具有“代表性”角色的参数， 在哪里:

type Representational :: (Type -> Type) -> Constraint
type Representational f = forall x y. Coercible x y => Coercible (f x) (f y)

否则， F 的参数是非代表性的。

类型检查器允许您在不同的地方注释类型参数的角色(尽管很奇怪，不是那种)。可悲的是，没有办法注释更高种类的类型变量的角色。然而，我们能做的只是要求 Representational f直接地:

b' :: forall f. Representational f => f B -> f B
b' = coerce $ a @f

现在进行类型检查。这表明了一种可能的方法来调整 Traversable typeclass 使其可通过强制导出。

现在让我们看看 Traversable 的类型操作 sequenceA :

class Traversable t
  where
  sequenceA :: forall f. Applicative f => forall a. t (f a) -> f (t a)
  {- ... -}

注意:有那个讨厌的 forall f再次，意思是 f被认为具有名义角色的类型参数。
什么 DerivingVia要做的是尝试 coerce之间:

sequenceA @T1 :: forall f. Applicative f => forall a. T1 (f a) -> f (T2 a)

和:

sequenceA @T2 :: forall f. Applicative f => forall a. T2 (f a) -> f (T2 a)

尽管 T1 ( FoonessOf Bar ) 和 T2 ( Bar ) 被“参数化”强制，这种强制将失败，因为整个操作的强制最终将分解为类型检查器提示的强制:

Couldn't match representation of type
‘f1 (Foo Bar a1)’
with that of
‘f1 (Bar a1)’

这不起作用，因为 f的参数被认为具有名义作用，正如我们所讨论的。
与我们上面的简化示例一样，修复很简单:只需询问 Representational f :

type Traversable' :: (Type -> Type) -> Constraint
class Traversable' t
  where
  traverse :: (Representational f, Applicative f) => (a -> f b) -> t (f a) -> f (t b)

现在我们终于可以推导出 Traversable' 的实例了。通过 FoonessOf Bar :

instance Foo f => Traversable' (FoonessOf f)
  where
  traverse = _

deriving via (FoonessOf Bar) instance Traversable' Bar