实例归纳作为约束

Question

我想表达的是给定的想法

instance (MonadTrans t, MonadX m) => MonadX (t m)

它应该遵循，只要所有 tx 都有 MonadTrans 实例，任何 t1 (t2 ... (tn m)) 也是 MonadX。但是，当我尝试将其写下来时，它不起作用：

{-# LANGUAGE BasicallyEverything #-}

data Dict c where
  Dict :: c => Dict c

class (forall m . Monad m => Monad (t m)) => MonadTrans t where
  lift :: Monad m => m a -> t m a

class    (c m, Monad m, forall t . (MonadTrans t, Monad (t m)) => c (t m)) => Foo c m
instance (c m, Monad m, forall t . (MonadTrans t, Monad (t m)) => c (t m)) => Foo c m

liftDict :: MonadTrans t => Dict (Foo c m) -> Dict (Foo c (t m))
liftDict Dict = Dict

这会导致以下错误：

    • Could not deduce: c (t1 (t m)) arising from a use of ‘Dict’
      from the context: MonadTrans t
        bound by the type signature for:
                   liftDict :: forall (t :: (* -> *) -> * -> *)
                                      (c :: (* -> *) -> Constraint) (m :: * -> *).
                               MonadTrans t =>
                               Dict (Foo c m) -> Dict (Foo c (t m))
        at src/Lib.hs:85:1-64
      or from: Foo c m
        bound by a pattern with constructor:
                   Dict :: forall (a :: Constraint). a => Dict a,
                 in an equation for ‘liftDict’
        at src/Lib.hs:86:10-13
      or from: (MonadTrans t1, Monad (t1 (t m)))
        bound by a quantified context at src/Lib.hs:1:1
    • In the expression: Dict
      In an equation for ‘liftDict’: liftDict Dict = Dict
    • Relevant bindings include
        liftDict :: Dict (Foo c m) -> Dict (Foo c (t m))
          (bound at src/Lib.hs:86:1)
   |
86 | liftDict Dict = Dict

有什么办法让它起作用吗？

Answer 1

你会得到与此处给出的 Foo c m 稍微简单一些的定义完全相同的错误：

 (c m, Monad m, forall t. MonadTrans t => c (t m))
                                      ^^^ don't really need Monad (t m) here

把一些变量名弄清楚，这样在写liftDict.

的时候，哪些变量是绝对相等的，哪些不是

有：

MonadTrans t
    forall m'. Monad m' => Monad (t m')
Foo c m
    c m
    Monad m
    forall t'. MonadTrans t' => c (t' m)

想要：

Foo c (t m)
    c (t m)
    Monad (t m)
    forall t''. MonadTrans t'' => c (t'' (t m))

在“想要”类别中，c (t m) 很简单——我们将 forall t'. MonadTrans t' => c (t' m) 应用于我们的 t'~t 和 MonadTrans t。 Monad (t m) 也很简单，只需将 forall m'. Monad m' => Monad (t m') 应用于 m'~m 和 Monad m.

但是最后一个……很棘手！你想要这些排队：

Have: forall t' . MonadTrans t'  => c (t'  m    )
Want: forall t''. MonadTrans t'' => c (t'' (t m))

但他们相当排队。这里发生的是 m 是一个固定的 monad，而不是我们可以专门针对 t m 的新选择的论证！好吧，让我们争论一下。

class    (c m, Monad m, forall m' t . (Monad m', MonadTrans t) => c (t m')) => Foo c m
instance (c m, Monad m, forall m' t . (Monad m', MonadTrans t) => c (t m')) => Foo c m

编译成功！但它不再表达我们想要的，因为我们在这里所说的归纳步骤不需要 c 约束。幸运的是，我们可以将其添加回去而不会导致它停止编译：

class    (c m, Monad m, forall m' t . (c m', Monad m', MonadTrans t) => c (t m')) => Foo c m
instance (c m, Monad m, forall m' t . (c m', Monad m', MonadTrans t) => c (t m')) => Foo c m

我认为您可能会发现将这些约束条件略微不同地分组是很直观的：

class ( (c m, Monad m) -- base case
      , forall m' t. (c m', Monad m', MonadTrans t) => c (t m')
      -- inductive hypothesis
      ) => Foo c m

但请注意：这个 Foo 的实例可能比您最初想象的要少。特别是，要有一个 Foo c 实例，可以有 只有一个 完全通用的 c 实例用于 type-level 应用程序。

实例归纳作为约束

Instance inductivity as constraint

haskell

typeclass

monad-transformers

quantified-constraints