如何在 haskell 中组合 'freer' 效果？
How do I compose 'freer' effects in haskell?
我正在尝试将一个简单的解释器从基于 transformers 的 monad 堆栈重写为基于 freer 的效果，但我 运行 遇到了将我的意图传达给 GHC 类型系统的困难。
我目前只使用State和Fresh效果。我正在使用两种状态，我的效果器看起来像这样：
runErlish g ls = run . runGlobal g . runGensym 0 . runLexicals ls
where runGlobal = flip runState
runGensym = flip runFresh'
runLexicals = flip runState
除此之外，我定义了一个函数 FindMacro，类型为：
findMacro :: Members [State (Global v w), State [Scope v w]] r
=> Arr r Text (Maybe (Macro (Term v w) v w))
到目前为止，所有这些都运行良好。当我尝试编写 macroexpand2 时出现问题（好吧，macroexpand1，但我正在简化它以便更容易理解问题）：
macroexpand2 s =
do m <- findMacro s
return $ case m of
Just j -> True
Nothing -> False
这会产生以下错误：
Could not deduce (Data.Open.Union.Member'
(State [Scope v0 w0])
r
(Data.Open.Union.FindElem (State [Scope v0 w0]) r))
from the context (Data.Open.Union.Member'
(State [Scope v w])
r
(Data.Open.Union.FindElem (State [Scope v w]) r),
Data.Open.Union.Member'
(State (Global v w))
r
(Data.Open.Union.FindElem (State (Global v w)) r))
bound by the inferred type for `macroexpand2':
(Data.Open.Union.Member'
(State [Scope v w])
r
(Data.Open.Union.FindElem (State [Scope v w]) r),
Data.Open.Union.Member'
(State (Global v w))
r
(Data.Open.Union.FindElem (State (Global v w)) r)) =>
Text -> Eff r Bool
at /tmp/flycheck408QZt/Erlish.hs:(79,1)-(83,23)
The type variables `v0', `w0' are ambiguous
When checking that `macroexpand2' has the inferred type
macroexpand2 :: forall (r :: [* -> *]) v (w :: [* -> *]).
(Data.Open.Union.Member'
(State [Scope v w])
r
(Data.Open.Union.FindElem (State [Scope v w]) r),
Data.Open.Union.Member'
(State (Global v w))
r
(Data.Open.Union.FindElem (State (Global v w)) r)) =>
Text -> Eff r Bool
Probable cause: the inferred type is ambiguous
好的，我可以给类型加一个Members注解：
macroexpand2 :: Members [State (Global v w), State [Scope v w]] r
=> Text -> Eff r Bool
现在我明白了：
Overlapping instances for Member (State [Scope v0 w0]) r
arising from a use of `findMacro'
Matching instances:
instance Data.Open.Union.Member'
t r (Data.Open.Union.FindElem t r) =>
Member t r
-- Defined in `Data.Open.Union'
There exists a (perhaps superclass) match:
from the context (Members
'[State (Global v w), State [Scope v w]] r)
bound by the type signature for
macroexpand2 :: Members
'[State (Global v w), State [Scope v w]] r =>
Text -> Eff r Bool
at /tmp/flycheck408QnV/Erlish.hs:(79,17)-(80,37)
(The choice depends on the instantiation of `r, v0, w0'
To pick the first instance above, use IncoherentInstances
when compiling the other instance declarations)
In a stmt of a 'do' block: m <- findMacro s
In the expression:
do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
In an equation for `macroexpand2':
macroexpand2 s
= do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
有人建议我在 irc 上尝试 forall r v w.，但没有任何区别。出于好奇，我在编译 this 代码时尝试使用 IncoherentInstances （我不喜欢检查 freer 和 playing 的分支）看看它是否会给我一个线索发生了什么事。它没有：
Could not deduce (Data.Open.Union.Member'
(State [Scope v0 w0])
r
(Data.Open.Union.FindElem (State [Scope v0 w0]) r))
arising from a use of `findMacro'
from the context (Members
'[State (Global v w), State [Scope v w]] r)
bound by the type signature for
macroexpand2 :: Members
'[State (Global v w), State [Scope v w]] r =>
Text -> Eff r Bool
at /tmp/flycheck408eru/Erlish.hs:(79,17)-(80,37)
The type variables `v0', `w0' are ambiguous
Relevant bindings include
macroexpand2 :: Text -> Eff r Bool
(bound at /tmp/flycheck408eru/Erlish.hs:81:1)
Note: there are several potential instances:
instance (r ~ (t' : r'), Data.Open.Union.Member' t r' n) =>
Data.Open.Union.Member' t r ('Data.Open.Union.S n)
-- Defined in `Data.Open.Union'
instance (r ~ (t : r')) =>
Data.Open.Union.Member' t r 'Data.Open.Union.Z
-- Defined in `Data.Open.Union'
In a stmt of a 'do' block: m <- findMacro s
In the expression:
do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
In an equation for `macroexpand2':
macroexpand2 s
= do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
所以，这是我对 freer 内部结构的理解用完了，我有问题：
- 为什么会有重叠实例？我不明白这是从哪里来的。
- IncoherentInstances 实际上 做什么？自动选择听起来很可能导致难以调试的错误。
- 如何在另一个函数中实际使用 findMacro？
干杯！
可扩展效果的类型推断在历史上一直很糟糕。让我们看一些例子：
{-# language TypeApplications #-}
-- mtl
import qualified Control.Monad.State as M
-- freer
import qualified Control.Monad.Freer as F
import qualified Control.Monad.Freer.State as F
-- mtl works as usual
test1 = M.runState M.get 0
-- this doesn't check
test2 = F.run $ F.runState F.get 0
-- this doesn't check either, although we have a known
-- monomorphic state type
test3 = F.run $ F.runState F.get True
-- this finally checks
test4 = F.run $ F.runState (F.get @Bool) True
-- (the same without TypeApplication)
test5 = F.run $ F.runState (F.get :: F.Eff '[F.State Bool] Bool) True
我将尝试解释一般问题并提供最少的代码说明。代码的独立版本可以是 found here.
在最基本的层面上（忽略优化表示），Eff 定义如下：
{-# language
GADTs, DataKinds, TypeOperators, RankNTypes, ScopedTypeVariables,
TypeFamilies, DeriveFunctor, EmptyCase, TypeApplications,
UndecidableInstances, StandaloneDeriving, ConstraintKinds,
MultiParamTypeClasses, FlexibleInstances, FlexibleContexts,
AllowAmbiguousTypes, PolyKinds
#-}
import Control.Monad
data Union (fs :: [* -> *]) (a :: *) where
Here :: f a -> Union (f ': fs) a
There :: Union fs a -> Union (f ': fs) a
data Eff (fs :: [* -> *]) (a :: *) =
Pure a | Free (Union fs (Eff fs a))
deriving instance Functor (Union fs) => Functor (Eff fs)
换句话说，Eff 是一个来自函子列表联合的自由单子。 Union fs a 表现得像 n 进制 Coproduct。二进制 Coproduct 类似于 Either 两个仿函数：
data Coproduct f g a = InL (f a) | InR (g a)
相比之下，Union fs a 让我们从函子列表中选择一个函子：
type MyUnion = Union [[], Maybe, (,) Bool] Int
-- choose the first functor, which is []
myUnion1 :: MyUnion
myUnion1 = Here [0..10]
-- choose the second one, which is Maybe
myUnion2 :: MyUnion
myUnion2 = There (Here (Just 0))
-- choose the third one
myUnion3 :: MyUnion
myUnion3 = There (There (Here (False, 0)))
我们以实现State效果为例。首先，我们需要为 Union fs 提供一个 Functor 实例，因为如果 Functor (Union fs)，Eff 只有一个 Monad 实例。
Functor (Union '[]) 是微不足道的，因为空联合没有值：
instance Functor (Union '[]) where
fmap f fs = case fs of {} -- using EmptyCase
否则我们在联合前面添加一个函子：
instance (Functor f, Functor (Union fs)) => Functor (Union (f ': fs)) where
fmap f (Here fa) = Here (fmap f fa)
fmap f (There u) = There (fmap f u)
现在 State 定义和跑步者：
run :: Eff '[] a -> a
run (Pure a) = a
data State s k = Get (s -> k) | Put s k deriving Functor
runState :: forall s fs a. Functor (Union fs) => Eff (State s ': fs) a -> s -> Eff fs (a, s)
runState (Pure a) s = Pure (a, s)
runState (Free (Here (Get k))) s = runState (k s) s
runState (Free (Here (Put s' k))) s = runState k s'
runState (Free (There u)) s = Free (fmap (`runState` s) u)
我们已经可以开始编写和 运行 我们的 Eff 程序，尽管我们缺少所有的糖和便利：
action1 :: Eff '[State Int] Int
action1 =
Free $ Here $ Get $ \s ->
Free $ Here $ Put (s + 10) $
Pure s
-- multiple state
action2 :: Eff '[State Int, State Bool] ()
action2 =
Free $ Here $ Get $ \n -> -- pick the first effect
Free $ There $ Here $ Get $ \b -> -- pick the second effect
Free $ There $ Here $ Put (n < 10) $ -- the second again
Pure ()
现在：
> run $ runState action1 0
(0,10)
> run $ (`runState` False) $ (`runState` 0) action2
(((),0),True)
这里只缺少两个基本的东西。
第一个是 Eff 的 monad 实例，它让我们使用 do-notation 而不是 Free 和 Pure，也让我们使用许多多态单子函数。写起来简单，这里略过。
第二个 inference/overloading 用于从效果列表中选择效果。以前我们需要写 Here x 来选择第一个效果， There (Here x) 来选择第二个，依此类推。相反，我们想编写在效果列表中具有多态性的代码，因此我们所要做的就是指定一些效果是列表的一个元素，并且一些隐藏类型 class 魔法将插入适当数量的 There-s.
我们需要一个 Member f fs class 可以在 f 是 [=54= 的元素时将 f a-s 注入 Union fs a-s ].从历史上看，人们以两种方式实现它。
首先，直接用OverlappingInstances：
class Member (f :: * -> *) (fs :: [* -> *]) where
inj :: f a -> Union fs a
instance Member f (f ': fs) where
inj = Here
instance {-# overlaps #-} Member f fs => Member f (g ': fs) where
inj = There . inj
-- it works
injTest1 :: Union [[], Maybe, (,) Bool] Int
injTest1 = inj [0]
injTest2 :: Union [[], Maybe, (,) Bool] Int
injTest2 = inj (Just 0)
其次，间接地，通过首先用类型族计算 fs 中 f 的索引，然后用非重叠 class 实现 inj，引导通过 f-s 计算的索引。这通常被认为更好，因为人们往往不喜欢重叠实例。
data Nat = Z | S Nat
type family Lookup f fs where
Lookup f (f ': fs) = Z
Lookup f (g ': fs) = S (Lookup f fs)
class Member' (n :: Nat) (f :: * -> *) (fs :: [* -> *]) where
inj' :: f a -> Union fs a
instance fs ~ (f ': gs) => Member' Z f fs where
inj' = Here
instance (Member' n f gs, fs ~ (g ': gs)) => Member' (S n) f fs where
inj' = There . inj' @n
type Member f fs = Member' (Lookup f fs) f fs
inj :: forall fs f a. Member f fs => f a -> Union fs a
inj = inj' @(Lookup f fs)
-- yay
injTest1 :: Union [[], Maybe, (,) Bool] Int
injTest1 = inj [0]
freer 库使用第二种解决方案，而 extensible-effects 对于 7.8 之前的 GHC 版本使用第一种，对于较新的 GHC-s 使用第二种。
无论如何，这两种解决方案都具有相同的推理限制，即我们几乎总是 Lookup 只有具体的单态类型，而不是包含类型变量的类型。 ghci 中的示例：
> :kind! Lookup Maybe [Maybe, []]
Lookup Maybe [Maybe, []] :: Nat
= 'Z
之所以可行，是因为 Maybe 或 [Maybe, []] 中都没有类型变量。
> :kind! forall a. Lookup (Either a) [Either Int, Maybe]
forall a. Lookup (Either a) [Either Int, Maybe] :: Nat
= Lookup (Either a) '[Either Int, Maybe]
这个卡住了，因为 a 类型变量阻止了缩减。
> :kind! forall a. Lookup (Maybe a) '[Maybe a]
forall a. Lookup (Maybe a) '[Maybe a] :: Nat
= Z
这是可行的，因为我们对任意类型变量的唯一了解是它们等于它们自己，并且 a 等于 a。
一般来说，类型族缩减会卡在变量上，因为约束求解可能会在以后将它们细化为不同的类型，因此 GHC 不能对它们做出任何假设（除了与它们自己相等）。 OverlappingInstances 实现（尽管没有任何类型族）也出现了本质上相同的问题。
鉴于此，让我们重新审视freer。
import Control.Monad.Freer
import Control.Monad.Freer.State
test1 = run $ runState get 0 -- error
GHC 知道我们有一个只有单一效果的堆栈，因为 run 适用于 Eff '[] a。它还知道该效果必须是 State s。但是当我们写 get 时，GHC 只知道它对一些新的 t 变量有 State t 的影响，并且 Num t 必须成立，所以当它试图计算freer 相当于 Lookup (State t) '[State s]，它卡在类型变量上，任何进一步的实例解析都会在卡住的类型族表达式上绊倒。另一个例子：
foo = run $ runState get False -- error
这也失败了，因为 GHC 需要计算 Lookup (State s) '[State Bool]，虽然我们知道状态必须是 Bool，但由于 s 变量，这仍然会卡住。
foo = run $ runState (modify not) False -- this works
这是可行的，因为 modify not 的状态类型可以解析为 Bool，并且 Lookup (State Bool) '[State Bool] 减少。
现在，在绕了这么大的弯路之后，我将在 post.
末尾回答您的问题
Overlapping instances 并不表示任何可能的解决方案，只是一个类型错误工件。我需要更多的代码上下文来查明它究竟是如何产生的，但我确信它不相关，因为一旦 Lookup 卡住，情况就变得毫无希望了。
IncoherentInstances 也无关紧要，无济于事。我们需要一个具体的效果位置索引才能为程序生成代码，Lookup卡住不能凭空拉一个索引。
findMacro 的问题是它对状态内的类型变量有 State 影响。每当您想使用 findMacro 时，您必须确保 Scope 和 Global 的 v 和 w 参数是已知的具体类型。您可以通过类型注释来做到这一点，或者更方便地您可以使用 TypeApplications，并写 findMacro @Int @Int 来指定 v = Int 和 w = Int。如果在多态函数中有 findMacro，则需要使用该函数的 forall v w. 注释启用 ScopedTypeVariables、绑定 v 和 w，并编写 findMacro @v @w使用的时候。您还需要为多态 v 或 w 启用 {-# language AllowAmbiguousTypes #-}（正如评论中指出的那样）。我认为尽管在 GHC 8 中它与 TypeApplications 一起启用是一个合理的扩展。
附录：
然而，幸运的是，新的 GHC 8 功能让我们修复了可扩展效果的类型推断，我们可以推断出 mtl 可以处理的一切，也可以推断出一些 mtl 无法处理的事情。新的类型推断对于效果的排序也是不变的。
我有一个 minimal implementation here 以及一些示例。然而，它还没有在我所知道的任何效果库中使用。我可能会写一篇关于它的文章，并提出拉取请求以便将其添加到 freer。
我正在尝试将一个简单的解释器从基于 transformers 的 monad 堆栈重写为基于 freer 的效果，但我 运行 遇到了将我的意图传达给 GHC 类型系统的困难。
我目前只使用State和Fresh效果。我正在使用两种状态，我的效果器看起来像这样：
runErlish g ls = run . runGlobal g . runGensym 0 . runLexicals ls
where runGlobal = flip runState
runGensym = flip runFresh'
runLexicals = flip runState
除此之外，我定义了一个函数 FindMacro，类型为：
findMacro :: Members [State (Global v w), State [Scope v w]] r
=> Arr r Text (Maybe (Macro (Term v w) v w))
到目前为止，所有这些都运行良好。当我尝试编写 macroexpand2 时出现问题（好吧，macroexpand1，但我正在简化它以便更容易理解问题）：
macroexpand2 s =
do m <- findMacro s
return $ case m of
Just j -> True
Nothing -> False
这会产生以下错误：
Could not deduce (Data.Open.Union.Member'
(State [Scope v0 w0])
r
(Data.Open.Union.FindElem (State [Scope v0 w0]) r))
from the context (Data.Open.Union.Member'
(State [Scope v w])
r
(Data.Open.Union.FindElem (State [Scope v w]) r),
Data.Open.Union.Member'
(State (Global v w))
r
(Data.Open.Union.FindElem (State (Global v w)) r))
bound by the inferred type for `macroexpand2':
(Data.Open.Union.Member'
(State [Scope v w])
r
(Data.Open.Union.FindElem (State [Scope v w]) r),
Data.Open.Union.Member'
(State (Global v w))
r
(Data.Open.Union.FindElem (State (Global v w)) r)) =>
Text -> Eff r Bool
at /tmp/flycheck408QZt/Erlish.hs:(79,1)-(83,23)
The type variables `v0', `w0' are ambiguous
When checking that `macroexpand2' has the inferred type
macroexpand2 :: forall (r :: [* -> *]) v (w :: [* -> *]).
(Data.Open.Union.Member'
(State [Scope v w])
r
(Data.Open.Union.FindElem (State [Scope v w]) r),
Data.Open.Union.Member'
(State (Global v w))
r
(Data.Open.Union.FindElem (State (Global v w)) r)) =>
Text -> Eff r Bool
Probable cause: the inferred type is ambiguous
好的，我可以给类型加一个Members注解：
macroexpand2 :: Members [State (Global v w), State [Scope v w]] r
=> Text -> Eff r Bool
现在我明白了：
Overlapping instances for Member (State [Scope v0 w0]) r
arising from a use of `findMacro'
Matching instances:
instance Data.Open.Union.Member'
t r (Data.Open.Union.FindElem t r) =>
Member t r
-- Defined in `Data.Open.Union'
There exists a (perhaps superclass) match:
from the context (Members
'[State (Global v w), State [Scope v w]] r)
bound by the type signature for
macroexpand2 :: Members
'[State (Global v w), State [Scope v w]] r =>
Text -> Eff r Bool
at /tmp/flycheck408QnV/Erlish.hs:(79,17)-(80,37)
(The choice depends on the instantiation of `r, v0, w0'
To pick the first instance above, use IncoherentInstances
when compiling the other instance declarations)
In a stmt of a 'do' block: m <- findMacro s
In the expression:
do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
In an equation for `macroexpand2':
macroexpand2 s
= do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
有人建议我在 irc 上尝试 forall r v w.，但没有任何区别。出于好奇，我在编译 this 代码时尝试使用 IncoherentInstances （我不喜欢检查 freer 和 playing 的分支）看看它是否会给我一个线索发生了什么事。它没有：
Could not deduce (Data.Open.Union.Member'
(State [Scope v0 w0])
r
(Data.Open.Union.FindElem (State [Scope v0 w0]) r))
arising from a use of `findMacro'
from the context (Members
'[State (Global v w), State [Scope v w]] r)
bound by the type signature for
macroexpand2 :: Members
'[State (Global v w), State [Scope v w]] r =>
Text -> Eff r Bool
at /tmp/flycheck408eru/Erlish.hs:(79,17)-(80,37)
The type variables `v0', `w0' are ambiguous
Relevant bindings include
macroexpand2 :: Text -> Eff r Bool
(bound at /tmp/flycheck408eru/Erlish.hs:81:1)
Note: there are several potential instances:
instance (r ~ (t' : r'), Data.Open.Union.Member' t r' n) =>
Data.Open.Union.Member' t r ('Data.Open.Union.S n)
-- Defined in `Data.Open.Union'
instance (r ~ (t : r')) =>
Data.Open.Union.Member' t r 'Data.Open.Union.Z
-- Defined in `Data.Open.Union'
In a stmt of a 'do' block: m <- findMacro s
In the expression:
do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
In an equation for `macroexpand2':
macroexpand2 s
= do { m <- findMacro s;
return
$ case m of {
Just j -> True
Nothing -> False } }
所以，这是我对 freer 内部结构的理解用完了，我有问题：
- 为什么会有重叠实例？我不明白这是从哪里来的。
- IncoherentInstances 实际上 做什么？自动选择听起来很可能导致难以调试的错误。
- 如何在另一个函数中实际使用 findMacro？
干杯！
可扩展效果的类型推断在历史上一直很糟糕。让我们看一些例子：
{-# language TypeApplications #-}
-- mtl
import qualified Control.Monad.State as M
-- freer
import qualified Control.Monad.Freer as F
import qualified Control.Monad.Freer.State as F
-- mtl works as usual
test1 = M.runState M.get 0
-- this doesn't check
test2 = F.run $ F.runState F.get 0
-- this doesn't check either, although we have a known
-- monomorphic state type
test3 = F.run $ F.runState F.get True
-- this finally checks
test4 = F.run $ F.runState (F.get @Bool) True
-- (the same without TypeApplication)
test5 = F.run $ F.runState (F.get :: F.Eff '[F.State Bool] Bool) True
我将尝试解释一般问题并提供最少的代码说明。代码的独立版本可以是 found here.
在最基本的层面上（忽略优化表示），Eff 定义如下：
{-# language
GADTs, DataKinds, TypeOperators, RankNTypes, ScopedTypeVariables,
TypeFamilies, DeriveFunctor, EmptyCase, TypeApplications,
UndecidableInstances, StandaloneDeriving, ConstraintKinds,
MultiParamTypeClasses, FlexibleInstances, FlexibleContexts,
AllowAmbiguousTypes, PolyKinds
#-}
import Control.Monad
data Union (fs :: [* -> *]) (a :: *) where
Here :: f a -> Union (f ': fs) a
There :: Union fs a -> Union (f ': fs) a
data Eff (fs :: [* -> *]) (a :: *) =
Pure a | Free (Union fs (Eff fs a))
deriving instance Functor (Union fs) => Functor (Eff fs)
换句话说，Eff 是一个来自函子列表联合的自由单子。 Union fs a 表现得像 n 进制 Coproduct。二进制 Coproduct 类似于 Either 两个仿函数：
data Coproduct f g a = InL (f a) | InR (g a)
相比之下，Union fs a 让我们从函子列表中选择一个函子：
type MyUnion = Union [[], Maybe, (,) Bool] Int
-- choose the first functor, which is []
myUnion1 :: MyUnion
myUnion1 = Here [0..10]
-- choose the second one, which is Maybe
myUnion2 :: MyUnion
myUnion2 = There (Here (Just 0))
-- choose the third one
myUnion3 :: MyUnion
myUnion3 = There (There (Here (False, 0)))
我们以实现State效果为例。首先，我们需要为 Union fs 提供一个 Functor 实例，因为如果 Functor (Union fs)，Eff 只有一个 Monad 实例。
Functor (Union '[]) 是微不足道的，因为空联合没有值：
instance Functor (Union '[]) where
fmap f fs = case fs of {} -- using EmptyCase
否则我们在联合前面添加一个函子：
instance (Functor f, Functor (Union fs)) => Functor (Union (f ': fs)) where
fmap f (Here fa) = Here (fmap f fa)
fmap f (There u) = There (fmap f u)
现在 State 定义和跑步者：
run :: Eff '[] a -> a
run (Pure a) = a
data State s k = Get (s -> k) | Put s k deriving Functor
runState :: forall s fs a. Functor (Union fs) => Eff (State s ': fs) a -> s -> Eff fs (a, s)
runState (Pure a) s = Pure (a, s)
runState (Free (Here (Get k))) s = runState (k s) s
runState (Free (Here (Put s' k))) s = runState k s'
runState (Free (There u)) s = Free (fmap (`runState` s) u)
我们已经可以开始编写和 运行 我们的 Eff 程序，尽管我们缺少所有的糖和便利：
action1 :: Eff '[State Int] Int
action1 =
Free $ Here $ Get $ \s ->
Free $ Here $ Put (s + 10) $
Pure s
-- multiple state
action2 :: Eff '[State Int, State Bool] ()
action2 =
Free $ Here $ Get $ \n -> -- pick the first effect
Free $ There $ Here $ Get $ \b -> -- pick the second effect
Free $ There $ Here $ Put (n < 10) $ -- the second again
Pure ()
现在：
> run $ runState action1 0
(0,10)
> run $ (`runState` False) $ (`runState` 0) action2
(((),0),True)
这里只缺少两个基本的东西。
第一个是 Eff 的 monad 实例，它让我们使用 do-notation 而不是 Free 和 Pure，也让我们使用许多多态单子函数。写起来简单，这里略过。
第二个 inference/overloading 用于从效果列表中选择效果。以前我们需要写 Here x 来选择第一个效果， There (Here x) 来选择第二个，依此类推。相反，我们想编写在效果列表中具有多态性的代码，因此我们所要做的就是指定一些效果是列表的一个元素，并且一些隐藏类型 class 魔法将插入适当数量的 There-s.
我们需要一个 Member f fs class 可以在 f 是 [=54= 的元素时将 f a-s 注入 Union fs a-s ].从历史上看，人们以两种方式实现它。
首先，直接用OverlappingInstances：
class Member (f :: * -> *) (fs :: [* -> *]) where
inj :: f a -> Union fs a
instance Member f (f ': fs) where
inj = Here
instance {-# overlaps #-} Member f fs => Member f (g ': fs) where
inj = There . inj
-- it works
injTest1 :: Union [[], Maybe, (,) Bool] Int
injTest1 = inj [0]
injTest2 :: Union [[], Maybe, (,) Bool] Int
injTest2 = inj (Just 0)
其次，间接地，通过首先用类型族计算 fs 中 f 的索引，然后用非重叠 class 实现 inj，引导通过 f-s 计算的索引。这通常被认为更好，因为人们往往不喜欢重叠实例。
data Nat = Z | S Nat
type family Lookup f fs where
Lookup f (f ': fs) = Z
Lookup f (g ': fs) = S (Lookup f fs)
class Member' (n :: Nat) (f :: * -> *) (fs :: [* -> *]) where
inj' :: f a -> Union fs a
instance fs ~ (f ': gs) => Member' Z f fs where
inj' = Here
instance (Member' n f gs, fs ~ (g ': gs)) => Member' (S n) f fs where
inj' = There . inj' @n
type Member f fs = Member' (Lookup f fs) f fs
inj :: forall fs f a. Member f fs => f a -> Union fs a
inj = inj' @(Lookup f fs)
-- yay
injTest1 :: Union [[], Maybe, (,) Bool] Int
injTest1 = inj [0]
freer 库使用第二种解决方案，而 extensible-effects 对于 7.8 之前的 GHC 版本使用第一种，对于较新的 GHC-s 使用第二种。
无论如何，这两种解决方案都具有相同的推理限制，即我们几乎总是 Lookup 只有具体的单态类型，而不是包含类型变量的类型。 ghci 中的示例：
> :kind! Lookup Maybe [Maybe, []]
Lookup Maybe [Maybe, []] :: Nat
= 'Z
之所以可行，是因为 Maybe 或 [Maybe, []] 中都没有类型变量。
> :kind! forall a. Lookup (Either a) [Either Int, Maybe]
forall a. Lookup (Either a) [Either Int, Maybe] :: Nat
= Lookup (Either a) '[Either Int, Maybe]
这个卡住了，因为 a 类型变量阻止了缩减。
> :kind! forall a. Lookup (Maybe a) '[Maybe a]
forall a. Lookup (Maybe a) '[Maybe a] :: Nat
= Z
这是可行的，因为我们对任意类型变量的唯一了解是它们等于它们自己，并且 a 等于 a。
一般来说，类型族缩减会卡在变量上，因为约束求解可能会在以后将它们细化为不同的类型，因此 GHC 不能对它们做出任何假设（除了与它们自己相等）。 OverlappingInstances 实现（尽管没有任何类型族）也出现了本质上相同的问题。
鉴于此，让我们重新审视freer。
import Control.Monad.Freer
import Control.Monad.Freer.State
test1 = run $ runState get 0 -- error
GHC 知道我们有一个只有单一效果的堆栈，因为 run 适用于 Eff '[] a。它还知道该效果必须是 State s。但是当我们写 get 时，GHC 只知道它对一些新的 t 变量有 State t 的影响，并且 Num t 必须成立，所以当它试图计算freer 相当于 Lookup (State t) '[State s]，它卡在类型变量上，任何进一步的实例解析都会在卡住的类型族表达式上绊倒。另一个例子：
foo = run $ runState get False -- error
这也失败了，因为 GHC 需要计算 Lookup (State s) '[State Bool]，虽然我们知道状态必须是 Bool，但由于 s 变量，这仍然会卡住。
foo = run $ runState (modify not) False -- this works
这是可行的，因为 modify not 的状态类型可以解析为 Bool，并且 Lookup (State Bool) '[State Bool] 减少。
现在，在绕了这么大的弯路之后，我将在 post.
末尾回答您的问题Overlapping instances并不表示任何可能的解决方案，只是一个类型错误工件。我需要更多的代码上下文来查明它究竟是如何产生的，但我确信它不相关，因为一旦Lookup卡住，情况就变得毫无希望了。IncoherentInstances也无关紧要，无济于事。我们需要一个具体的效果位置索引才能为程序生成代码，Lookup卡住不能凭空拉一个索引。findMacro的问题是它对状态内的类型变量有State影响。每当您想使用findMacro时，您必须确保Scope和Global的v和w参数是已知的具体类型。您可以通过类型注释来做到这一点，或者更方便地您可以使用TypeApplications，并写findMacro @Int @Int来指定v = Int和w = Int。如果在多态函数中有findMacro，则需要使用该函数的forall v w.注释启用ScopedTypeVariables、绑定v和w，并编写findMacro @v @w使用的时候。您还需要为多态v或w启用{-# language AllowAmbiguousTypes #-}（正如评论中指出的那样）。我认为尽管在 GHC 8 中它与TypeApplications一起启用是一个合理的扩展。
附录：
然而，幸运的是，新的 GHC 8 功能让我们修复了可扩展效果的类型推断，我们可以推断出 mtl 可以处理的一切，也可以推断出一些 mtl 无法处理的事情。新的类型推断对于效果的排序也是不变的。
我有一个 minimal implementation here 以及一些示例。然而，它还没有在我所知道的任何效果库中使用。我可能会写一篇关于它的文章，并提出拉取请求以便将其添加到 freer。