Dav*_*vid 357 monads haskell free-monad
我见过的长期免费单子弹出每一个 现在 和 随后一段时间,但每个人似乎只是使用/讨论这些问题没有给予它们是什么解释.所以:什么是免费的monads？(我会说我熟悉monad和Haskell的基础知识,但对类别理论只有非常粗略的了解.)
Joh*_*ley 401
这里有一个更简单的答案:Monad是在monadic context崩溃时"计算"的东西join :: m (m a) -> m a(回想起>>=可以定义为x >>= y = join (fmap y x)).这就是Monads如何通过顺序计算链来传递上下文:因为在序列中的每个点,前一个调用的上下文都会与下一个调用一起折叠.
一个免费的monad满足所有Monad定律,但不做任何崩溃(即计算).它只是构建了一系列嵌套的上下文.创建这样一个自由monadic值的用户负责使用那些嵌套的上下文做某事,这样这个组合的含义可以推迟到创建monadic值之后.
Phi*_* JF 279
Edward Kmett的回答显然很棒.但是,它有点技术性.这是一个可能更容易理解的解释.
免费monad只是将仿函数转换为monad的一般方法.也就是说,鉴于任何仿函数f Free f都是monad.除非你得到一对函数,否则这不会很有用
liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r
第一个让你"进入"你的monad,第二个给你一个"走出去"它的方法.
更一般地说,如果X是带有一些额外东西P的Y,那么"自由X"是从Y到X而不获得额外任何东西的一种方式.
示例:monoid(X)是具有额外结构(P)的集合(Y),基本上表示它具有操作(您可以想到添加)和一些身份(如零).
所以
class Monoid m where
mempty :: m
mappend :: m -> m -> m
现在,我们都知道列表
data [a] = [] | a : [a]
好吧,鉴于任何类型,t我们知道这[t]是一个幺半群
instance Monoid [t] where
mempty = []
mappend = (++)
所以列表是集合(或Haskell类型)中的"免费幺半群".
好吧,所以免费的monad是一样的想法.我们带一个仿函数,然后给一个monad.事实上,由于monads可以被视为endofunctors类别中的monoids,因此定义了一个列表
data [a] = [] | a : [a]
看起来很像免费monads的定义
data Free f a = Pure a | Roll (f (Free f a))
并且实例与列表的Monad实例具有相似性Monoid
--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
现在,我们得到了两个操作
-- 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)
Edw*_*ETT 136
一个免费的foo恰好是满足所有'foo'定律的最简单的东西.也就是说它完全满足成为foo所必需的法则,而不是额外的.
一个健忘的仿函数是一个"忘记"结构的一部分,因为它从一个类别到另一个类别.
给定仿函数F : D -> C,并且G : C -> D,我们说F -| G,只要forall a,b:是同构的,其中箭头来自适当的类别,它们F是伴随的G,或者G是伴随的.FF a -> ba -> G b
在形式上,一个自由的仿函数与一个健忘的仿函数相伴.
自由幺半群
让我们从一个更简单的例子开始,即免费的幺半群.
取一个由一些载体集定义的monoid,T一个将一对元素混合在一起的二元函数f :: T ? T ? T,以及a unit :: T,使得你有一个关联定律和一个身份定律:f(unit,x) = x = f(x,unit).
你可以U从幺半群的类别(其中箭头是monoid homomorphisms,也就是说,它们确保它们映射unit到unit另一个monoid上,并且你可以在映射到另一个monoid之前或之后编写而不改变含义)构成一个仿函数到类别套件(箭头只是功能箭头)"忘记"操作unit,并且只给你载体集.
然后,您可以将一个仿函数F从集合类别定义回与该仿函数相邻的一元组类别.该仿函数是将一组映射a到monoid的仿函数[a],其中unit = []和mappend = (++).
那么到目前为止,回顾我们的例子,在伪Haskell中:
U : Mon ? Set -- is our forgetful functor
U (a,mappend,mempty) = a
F : Set ? Mon -- is our free functor
F a = ([a],(++),[])
然后展示F是免费的,需要证明它是伴随的U,一个健忘的仿函数,也就是说,正如我们上面提到的,我们需要证明
F a ? b 是同构的 a ? U b
现在,记住目标F是Mon幺半群的类别,其中箭头是幺半群同态,所以我们需要一个来证明一个幺半群同态[a] ? b可以用一个函数来精确描述a ? b.
在Haskell中,我们称之为存在于Set(呃,Hask我们假装设置的Haskell类型的类别)的一方,只是foldMap,当专门从Data.FoldableLists类型Monoid m => (a ? m) ? [a] ? m.
这是一个附带的后果.值得注意的是,如果你忘记然后自由积累,那么再次忘记,它就像你忘了一次,我们可以用它来建立monadic连接.由于UFUF〜U(FUF)〜UF,我们可以在身份幺同态,从传递[a]到[a]通过定义我们的红利同构,获取从列表同构[a] ? [a]是类型的函数a -> [a],而这仅仅是返回列表.
您可以通过使用以下术语描述列表来直接撰写所有这些内容:
newtype List a = List (forall b. Monoid b => (a -> b) -> b)
免费Monad
什么是免费Monad？
好吧,我们做了我们之前做过的同样的事情,我们从一个健忘的仿函数U开始,从monad类别中箭头是monad同态到一类endofunctors,其中箭头是自然变换,我们寻找一个左边伴随的仿函数那个.
那么,这与通常使用的免费monad的概念有什么关系呢？
知道某个东西是一个自由的monad,Free f告诉你给出一个monad同态Free f -> m,与给出一个自然变换(一个仿函数同态)是一样的(同构的)f -> m.记住F a -> b必须是同构的,a -> U b因为F要与U同伴.这里将monad映射到仿函数.
F至少与Free我free在hackage包中使用的类型同构.
我们还可以通过定义来构建它,以类似于上面的代码为自由列表
class Algebra f x where
phi :: f x -> x
newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)
Cofree Comonads
我们可以构造类似的东西,通过查看正确的伴随假定它存在的健忘函子.一个cofree仿函数简单地/正确地伴随着一个健忘的仿函数,并且通过对称性,知道一些cofree comonad就像知道给出一个comonad homomorphism与w -> Cofree f给出一个自然变换一样w -> f.
com*_*nad 65
Free Monad(数据结构)是Monad(类),类似于List(数据结构)到Monoid(类):这是一个简单的实现,您可以在其中决定如何组合内容.
你可能知道Monad是什么,每个Monad需要一个特定的(Monad-law持久)实现fmap+ join+ return或bind+ return.
我们假设您有一个Functor(一个实现fmap),但其余的依赖于在运行时所做的值和选择,这意味着您希望能够使用Monad属性但是之后想要选择Monad函数.
这可以使用Free Monad(数据结构)来完成,它以这样的方式包装Functor(类型),这样join那些函数的堆叠比减少更多.
真实return和join你想要使用,现在可以作为减少函数的参数给出foldFree:
foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a
为了解释的类型,我们可以更换Functor f使用Monad m,并b用(m a):
foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)
Gab*_*lez 56
Haskell免费monad是一个仿函数列表.相比:
data List a = Nil | Cons a (List a )
data Free f r = Pure r | Free (f (Free f r))
Pure类似于Nil并且Free类似于Cons.免费monad存储一个函子列表而不是值列表.从技术上讲,您可以使用不同的数据类型实现免费monad,但任何实现都应该与上面的实现同构.
只要需要抽象语法树,就可以使用免费的monad.free monad的基础仿函数是语法树每一步的形状.
我的帖子,有人已经链接,提供了几个如何使用免费monad构建抽象语法树的示例
Tom*_*lis 21
我认为一个简单的具体例子会有所帮助.假设我们有一个仿函数
data F a = One a | Two a a | Two' a a | Three Int a a a
显而易见的fmap.然后Free F a是树木,叶子有型的类型a,其节点标记One,Two,Two'和Three. One-nodes有一个子节点,Two而Two'-nodes有两个子Three节点,-nodes有三个子节点,并且还标有一个子节点Int.
Free F是一个单子. return映射x到只是具有值的叶子的树x. t >>= f查看每个叶子并用树替换它们.当叶子有值时,y它用树替换该叶子f y.
图表使这更清楚,但我没有轻松绘制一个的设施!
尝试在此处的超级简单答案和完整答案之间提供 \xe2\x80\x9cbridge\xe2\x80\x9d 答案。
\n所以 \xe2\x80\x9cfree monads\xe2\x80\x9d 从任何 \xe2\x80\x9cfunctor\xe2\x80\x9d 构建一个 \xe2\x80\x9cmonad\xe2\x80\x9d ，所以让 \xe2\x80 \x99s 按顺序排列这些。
\n有些东西是类型级形容词，这意味着它们采用像 \xe2\x80\x9cintegers\xe2\x80\x9d 这样的类型名词，并给你一个不同的类型名词，如 \xe2\x80\x9clists of integers\xe2\x80 \x9d 或 \xe2\x80\x9c 带有整数的字符串对\xe2\x80\x9d 甚至 \xe2\x80\x9c 用整数生成字符串的函数。\xe2\x80\x9d 为了表示任意形容词，让我使用标准 -在单词\xe2\x80\x9cblue\xe2\x80\x9d中。
\n但随后我们注意到一种模式，其中一些形容词在它们修饰的名词中是输入型或输出型。例如， \xe2\x80\x9c 函数从 __\xe2\x80\x9d 生成字符串是类似输入的， \xe2\x80\x9c 函数将字符串转换为 __\xe2\x80\x9d 是类似输出的。这里的规则涉及我有一个函数X \xe2\x86\x92 Y，一些形容词 \xe2\x80\x9cblue\xe2\x80\x9d is outputtish ，或者 functor ，如果我可以使用这样的函数来转换蓝色X变成蓝色Y。想想 \xe2\x80\x9ca 消防水带喷射X s\xe2\x80\x9d，然后你拧上这个X \xe2\x86\x92 Y函数，现在你的消防水带喷射Y s。或者，如果相反，则它是输入性的或逆变的，真空吸尘器吸起Y s，当我拧上它时，我得到一个吸尘器吸起X s。有些东西既不是输出也不是输入。事实证明，两者都是幻影：它们与它们描述的名词完全无关，从某种意义上说，您可以定义一个函数 \xe2\x80\x9ccoerce\xe2\x80\x9d ，它接受一个蓝色的X和制作一个蓝色的Y ，但是*在不知道类型X或Y的详细信息的情况下，\xe2\x80\x9d 甚至不需要它们之间的函数。
\n因此 __\xe2\x80\x9d 的 \xe2\x80\x9clists 是输出性的，您可以将X \xe2\x86\x92 Y映射到X列表上以获得Y列表。类似地， \xe2\x80\x9ca 一对字符串和 __\xe2\x80\x9d 是输出性的。同时 \xe2\x80\x9ca 从 __ 到自身的函数 \xe2\x80\x9d 既不是输出也不是输入，\xe2\x80\x9d 而 \xe2\x80\x9ca 字符串和正好为零的 __s\xe2\x80\ 列表x9d 可能是 \xe2\x80\x9cphantom\xe2\x80\x9d 情况。
\n但是，是的，这就是编程中函子的全部内容，它们只是可映射的东西。如果某个东西是一个函子，那么它就是一个独特的函子，那么最多只有一种方法可以将函数一般地映射到数据结构上。
\n一个monad是一个函子，此外它还是
\n所以这意味着有一个规范函数将任何 blue -blue __ 折叠为 blue __。（当然，我们添加法则来使一切变得理智：如果其中一层蓝色来自通用应用程序，那么我们只想删除该通用应用程序；此外，如果我们将蓝-蓝-蓝 X 扁平化为蓝色 X，无论我们先折叠前两个蓝色还是先折叠后两个，应该没有什么区别。）
\n第一个示例是 \xe2\x80\x9ca 可空 __\xe2\x80\x9d。因此，如果我给你一个可空的整数，从某种意义上说，我给你的只是一个可空的整数。或者 \xe2\x80\x9ca 整数列表列表，\xe2\x80\x9d 如果点只是有 0 个或多个整数，那么 \xe2\x80\x9ca 整数列表 \xe2\x80\x9d 就可以工作很好，正确的折叠是将所有列表连接在一起形成一个超级列表。
\nMonads 在 Haskell 中变得很重要，因为 Haskell 需要一种方法来在现实世界中做事，而不违反其数学上纯粹的世界，在这个世界上什么也没有发生。解决方案是添加一种淡化形式的元编程，其中我们引入 \xe2\x80\x9ca 程序的形容词，该程序生成 __.\xe2\x80\x9d 那么我如何获取当前日期？好吧，Haskell 不能直接做到这一点unsafePerformIO，但它可以让你描述和编写生成当前日期的程序。在这个愿景中，您应该描述一个不生成任何名为 \xe2\x80\x9cMain.main,\xe2\x80\x9d 的程序，并且编译器应该接受您的描述并将该程序作为二进制可执行文件交给您随时随地跑步。
无论如何，生成一个 int\xe2\x80\x9d 的程序的 \xe2\x80\x9ca 程序并不会比生成一个 int\xe2\x80\x9d 的 \xe2\x80\x9ca 程序买得更多，所以事实证明成为一个单子。
\n与函子不同，单子并不是唯一的单子。对于给定的函子来说，不只有一个 monad 实例。例如 \xe2\x80\x9ca 一对 int 和 __\xe2\x80\x9d，你用这个 int 做什么？你可以加它，你可以乘它。如果将其设为可空 int，则可以保留最小非空值或最大非空值，或者最左边的非空值或最右边的非空值。
\n给定函子的自由单子是“最无聊的 \xe2\x80\x9d 构造，它只是 \xe2\x80\x9cA 自由蓝色X是任何n = 0, 1, 2, ...\ xe2\x80\x9d。
\n它是通用的，因为 blue\xe2\x81\xb0 X只是一个X。自由蓝自由蓝X是蓝色m蓝n X，它只是蓝色m + n X。它实现了 \xe2\x80\x9ccollapse\xe2\x80\x9d 因此根本不实现折叠，内部蓝色是任意嵌套的。
\n这也意味着您可以准确地将您选择的 monad 推迟到稍后的日期，稍后您可以定义一个函数，将blue -blue X减少为 blue X并将所有这些折叠为 blue 0,1 X，然后从另一个函数X到蓝色X给你蓝色1 X。
\n| 归档时间： |
|
| 查看次数： |
48062 次 |
| 最近记录： |