haskell - 哪些单子可以通过某个函子表示为 Free？

Question

的文档Free说：

许多常见的单子以自由单子的形式出现，

Given data Empty a,与monadFree Empty同构。Identity

FreeMaybe可用于对偏性 monad 建模，其中每一层代表运行计算一段时间。

还有哪些其他 monad 可以用来表达Free？

我只能再想到一个：我相信Free (Const e)与Either e.

编辑：哪些单子是不可表达的Free，为什么？

score 31 · Accepted Answer

几乎所有这些（直到涉及循环和的问题mfix）但不是Cont.

考虑State单子

newtype State s a = State (s -> (a,s))

看起来一点也不像一个免费的单子......但考虑一下State你如何使用它

get :: m s --or equivalently (s -> m a) -> m a
set :: s -> m () --or (s,m a) -> m a
runState :: m a -> s -> (a,s)

我们可以通过将操作列为构造函数来设计具有此接口的免费 monad

data StateF s a
  = Get (s -> a) | Set s a deriving Functor

那么我们有

type State s a = Free (StateF s) a

和

get = Impure (Get Pure)
set x = Impure (Set x (Pure ())

我们只需要一种使用它的方法

runState (Pure a) s = (a,s)
runState (Impure (Get f)) s = runState (f s) s
runState (Impure (Set s next)) _ = runState next s

你可以用大多数单子来做这个构造。就像可能/偏颇性单子由以下定义

stop :: m a
maybe :: b -> (a -> b) -> m a -> b

m x规则是，我们将每个以 some结尾的函数x视为函子中的构造函数，而其他函数是运行生成的自由 monad 的方式。在这种情况下

data StopF a = StopF deriving Functor

maybe _ f (Pure a)      = f a
maybe b _ (Impure Stop) = b

为什么这么酷？有几件事

免费的 monad 为您提供了一段数据，您可以将其视为 monadic 代码的 AST。您可以编写对这些数据进行操作的函数，这对 DSL 非常有用
Functors compose，这意味着像这样分解你的 monad 使它们成为半可组合的。特别是，给定两个共享一个代数的函子（一个代数本质上只是一个函数f a -> a，a当f它是一个函子时），组合也有那个代数。

~~函子组合只是~~我们可以通过多种方式组合函子，其中大多数都保留了该代数。在这种情况下，我们想要的不是函子的组合， (f (g (x)))而是函子 coproduct。函子添加

data f :+: g a = Inl (f a) | Inr (g a) 

instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap f (Inl x) = Inl (fmap f x)
  fmap f (Inr x) = Inr (fmap f x)

compAlg :: (f a -> a) -> (g a -> a) -> f :+: g a -> a
compAlg f _ (Inl x) = f x
compAlf _ g (Inr x) = g x

自由单子也保存代数

freeAlg :: (f a -> a) -> Free f a -> a
freeAlg _ (Pure a) = a
freeAlg f (Impure x) = f $ fmap (freeAlg f) x

在 Wouter Swierstra 的著名论文Data Types A La Carte中，这被用来取得很好的效果。该论文中的一个简单示例是计算器。我们将对这篇文章采取一元化的方式。给定代数

class Calculator f where
 eval :: f Integer -> Integer

我们可以想到各种实例

data Mult a = Mult a a deriving Functor
instance Calculator Mult where
  eval (Mult a b) = a*b

data Add a = Add a a deriving Functor
instance Calculator Add where
  eval (Add a b) = a+b

data Neg a = Neg a deriving Functor
instance Calculator Neg where
  eval (Neg a) = negate a

instance Calculator (Const Integer) where
  eval (Const a) = a

data Signum a = Signum a deriving Functor
instance Calculator Signum where
  eval (Signum a) = signum a

data Abs a = Abs a deriving Functor
instance Calculator Abs where
  eval (Abs a) = abs a

和最重要的

instance (Calculator f, Calculator g) => Calculator (f :+: g) where
   eval = compAlg eval

你可以定义数字单子

newtype Numerical a = Numerical (
        Free (Mult 
        :+: Add 
        :+: Neg 
        :+: Const Integer 
        :+: Signum
        :+: Abs) a deriving (Functor, Monad)

然后你可以定义

 instance Num (Numerical a)

这可能完全没用，但我觉得很酷。它确实可以让您定义其他内容，例如

 class Pretty f where
    pretty :: f String -> String

 instance Pretty Mult where
    pretty (Mult a b) = a ++ "*" ++ b

其余的都类似。

这是一个有用的设计策略：列出你想让你的 monad 做的事情 ==> 为每个操作定义函子 ==> 找出它的一些代数应该是什么 ==> 为每个操作定义那些函子 ==> 让它快速地。

让它变快很难，但我们有一些技巧。技巧 1 是把你的自由单子包裹起来Codensity（“更快的按钮”），但是当这不起作用时，你想摆脱自由表示。记得当我们有

runState (Pure a) s = (a,s)
runState (Impure (Get f)) s = runState (f s) s
runState (Impure (Set s next)) _ = runState next s

好吧，这是一个从结果类型Free StateF a到s -> (a,s)只使用结果类型的函数，因为我们对状态的定义似乎是合理的……但是我们如何定义操作呢？在这种情况下，您知道答案，但推导它的一种方法是根据 Conal Elliott 所谓的类型类态射进行思考。你要

runState (return a) = return a
runState (x >>= f) = (runState x) >>= (runState f)
runState (set x) = set x
runState get = get

这很容易

runState (return a) = (Pure a) = \s -> (a,s)

runState (set x) 
   = runState (Impure (Set x (Pure ()))) 
   = \_ -> runState (Pure ()) x
   = \_ -> (\s -> (a,s)) x
   = \_ -> (a,x)

runState get
  = runState (Impure (Get Pure))
  = \s -> runState (Pure s) s
  = \s -> (s,s)

这非常有帮助。以这种方式推导>>=可能很困难，我不会在此处包含它，但其中的其他定义正是您所期望的。

score 9 · Accepted Answer

要回答所说的问题，您在问题中没有提到的大多数熟悉的单子本身并不是自由单子。Philip JF 的回答暗示了如何将给定的 monad 与一个新的、自由的 monad 联系起来，但新的 monad 会“更大”：它比原来的 monad 具有更多不同的值。例如 real State smonad 满足get >>= put = return ()，但 free monadStateF不满足。作为一个自由单子，它不满足定义上的额外方程；这就是自由的概念。

我将证明Reader r,Writer w和State smonad 不是免费的，除非在r/ w/的特殊条件下s。

让我介绍一些术语。如果m是 monad，那么我们称任何类型m a的值为 ( m-) 动作。m如果一个 -action 等于return xfor some ，我们称它为平凡x；否则我们称它为非平凡的。

如果m = Free f是函子上的任何自由单子f，则m承认单子同态Maybe。这是因为Free它的参数是函子的，f而函子类别中的终端对象在Maybe = Free (Const ())哪里。Const ()具体来说，这个同态可以写成

toMaybe :: Free f a -> Maybe a
toMaybe (Pure a) = Just a
toMaybe (Impure _) = Nothing

因为toMaybe是 monad 同态，所以它特别满足toMaybe (v >> w) = toMaybe v >> toMaybe w任何m-actionv和w. 现在观察toMaybe将琐碎m的 -actions 发送到琐碎的Maybe-actions 和mnontrivial -actions 到 nontrivial Maybe-action Nothing。现在Maybe有这样的性质，即>>以任何顺序对任何动作进行非平凡动作，都会产生非平凡动作（Nothing >> w = v >> Nothing = Nothing）；所以对于也是如此m，因为toMaybe是一个保持（非）平凡的单子同态。

（如果您愿意，也可以直接从>>免费 monad 的公式中验证这一点。）

为了证明一个特定的 monadm不与任何自由 monad 同构，只需找到m-actionsv和w至少一个v和w不是平凡的而是v >> w平凡的。

Reader r满足v >> w = w，所以我们只需要选择w = return ()和任何非平凡的行动v，只要它r至少有两个值就存在（那么ask是非常量，即非平凡）。

对于Writer w，假设除了恒等元之外还有一个可逆元素k :: w。让它kinv :: w成为它的倒数。那么tell k >> tell kinv = return (), 但是tell k和tell kinv是不平凡的。任何非平凡群（例如加法下的整数）都有这样的元素k。我假设形式的自由单子Writer w只是那些幺半群w本身是自由的，即w = [a], Writer w ~ Free ((,) a)。

因为State s，类似地，如果允许任何具有逆的s非平凡自同构，则. 任何具有至少两个元素和可判定相等的类型都具有这样的自同构。f :: s -> sfinv :: s -> smodify f >> modify finv = return ()s

score 5 · Accepted Answer

根据 Reid 回答中的见解，我写了一个证明，证明 list monad 在发布到 haskell-cafe mailing list时不是免费的：

回想一下，对于任何函子 f，我们可以构造 f 上的自由单子：

data Free f a = Pure a | Roll (f (Free f a))

直观地说，Free fa 是具有 a 型叶子的 f 形树的类型。连接操作只是将树嫁接在一起，不执行任何进一步的计算。在这篇文章中，表单（Roll _）的值应称为“非平凡”。

一些常见的单子实际上是一些函子上的自由单子：

Tree monad 是 functor 上的自由 monad Pair，其中 data Pair a = MkPair a a. 在这个例子中，对形状树的直觉是最强烈的。每个父节点都有一对子节点。
Maybe monad 是函子上的自由 monad Unit，其中 data Unit a = MkUnit. 在图形图片父节点有一个 Unit孩子，所以根本没有孩子。所以正好有两棵 Unit- 形的树：仅由叶子组成的树（对应于Just _）和由无子父节点组成的三棵树（对应于Nothing）。
Identitymonad 是 functor 上的自由 monad ，Void其中Void a是没有构造函数的类型。
Partialitymonad 是 free monad Maybeover 。
Writer [r]monad 是 functor 上的自由monad (r,)。在(r,)- 形树中，父节点用 type 值装饰，r并且只有一个子节点。遍历这样的路径会产生一个r's 列表和一个 type 的叶值a，因此总共有一个 type 的值([r],a) = Writer r a。

（特别Free (r,) ()是同构于[r]。这个观察导致了列表单子是免费的。但这个声明是错误的，并且确实不是从观察中得出的。为了证明一个单子m 是免费的，一个人必须展示一个单子forall a. m a -> Free f a 某些函子的同构f。相比之下，展示 with 的同构m a既不 Free (f a) ()充分也不必需。）

更多的单子是自由单子的商。例如，State s是的商Free (StateF s)，其中

data StateF s a = Put s a | Get (s -> a).
-- NB: This functor is itself a free functor over a type constructor
-- which is sometimes called StateI [1], rendering Free (StateF s) what
-- Oleg and Hiromi Ishii call a "freer monad" [2].

商由以下单子态射展示，它为自由单子的纯句法值提供语义。

run :: Free (StateF s) a -> State s a
run (Pure x)         = return x
run (Roll (Put s m)) = put s >> run m
run (Roll (Get k))   = get >>= run . k

这种观点是 apfelmus [1] 的操作包的基础，也在 StackOverflow 线程 [3] 中讨论过。这是自由单子在编程环境中有用的主要原因。

那么，列表单子是免费单子吗？直观地说，它不是，因为 list monad（连接）的连接操作不仅将表达式嫁接在一起，而且将它们展平 [4]。

这是一个证明单子列表不是免费的。我正在记录它，因为我对证明感兴趣已经有一段时间了，但是搜索它并没有产生任何结果。不过，线程 [3] 和 [5] 很接近。

在任何函子上的自由单子中，将非平凡动作与任何函数绑定的结果总是非平凡的，即

(Roll _ >>= _) = Roll _

这可以直接从(>>=)自由单子的定义中检查，或者使用 Reid Barton 将单子态射利用到 Maybe 的技巧，请参阅 [3]。

如果列表 monad 在某个函子上与自由 monad 同构，则同构只会将单例列表映射[x]到表单的值，(Pure _)而将所有其他列表映射到非平凡值。这是因为 monad 同构必须与“return”通勤，并且return x 在[x]list monad 和Pure xfree monad 中。

这两个事实相互矛盾，如以下示例所示：

do
    b <- [False,True]  -- not of the form (return _)
    if b
        then return 47
        else []
-- The result is the singleton list [47], so of the form (return _).

在通过某个函子对自由单子应用假设的同构之后，我们会得到一个非平凡值（[False,True]同构下的图像）与某个函数的绑定会产生一个平凡值（的图像[47]，即return 47）。

干杯，英戈

[1] http://projects.haskell.org/operational/Documentation.html

[2] http://okmij.org/ftp/Haskell/extensible/more.pdf

[3]哪些单子可以通过某个函子表示为 Free？

[4] https://hackage.haskell.org/package/free-4.12.4/docs/Control-Monad-Free.html

[5] https://www.reddit.com/r/haskell/comments/50zvyb/why_is_liststate_not_a_free_monad/