什么是自由单子? [英] What are free monads?

问题描述

我看到Free Monad这个词弹出每个 现在 和 然后有一段时间，但每个人似乎只是使用/讨论它们而没有解释它们是什么.那么:什么是自由 monad?(我想说我熟悉 monad 和 Haskell 基础知识，但对范畴论只有非常粗略的了解.)

I've seen the term Free Monad pop up every now and then for some time, but everyone just seems to use/discuss them without giving an explanation of what they are. So: what are free monads? (I'd say I'm familiar with monads and the Haskell basics, but have only a very rough knowledge of category theory.)

推荐答案

Edward Kmett 的回答显然很棒.但是，这有点技术性.这是一个可能更容易理解的解释.

Edward Kmett's answer is obviously great. But, it is a bit technical. Here is a perhaps more accessible explanation.

自由 monad 只是将函子转换为 monad 的一般方法.也就是说，给定任何函子 f Free f 是一个 monad.这不会很有用，除非你得到一对函数

Free monads are just a general way of turning functors into monads. That is, given any functor f Free f is a monad. This would not be very useful, except you get a pair of functions

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

第一个让你进入"你的 monad，第二个让你摆脱"它.

the first of these lets you "get into" your monad, and the second one gives you a way to "get out" of it.

更一般地说，如果 X 是带有一些额外东西 P 的 Y，那么免费 X"是一种从 Y 到 X 而不获得任何额外东西的方式.

More generally, if X is a Y with some extra stuff P, then a "free X" is a a way of getting from a Y to an X without gaining anything extra.

示例:幺半群 (X) 是具有额外结构 (P) 的集合 (Y)，基本上表示它具有运算(您可以考虑加法)和一些恒等式(例如零).

Examples: a monoid (X) is a set (Y) with extra structure (P) that basically says it has an operation (you can think of addition) and some identity (like zero).

所以

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

现在，我们都知道列表

data [a] = [] | a : [a]

好吧，给定任何类型 t 我们知道 [t] 是一个幺半群

Well, given any type t we know that [t] is a monoid

instance Monoid [t] where
  mempty   = []
  mappend = (++)

因此列表是集合(或 Haskell 类型)上的自由幺半群".

and so lists are the "free monoid" over sets (or in Haskell types).

好的，所以免费 monad 是相同的想法.我们取一个函子，并返回一个 monad.事实上，由于 monads 可以看作是内函子范畴中的幺半群，列表的定义

Okay, so free monads are the same idea. We take a functor, and give back a monad. In fact, since monads can be seen as monoids in the category of endofunctors, the definition of a list

data [a] = [] | a : [a]

看起来很像自由单子的定义

looks a lot like the definition of free monads

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

并且 Monad 实例与列表的 Monoid 实例有相似之处

and the Monad instance has a similarity to the Monoid instance for lists

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

现在，我们得到了两个操作

now, we get our two operations

-- this is essentially the same as x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)

这篇关于什么是自由单子?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！