haskell - 哪些单子(monad)可以通过某个仿函数表示为 Free？

Question

documentation for Free 说:

A number of common monads arise as free monads,

• Given data Empty a, Free Empty is isomorphic to the Identity monad.
• Free Maybe can be used to model a partiality monad where each layer represents running the computation for a while longer.

使用 Free 可以表达哪些其他 monad ?

我只能再想一个:我相信 Free (Const e)与 Either e 同构.

编辑:使用 Free 无法表达哪些单子(monad)为什么？

Answer 1

几乎所有(直到涉及循环和 mfix 的问题)但不是 Cont .

考虑 State单子(monad)

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

看起来一点也不像一个免费的单子(monad)......但想想 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)

我们可以通过将操作列为构造函数来设计具有此接口(interface)的免费 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

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

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

规则是，我们处理每个以 m x 结尾的函数。对于一些 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)))但仿函数副产品。仿函数添加

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

自由单子(monad)也保存代数

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

你可以定义数字单子(monad)

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 是将你的免费 monad 包装在 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)

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