哪些 monad 可以在某些函子上表示为 Free? [英] What monads can be expressed as Free over some functor?

问题描述

免费 的文档说:

许多常见的 monad 都是作为自由 monad 出现的，

A number of common monads arise as free monads,

• 给定 data Empty a，Free Empty 与 Identity monad 同构.
• 免费的Maybe 可用于建模偏向性monad，其中每一层都代表运行一段时间的计算.

• 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.

还有哪些 monad 可以使用 Free 表达?

What other monads are expressible using Free?

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

I could think only of one more: I believe Free (Const e) is isomorphic to Either e.

哪些单子不能使用Free来表达，为什么?

What monads are not expressible using Free and why?

推荐答案

几乎所有(包括涉及循环和 mfix 的问题)，但不包括 Cont.

Almost all of them (up to issues involving looping and mfix) but not Cont.

考虑State monad

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

看起来任何都不像一个免费的monad...但是从你如何使用它

does not look anything like a free monad... but think about State in terms of how you use it

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

we can design a free monad with this interface by listing the operations as constructors

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 ())

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

and we just need a way to use it

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

您可以对大多数 monad 进行这种构造.就像maybe/partiality monad由

you can do this construction with most monads. Like the maybe/partiality monad is defined by

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

规则是，对于某些x，我们将每个以mx结尾的函数视为函子中的构造函数，而其他函数则是运行产生的自由单子.在这种情况下

the rule is, we treat each of the functions that end in m x for some x as a constructor in the functor, and the other functions are ways of running the resulting free monad. In this case

data StopF a = StopF deriving Functor

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

为什么这么酷?好几件事

why is this cool? Well a few things

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

1. The free monad gives you a piece of data that you can think of as being an AST for the monadic code. You can write functions that operate on this data which is really useful for DSLs
2. Functors compose, which means breaking down your monads like this makes them semi composeable. In particular, given two functors which share an algebra (an algebra is essentially just a function f a -> a for some a when f is a functor), the composition also has that algebra.

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

Functor composition is just We can combine functors in several ways, most of which preserve that algebra. In this case we want not the composition of functors (f (g (x))) but the functor coproduct. Functors add

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 也保存代数

also free monads preserve algebras

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

在 Wouter Swierstra 的著名论文 数据类型点菜 这用于效果很好.该论文中的一个简单示例是计算器.我们将在这篇文章中采用新的 monadic.鉴于代数

In Wouter Swierstra's famous paper Data Types A La Carte this is used to great effect. A simple example from that paper is the calculator. Which we will take a monadic take on new to this post. Given the algebra

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)

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

which might be totally useless, but I find very cool. It does let you define other things like

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

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

其余的都类似.

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

It is a useful design stategy: list the things you want your monad to do ==> define functors for each operation ==> figure out what some of its algebras should be ==> define those functors for each operation ==> make it fast.

让它变快很难，但我们有一些技巧.技巧 1 是将您的免费 monad 包装在 Codensity(更快的按钮")中，但是当这不起作用时，您想摆脱免费表示.还记得我们曾经

Making it fast is hard, but we have some tricks. Trick 1 is to just wrap your free monad in Codensity (the "go faster button") but when that doesn't work you want to get rid of the free representation. Remember when we had

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 所说的类型类态射来思考.你想要

well, this is a function from Free StateF a to s -> (a,s) just using the result type as our definition for state seems reasonable...but how do we define the operations? In this case, you know the answer, but one way of deriving it would be to think in terms of what Conal Elliott calls type class morphisms. You want

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)

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

which is pretty darn helpful. Deriving >>= in this way can be tough, and I won't include it here, but the others of these are exactly the definitions you would expect.

这篇关于哪些 monad 可以在某些函子上表示为 Free?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！