什么monad可以表达为一些functor的免费？ [英] What monads can be expressed as Free over some functor?

问题描述

免费 的文件说：

许多常见单子作为免费单子出现，

• 给定数据清空， Free Empty 同构于 Identity monad。 / code>可用于建模偏好monad，其中每个图层代表运行计算一段时间。

使用免费？

可以表达其他单子我可以再考虑一次：我相信 Free（Const e）同构于或者e 。

编辑： >

解决方案

几乎所有人（最多涉及循环的问题和 mfix ）但不是 Cont 。

考虑州 monad

  newtype State sa = State（s  - >（a，s））
  

看起来不像任何东西就像一个免费的monad ...但是根据 来考虑 State

  get :: ms  - 或等效（s  - > ma） - > m a 
 set :: s  - > m（） - 或（s，m a） - > m a 
 runState :: m a  - > s  - > （a，s）
  

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

  data StateF sa 
 = Get（s  - > a）设置派生Functor 
  

然后我们有

类型State sa = Free（StateF s）a 
  

  get =不纯（获得纯净）
集x =不纯（Set x（Pure（））
  

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

 runState（Pure a）s =（a，s）
 runState（Impure（Get f））s = runState（fs）s 
 runState（Set下一个））_ = runState next s 
  

偏好monad被定义为：

  stop :: ma 
 maybe :: b  - >（a  - > b ） - > ma  - > b 
  

规则是，我们将每个结束的函数在 mx 中，一些 x 作为函子的构造函数，其他函数是运行结果的自由单体的方法。在这种情况下

 数据StopF a = StopF派生Functor 
 
也许_f（Pure a）= fa 
也许b _（不纯中止）= b 
  

为什么这很酷？好几件事

1. 免费的monad为您提供了一段您可以认为是一个数据 AST代表单子代码。您可以编写对这些数据进行操作的函数，这对DSLs真的很有用。


2. 分数器组成，这意味着分解您的monads，这样可以使它们成为可分配的。特别是，给定两个共享一个代数的函数（对于一些 a fa - > a 当 f 是一个仿函数时），组成也有该代数。

函子的构成就是我们可以用几种方式组合函子，其中大部分都保存了代数。在这种情况下，我们不希望函数的构成 （f（g（x））），而是 functor coproduct 。 Functors add

  data f：+：g a = Inl（f a）| Inr（g a）
 
 instance（Functor f，Functor g）=> Functor（f：+：g）其中
 fmap f（Inl x）= Inl（fmap fx）
 fmap f（Inr x）= Inr（fmap fx）
 
 compAlg ::（fa  - > a） - > （g a  - > a） - > f：+：g a  - > a 
 compAlg f _（Inl x）= fx 
 compAlf _ g（Inr x）= gx 
  

也免费单子保存代数

  freeAlg ::（fa  - > a） - >免费f a  - > a 
 freeAlg _（Pure a）= a 
 freeAlg f（Impure x）= f $ fmap（freeAlg f）x 
  

在Wouter Swierstra的着名论文数据类型单点菜单这很有用。该文件的一个简单例子就是计算器。我们将采取monadic采取新的这篇文章。给定代数

  class Calculator f其中
 eval :: f Integer  - >整数
  

我们可以考虑各种实例

  data Mult a = Mult aa派生Functor 
实例Calculator Mult其中
 eval（Mult ab）= a * b 
 
 data添加a =添加aa派生函数
实例计算器添加其中
 eval（Add ab）= a + b 
 
 data Neg a = Neg a派生函子
实例Calculator Neg where 
 eval（Neg a）=否定
 
实例Calculator（Const Integer）其中
 eval（Const a）= a 
 
 data Signum a = Signum a派生函子
实例Calculator Signum其中
 eval（Signum a）= signum a 
 
数据Abs a = Abs a派生Functor 
实例计算器Abs其中
 eval（Abs a）= abs a 
  

和最重要的

  instance（Calculator f，Calculator g）=>计算器（f：+：g）其中
 eval = compAlg eval 
  

您可以定义数字monad

  newtype数字a =数字（
 Free（Mult 
 ：+：添加
：+：Neg 
：+：Const整数
：+：Signum 
：+：Abs）a派生（Functor，Monad）
  

然后您可以定义

  instance Num（Numerical a）
  

这可能完全没用，但我觉得很酷。它确实可以让你定义其​​他的东西，例如：

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

实例Pretty Mult其中
pretty（Mult ab）= a ++*++ b


以及其他所有元素类似。

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

使它快速很难，但我们有一些技巧。窍门1就是将你的免费monad包装在 Codensity （更快的按钮）中，但是当这不起作用时，你想摆脱自由表示。请记住，当我们有

  runState（Pure a）s =（a，s）
 runState（Impure（Get f ））s = runState（fs）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）
  

这非常有帮助。以这种方式推导>> = 会很困难，我不会在这里包括它，但其他的恰好是您期望的定义。 p>

The documentation for Free says:

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.

What other monads are expressible using Free?

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

Edit: What monads are not expressible using Free and why?

解决方案

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

Consider the State monad

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

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)

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

then we have

type State s a = Free (StateF s) a

with

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

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

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

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

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

we can think of various instances

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

and the most important

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

you can define the numeric monad

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

and you can then define

 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

and similar for all the rest of them.

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.

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

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

which makes it pretty easy

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可以表达为一些functor的免费？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！