没有合适的资源?快使用搜索试试~ 我知道了~
自由单子与单子逼近的近似分布律
−→可在www.sciencedirect.com在线获取理论计算机科学电子笔记341(2018)277-295www.elsevier.com/locate/entcs近似分布律Ernie Manes1美国马萨诸塞大学阿默斯特分校数学与统计系菲尔·穆利2美国纽约州汉密尔顿市高露洁大学计算机科学系摘要Monad及其组合有时可以从更简单的数据类型生成,而不需要任何Monad公理。自由单子和单子近似提供了两种方法来克服单子组合律所需的约束,同时产生近分布律。关键词:单子复合,自由单子,单子逼近,近似分配律。1介绍本文继续了文[10]、[11]中关于单子合成的研究。我们将使用与第二篇论文中相同的符号我们在第五类中工作。在编程语言中使用monad时,有两个问题:使用程序员可用的数据类型定义monad可能很困难,并且可能很难验证monad公理。第二种情况在单子合成中很常见。给定单子(H,μ,η)和K,ν,ρ),它们的合成应该有形式(KH,τ,ρη)。问题是没有明显的τ。解决方案是提供一个自然变换λ:HK→KH,它允许τ被定义为τ=KHKHK−−λ→HKKHνμ KH1电子邮件:egmanes@gmail.com2电子邮件:pmulry@colgate.eduhttps://doi.org/10.1016/j.entcs.2018.11.0141571-0661/© 2018作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。278E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277→^[3]发现了关于λ等价于将(KH,τ,ρη)表示为单子的公理如下。HHρ)HK\( HνHKK\\(DL A)\λ(DLB)vλKKHK\ρH\\vvKλ\\KH(KKHνHKηK)HK\( μKHHK\\(DL C)\λ(DLD)vHλHKH\Kη \vvλH\\KH(KHHKμ公理(DL C,DL D)成立当且仅当K提升通过H的Eilenberg-Moore代数的范畴VH,并且我们说λ在这种情况下是近分配律实际上,这样的公理给程序员带来了障碍。我们回顾[4,第34页]:“函数式编程中的所有多态函数都是自然变换”。因此,公理是自然性的障碍,而不是自然性的要求在本文中,我们提出了两种方法来绕过障碍,并在这个过程中,发现各种接近分布律。 在第一种情况下,我们考虑内函子H,K和任意自然变换λ:HK KH,其中λ上没有公理。若H生成一个自由单子H@,则λ诱导一个近似分配律λ@:H@K→KH@,且λ生成λ@。我们详细考虑了近分配法律的一个共同的一类自由单子,即代数签名所产生的一种不同的方法是将V中的前单子的概念定义为(H,η,μ),其中H:V →V是内函子,μ:HH→H,η:id→H是自然变换,没有进一步的公理。前单子保留了惊人数量的结构。类似于生成一个自由单子的性质,我们将看到一个前单子H通常有一个单子近似H。 我们证明了,如果(K,m,e)是一个预单子,那么一个近分配律λ:HK → KH诱导一个近分配律λ:HK → KH,其中λ^:H^K→KH^。E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277279V → V我−→−→我−→我我我我2自由单子我们最宽松的单子模型是函子H:。在标准情况下,存在由H生成的自由单子(H@,μ,η;i),其中H@=(H@,μ,η)是V中的单子,并且i:H→H@是自然变换,服从普适性质[2]。Hi )H@\\(H@,μ,η)α\β\\vKψv(K,ν,ρ)如果(K,ν,ρ)是V中的单子且α:H→K是自然变换,则存在唯一的单子映射<$i,如图<$i =α所示。例2.1假设V有有限次幂。对有限序数i≥ 1,设Hi:V → V是函子HiX= Xi,即通常的i元幂函子. 当V = Set时,数据类型H@X是所有树的集合,其中每个节点要么是X的元素,记为Lix(如果它是叶子),要么在它下面有i个子树,记为Bit1···ti∈ H@X。 自然变换ηX:X → H@X将x映射到Lix而μX:H@H@X→H@映射Lit到t和Bit1. ti到Bi(μXt1). (μXti)。在下文中,我们只考虑H@存在的H定义2.2H-代数是一对(X,δ),其中δ:HX→X在V中。 一个H-代数的H-同态f:(X,δ)→(Y,δ)必满足HXHf)HYδϵV VX)YF证明了idX:(X,δ)→(X,δ)是H-同态,并且H-同态在复合下是闭的.这就产生了一个H-代数的范畴VH,其基础函子为VH→ V。定理2.3[2]若VH→V是单子的,则VH在V上同构于Eilenberg-Moore代数范畴VH@,其中H@是由H生成的自由单子。 同构Φ:VH@→VH由下式给出:Φ(X,H@X<$X)=(X,HXiX H@XX)3功能提升定义3.1设H=(H,μ,η)是V中的单子,设K:V → V是函子。函子K:VH→ VH是K通过Eilenberg-Moore范畴VH的函子提升,如果下列平方交换:280E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277−−−−→=HKXX HKHXX−→公司简介−−−−→X−−−−→HK)HV Vv) vVKV下面的结果是由于[1]。 见[7]。定理3.2设H=(H,μ,η)是V中的单子,K:V → V是函子,函子提升K∈:VH →VH与满足(DL C)和(DL D)的自然变换λ:HK → KH是双射对应的.对应关系是(一)和K(X,)=(KX,HKXλXKKHX−→KX)(2)λXHKη−−−−→ω−−−−→ KHX其中K∈(HX,μX)=(KHX,HKHXωXKHX)。此外,本发明还(三)ω=HKHXλHXKμ−−−−→ KHX直接证明λX:(HKX,μKX)→K(HX,μX)是H-同态;同态图恰好是(DLD)。它遵循(使用(DL C))λX是Kη的唯一同态扩张。然而,有不止一个可能的λ,因为K∈(HX,μX)有不止一个可能的K-代数结构。定义3.3设H:V → V生成自由单子H@,设K:V → V是函子。设K∈:VH@→VH@是K的函子提升,其分类自然变换λ@:H@K→KH@如定理3.2所示. 我们说K是一个λ at函子提升,如果存在一个自然变换λ:HK→KH使得下列平方交换。HK(K)H@Kλλ@(3. 第三章V V)的方式KHK iKH@然后我们说λ生成K,或λ生成λ@,当K是单子时,λ@是在接近分配律处的一个。定理3.4给定H,K:V → V,使得H@存在,每个自然变换λ:HK→KH生成K通过H@的一次函子提升。证据 给定λ,定义K:VH→ VHoverV,K†(X,δ)=(KX,HKXλXKHX−−K−−δ→KX)E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277281n−−−−→若f:(X,δ)→(Y,δ)是H-同态,则图λX)Kδ)HKX KHX KXHKFvKfV V)的情况)HKYλYKHYKKY证明了Kf:K<$(X,δ)→K<$(Y,δ)又是一个H-同态。在定理2.3的注释中,我们有函子提升K=H@ΦHK†HΦ−1H@V−→ V−→ V−→ V我们把剩下的细节留给读者。Q推论3.5给定H,K:V → V,其中K是单子,H@存在,则每个自然变换λ:HK →KH在接近分配律λ@:H@K→ KH@处生成一个子。4自由单子4.1通过类属预强的近似分布律在[11]和[12]中定义并使用了范畴的内函子F上的预强度概念,作为处理Kleisli强度过 程 的 一 部 分 。 对 于 固 定 n≥1 , 函 子 F 上 的 n 阶 预 强 是 自 然 变 换 Γn :FX1×· ··×FXn→F(X1×· ··×Xn)。我们立即注意到函子F上的n阶预强的一个特殊情况是自然变换Γ n:HnF→FHn,其中Hn是例2.1的n元幂函子。我们利用什么可以适当地称为单子诱导的通用prestrength的存在,以获得类附近的分配律的自由单子H@。稍后,在4.3节中,我们将确定另一种非一般类型的预强,这些预强又产生不同的近似分布律。引理4.1对于集合中的任意单子K=(K,ν,ρ),存在一个类属预强In:KX1×. KXn→ K(X1×... Xn)的阶数n ≥ 1。证据设K=(K,ν,ρ)是集合中的单子.本文证明了对任意给定的n≥ 1,存在一个自然变换Γ n:KX1×... KXn→K(X1×... Xn)。假设存在两个变量公司简介K(X×Y)则对于n=1,定义Γ1 =idX1,对于n=2,设Γ2 = ΓX X. 程序1 2归纳地说,如果Γi是自然的,我们得到一个自然变换Γi+1,idX1×ΓiΓX1(X2. ×Xi+1)KX1×(KX2)×KXi+1)−→KX1×K(X2. ×Xi+1)−−→K(X1×X2. ×Xi+1)为了构造Γ2,对于x∈X,令inx:Y→X×Y定义为inx(y)=(x,y)。是282E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277X YXY我δ×·显然,对于每个f,下面的平方交换:X→X1,g:Y→Y1:Y在x中G v)X×Yf×gY1)在外汇vX1×Y1定义δXY:X×KY→K(X×Y)通过δXY(x,τ)=(Kinx)τ。从前面的平方和函数性K,我们得到X×KYf×KgδXY )K(X×Y)K(f×g)vX1×KY1v)K(X1Y1)1 1在这个阶段,我们需要K是单子。任何从X到K-代数的函数都有唯一的自由代数(KX,μX)的K-同态扩张f#定义所需的ΓXY :KX×KY→K(X×Y),其中ΓXY(σ,τ)=δXY(·, τ)#σ。THE期望的自然性平方等于(δ (, τ))#KXKF)K(X×Y)K(f×g)V V)的方式KX1(δX1Y1(·,(Kf)τ))#K(X1×Y1)对于每个τ∈KY。由于这个正方形中的四个映射中的每一个都是一个K-同态,所以它可以检查限制在生成元ρ X上的交换性,这在δ XY的正方形中是清楚的。 就在上面。Q4.2顺从单子我们不知道任何非平凡的单子,它承认分配律与每个单子。这就限制了分配律在程序设计中的应用。我们认为,而不是单子承认近分配律与每一个单子,呼吁这些顺从,并提供例子。定义4.2V中的单子H是顺从的,如果对于V中的每个单子K,K有一个通过VH的函子提升。命题4.3例2.1中的单子H@是可修改的。证据 设K =(K,ν,ρ)是集合中的单子. 根据引理4.1,对于任意i≥1,存在E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277283一般的自然变换Γi:HiK→KHi,因此根据推论3.5,我们完成了。Q284E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)2772∗→2JJHJΣ我ΣJJ我例4.4设(C,e,n)是么半群,K是读者么半群KX = C ×X。 则命题4.3中的λ=Γ 2:H2KKH2变为Γ 2((c1,x1),(c2,x2))=(c1c2,(x1,x2))。 作用在H@ KX型二叉树t上,λ@(t)=(p,t)其中p是在叶子中找到的c i s的乘积,t是H@X中仅由X的元素组成的对应树。例4.5当K本身是形式为H@的自由单子时,我们可以给出一个递归的K=H的函子提升的构造@至集合i近的定义分配律λ:H@H@→ H@H@。细节直截了当,阅读(参见示例2.1的注释)。对于i,j≥1:λ(LiLja)=LjLiaλLi(Bjt1···tj)=Bj(λLit1)···(λLitj)λBi(t1···ti)=(H@Bi)Γi((λt1),···,(λti))命题4.6设V有小的余积,设(Hα)是一个小的内函子族,H = Hα是点态余积. 假设自由单子H@,H@存在。如果每个H@都顺从,那么H @也顺从。α α证据 一个H-代数由一个族(δα:HαX→X)决定. 设K是一个单子inV且令(X,HαX−δ→α X)<$→(KX,HαKX−<$α→X)在函子下K通过VHα的升力。 其余的细节都很清楚。Q例4.7设n是一个无穷算子定义域,即一个(可能为空)集合的不交序列(n)。一个λ-代数(如泛代数中的传统定义)是(X,δ),其中X是一个集合,δ =(δσ:σ∈ λ),δσ:Xn→X,如果σ∈n。考虑余积函子H=Xnσ∈n所以H-代数和H-代数是一样的从集合H_∞出发,通过引入方程,得到了各种泛代数H@X是由X生成的通常的自由n-代数。这是直接从命题4.3 4.6证明了H@是集合中的顺从单子。4.3预强与平坦近似分布律在这一节中,我们考虑一类不同的近似分配律,它们一般不同于前一节中的那些引理4.8对集合中的任意单子K =(K,ν,ρ),若存在自然变换γ:K→id,则存在预强Γ i:KA1×... ×KAi→K(A1×... ×Ai),对任意i≥ 1。证据构造很简单:对i= 1,定义Γ1 =ρ<$γ。如果i≥ 2,则Γ i= ρε(γ×.. .×γ)。因为在每种情况下,Γi都是自然变换的合成,所以我们完成了QE. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277285我J我我J我J我我JJ我命题4.9对任意具有自然变换γ的单子K=(K,ν,ρK→ id,在分配律λ@附近存在一个解:H@K → KH@。证据 对于任意i ≥ 1,前一引理的预强Γ i生成一个自然变换HiK → KHi,因此结果直接由推论得出三点五Q例4.10对于j ≥ 1,设πj表示第j个投影自然变换Hj→id,根据前面的命题,这就产生了一个近似分布律λ@:H@H@→H@H@,它一般不同于例4.5中的分布律。例4.11设K为例4.4中的读素单子,其幺半群为(C,e,)。定义γ:K → id由γ(c,a)= a。 这样的γ是自然的,生成Γ n:KA1×. KAn→K(A1×... An)。 对于非空列表L的单子,在分配l awλ@:L(C×A)→C×LAtakes[(c1,a1),.(cn,ann)]到(e,[a1,. an])。4.4一致分枝树与非线性近似分配律。对于自由单子H@,H@X由树组成,其中每个非叶都有i我我树枝由于其特殊的结构,这些树还生成一类(不一定是近似的)H@在H@因为很少有在该过程中创建或销毁基础数据。显然,这些近似分配律并不是通过提升产生的,而是直接从H@上的单子结构产生的。回想一下,H@的代数由(A,[]i)生成,其中[]i:Ai→A是A上的i元运算。对于i,j≥@1,我们建立了一个递归模式,H@在集合Hi上的函子提升为了做到这一点,我们定义(H@)在情况下,明确定义(H@)≠(A,[ ]i)=(H@A,[ ]i)。 (Note我们用同样的符号J J对于两个i元运算)。当i= 1• [(Lja)]1=Lj([a]1)• [(Bjt1. tj)]1=Bj[t1]1. [tj]1当j= 1时,我们有• [L1a1,... L1ai] i=L1 [a1,.一个[i] i• [L1a1,... L1ai−1,(B1t)]i=B1[L1a1,. L1ai−1,t]i• 等• [(B1t1)t2. ti]i=B1[t1,t2. 我的否则,对于i,j≥2• [Lja1,. Ljai] i=Lj [ai,.一个[i] i• [Lja1,. Ljai−1,(Bjti,1. ti,j)]i=Bj[Lja1,. Ljai−1,ti,1]iti,2. ti,j• 等• [(Bjt1,1. t1,j)t2. ti]i=Bjt1,1. t1,j−1[t1,j,t2. 我的286E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277J我1JJ我我我我我 JJ我我 JJ我我 JJ定理4.12对于i,j≥1,存在递归定义的近距离模式在所有自由单子H@,H@之间的分配律λ:H@H@→H@H以上i j j i i j证据 通过提升函子(H@)的推广, 建 立 了 一 个 近 似 分 布 律 λH@代数。将(H@)i应用于(H@A,Bi),i元运算i j i与正则代数(H@A,μ)相关联的生成λ,由以下定义方程组• λ(LiLja)=LjLia• λLi(Bjt1. tj)= Bj(λ Lit1). (λ Litj)• λ(Bit1. ti)=[λti] i其中[] i的定义与前面的结果相同这两个定律(DL C)和(DL D)的成立是通过结构递归从一个简单的论点得出的,留给读者。Q例4.13对于定理4.12中i = 1的特殊情况,H@是写单子N×,其中N是自然数{0,1,2,. . }下添加。 λ:N×H@a→H@(N×A)实际上是一个分配律,其中λ(n,t)将n分配给树t的每个叶子。同样对于j= 1的特殊情况λ:H@(N×A)→N×H@A又是一个完全分配律,如下所示。用于H@(N×A)中的任意树t,λ t=(k,t)其中t是H@A中的树,与t相同的形状,通过将形式Li(m,a)的t中的每个叶替换为Lia而其中k等于在叶子中找到的所有m的和定理4.12的近似分配律是否总是前例中两种情况下的在其他情况下,答案都是否定的定理4.14对任意i,j≥2,近似分配律λ:H@H@→H@H@定理4.12不能产生一个分配律,因为人们可以产生一棵树tH@H@H@,其中定律(DL B)失效。i j j证据对于λ:H@H@→H@H@,我们生成一棵树t∈H@H@H@,其中4(j−1)+i(B)不合格的。 让• lt = Bj(Lj(Lja1)). (Lj(Ljaj−1))(Lj(Bj(Ljaj). (Lja2j− 1)• rt= Bj(Lj(Bj(Lja2 j). (Lja3 j− 1)(Lj(Lja3 j)). (Lj(Lja4j−2))• t= Bi(Li(lt))(Li(Lj(Ljb1). (Li(Lj(Ljbi−2)(Li(rt))则(DL B)对于该t失败。细节留给读者。Q5前单核细胞定义5.1V中的前单子是H=(H,μ,η),其中H:V → V是函子,η:id→H,μ:HH→H是自然变换。∈E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277287−−−−→前单子的组成很容易得到。若(H,μ,η)和(K,ν,ρ)是预单子,且λ:HK→KH是自然变换,则得到复合预单子(KH,KHKH−−K−λ−H−→KKHHνμρηKH,id−→KH)它发展了带有附加公理的λ将分类K到VH的函子提升。为了理解这一点,我们必须定义定义5.2定义前单子H=(H,μ,η)和H-同态f:(X,μ)→(Y,θ)的代数(X,μ)的公理与定义单子的公理完全相同,即XηX)HX(μX\\Hf)公司简介ID\nHθX\ \\vv v vX(HXξX)YF对于单子,所得的代数范畴记为VH。众所周知,单子的代数理论提供了一种发展泛代数的方法[9]。对于一个预单子K,存在一个同构Φ:VK→ VK·,其中K·是单子,也就是说VK→V是单子的。 根据著名的这表明前单子在发展泛代数中起着重要作用。这个想法将在其他地方发展,但我们现在提出一个带是其中每个元素都是幂等元的半群带是满足附加方程xx=x的半群的簇,所以带的单子B是非空列表单子的商单子θ:L→B注意,在本文中,列表单子将指非空列表。从单子程序员的角度来看,自由带BX的构造(尽管当X是时BX是有限的,这与列表的情况不同)并不直观。[6]的一整节专门讨论所涉及的问题接下来我们介绍一种只使用列表数据类型的波段方法。这说明了我们的主张,即通过放松公理,我们有时可以使用现成的数据类型来描述我们需要的东西。我们将在下面的定理6.2中看到,这个结果如何导致在确定近似分配律时的简化。因此,我们已经绕过了工作,以解决字的问题,为自由乐队简单地不需要它!命题5.3设(L,m,e)是集合中非空列表的单子。将其修改为p re monad(L,m,e),其中r eXx=[x,x]。集合(L,m,e)是288E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277·f#−→−→#−→−−−−−−→乐队.证据一个代数(X,X)满足XeX\\ID\)LX(mXξLLXLX\ \\v vX(LXξ我们有x=<$[x,x] =<$(mX[[x],[x]])=<$(L <$)[[x],[x]])=([[x],[x]]=eX([x])=[x]但(X,· )也 是 单 子 的 一个代数,即 半群(X, ·)有h∈([x1,..., xn])=x1···xn。这个半群是一个带,因为x2=<$[x,x] = x。其余的细节都是例行公事。Q虽然每个单子都是前单子,但前单子不需要满足三个单子公理中的任何一个。我们确实有两个前单子定律或公理(PME.1,PME.2),其中命题5.4P_r_monads可简单地描述为(H,()#,η),其中FH:V → V是函子,η:id→H是自然变换,X−→HY<$→HX−→HY是一个服从公理的算子,(idHZ)(PME.1)Forg:Y→HZ, g#=HYHG 公司简介(PME.2)F或f:X→HY,g:Y→Z,(Hg)f#=((Hg)f)#对于单子,对应关系是(四)(五)f#=HXHfμX=(idHX)#HHYμY HY证据设(H,μ,n)为一个前单子。对于f:X→HY,定义f#:HX→HY,如(4)所示。由于H(idHX)= idHX,(idHX)=μX,这给出(PME.1)。对于(PME.2),设f:X→HY,g:Y→Z. 然后(Hg)f#=(Hg)μY(Hf)=μZ(Hg)(Hf)(μnatural)=μZH((Hg)f)=((Hg)f)##E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277289相反,设(PME.1,PME.2)保持不变,并通过(5)定义μ(4)由PME.1持有为g:Y→Z,(Hg)μY=(Hg)(idHY)#=((Hg)idHY)#(PME.2)=(Hg)#=μZ(HHg)290E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277#−→=HXXHKXX−→−→−→σ\这表明μ是自然的。 为了完成证明,我们证明这两个通道是逆双射。 从(·)#开始 , 定 义 μZ= ( idHZ ) #anddten ( · ) ##by ( 4 ) 。 则 ( · ) #= ( · ) ##by(PME.1)。 从μ开始,定义(·)#,如(4)中所示,并且nνZ=(id HZ)。 则νZ=μZ,从(4)中设置g = id HZ可以清楚地看出。 证据是完整的。Q定义5.5设H=(H,μ,η),K=(K,ν,ρ)是预单子。前单子映射σ:H→K是自然变换σ:H→K,使得idη)H(μHH\\联系我们\\v vK( νKK这个定义与通常的单子映射的定义相同,所以单子构成了前单子的一个完整的子范畴定义5.6给定V中的一个前单子H,H的单子近似是H在单子的全子范畴中的反射σ:H→K定理5.7设H=(H,μ,η),K=(K,ν,ρ)是V中的预单子。然后,一个预单子映射σ:H→K在V上诱导一个函子W:VK→ VH,定义为:(六)W(X,H)=(X,HXσXξKX−→X)另外,如果K是单子,则σ<$→W是有逆的双射(7) σXHρ−−−−→γ−→KX其中(KX,γX)= W(KX,νX)。证据给定σ,我们首先证明W(X,λ)是H-代数。这一点源于n σXηX=n ρX=idX和<$σXμX=<$νX(σσ)X (σ前单子映射)=νXσKX(HσX)=<$(K <$)σKX(HσX)(K-代数)=σX(H)(HσX)(σnatural)=<$σXH(<$σX)从σ的自然性可以清楚地看出,W将同态映射到同态。现在假设K是一个单子,使得(KX,νX)是一个K-代数。接下来我们证明,如果W<$→σ<$→W,则W=W。(Of当然,我们不能在这里假设σ是一个前单子映射,因为它还没有被显示出来)。从一个K-代数(X,X)开始W(X,λ)是(X,HX σXKX<$X),其中σ= HX HρXHKXγXKX−→XE. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277291且(KX,γX)=W(KX,νX). 当n:(KX,νX)→(X,ν)是K-同态时,(KX,γX)→W(X,γX)是H-同态.记W(X,δ)为(X,δ),我们292E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277有交换图HρXHX\\ID\)HKXHγX)KXξX\ \\v vHX) Xδ其中正方形是因为k是同态,三角形是K-代数公理。但是最上面一行是σX,所以δ=<$σX和W(X,<$)=(X,δ)=W(X,<$)。 特别地,我们可以将这一点应用于K-代数(KX,νX),以建立:(8) γX=νXσKX我们转而证明W→σ是有明确定义的。 对于V中的f:X→Y,Kf:(KX,νX)→(KY,νY)是K-同态.应用W得到图HXHρX)HKXγX)KXHf HKf Kfv v v)的情况)公司简介但是左边的方块是上下班的,因为ρ是自然的。因为行是σX和σY,所以图的周长表明σ是自然的。第一个pre-monad映射定律如下所示:σXηX=γX(HρX)ηX=γXηKXρX(η自然)=ρX((KX,γX)代数)对于第二预单子映射定律,νX(σσ)X=νXσKX(HσX)=γX(HσX)(由(8))=γX(HγX)(HHρX)=γXμKX(HHρX)((KX,γ)代数)=γX(HρX)μX(μnatural)=σXμX最后,我们证明了如果σ <$→ W <$→ σ,则σ= σ。σX=γX(HρX)=νXσKX(HρX)(由(8))=νX(KρX)σX(σnatural)=σX(Kmonad)Q定理5.8设H是一个预单子,使得U:VH→ V是一元的,使得存在一个单子K和V上范畴Φ:VK → VH的同构。则定理5.7中相应的预单子映射σ:H → K是H的单子逼近。E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277293HΦ···×证据设α:H→M是一个前单子映射,其中M是单子,并证明存在唯一的单子映射β来完成下面的三角形Hσ) K\α\β\ \vM设W :VM → VH 对应于α,设β是唯一单子映射对应于VM−W→V−1−→ V K. 我们把剩下的细节留给读者Q例5.9由定理可知,σ:(L,m,e)→B是带单子的单子近似。 这个例子很容易推广。Let(L,m,e)e是列表前置元,其中e(x)=[x,x,x,,x]n次,m是列表的常用计数。设Se t(L,m,e)是n-带范畴(其中每个元素都有hxn=x的半群).例5.10设(L,m,e)为列表前缀,其中e(x) 为[x]和m[l1,. lk]=l++l++. lk次,其中l具有与列表l1相同的长度,并且其所有元素都是l1的第一个元素。 其中σ[a1.ak]=(k,a1)作为单子近似有读者单子N × A,其中N =(N,n,1)是乘法下的自然数的单子。例5.11矩形带是一个半群,其中每个元素都是恒等式,并且满足方程xyz=xz。设(L,m,e)为Li,前单子,其中e∈(x)=[x,x]anddm∈ll l=[fstfstll,lstlstll],其中refstandlstpick取出非空列表的第一个和最后一个元素。与命题5.3的情况一样,na lgebr a(X,n)inSe t(L,m,en)满足x=n[x]。另外,x(yz)=<$[<$[x],<$[y,z]]=m[[x],[y,z]]=[x,z]=xz类似地,(xy)z=xz。矩形带单子R =(R,μ,η)其中RA =A×A是由反射σ[x]=(x,x)和σ[x1, . . xn]=(x1,xn). 我们可以很容易地证明σ是一个premonad映射,并且(R,μ,η)的monad性质可以直接从(L,m,e)导出。 参见例6.5。例 5.12 设 ( L ,m, e ) 是 列 表 前置 元, 其 中 e ( x) =[x] ,m[[x]]=[x] , m[l1 , .lk] =[fstl1, fstl1]。 则σ:L→B×A定义为yσ[a] =(F,a),σ[a1. ak]=(T ,a1)定义了Boo lean-集合单子B的单子a p p r oximation其中B=(T,F),B=(B,OR, F)。集合(L,m∈ ,e)中的代数(X,n)是满足xy=x2的半群,因为xy=[x,y]=[[x],[y]]=m[[x],[y]]=[x,x]=x2294E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277→−→=HKXX HKMXXθλX6准单子的近似分布律我们注意到,定律DL A,DL B,DL C,DL D在(H,μ,η)时是有意义的,(K,ν,ρ)是前单子。在这一节中,我们将展示预单子的分配律和近似分配律如何在它们的单子近似上导出类似的律如[10,定理2.2.2]所示,当H是单子时,下面的结果是众所周知的。当H是一个预单子时的推广必须小心地证明定理6.1设K:V → V是函子,(M,m,e)是V中的单子,(H,μ,η)是V中的预单子,使得VH →V是单子的。 函升K<$:VM → VH双射地对应于满足(K<$A,K<$B)的自然变换λ:HK KM:KηK)HK\( μKHHK\\(KA)\\柯\ \λv(KB)vHλHKMvλM对应关系是\\KM(KMMKm(9) K(X,MX−→X)=(KX,HKX且若K∈(MX,mX)=(KMX,γX),KMX−K−→θKX)(10) λXHKe−−−−→γ−−−−→ KMX此外,如果M仅是一个预单子,即如果λ满足(K<$A)和(K<$B),则如(9)中所示的K<$是K的函子提升VM→VH。证据设λ满足(K<$A)和(K<$B),且M,H是任意的预单子,我们首先通过检验定义5.2中的性质证明了(KMX,(Kθ)λX)是H-代数. 我们有(Kθ)λXηKX=(Kθ)(KeX)((K<$A)forλ)=idKX(θ代数)还有,(Kθ)λXμKX=(Kθ)(KmX)λMX(HλX)((K<$ B)forλ)=(Kθ)(KMθ)λMX(HλX)(θ代数)=(Kθ)λX(HKθ)(HλX)(λnatural)进一步,M-同态f:(X,θ)→(Y,θ),Kf是H-同态,如下:(Kf)(K θ)λX=(Kθ)(KMf)λX(M-同态)=(Kθ)λY(HKf)(λnatural)相反,现在假设M是单子,令K:VM→ VH是函子K的升力。Letσ:H→H^使得(H^,μ^,η^)是单子幂次化E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277295^^σK^λ^λ=HK−→HK−→KM^^^^^^^^X^X^X^^^=HKMX−−→H^KMX^KMX. By(10),其中h成立,因为H^对应于同构Φ:VH→VH,(X,<$)<$$> →(X,<$σX),如定理五点八 这就产生了一个新的函子提升s −1VM−−K−−→VH−−Φ−→VH由于该定理对单子成立,它对应于满足(K<$A)和(K<$B)的自然变换λ ^:H ^K → K M。德费恩我们首先证明这样的λ满足(K<$ A)和(K<$ B)。λ(σK)(ηK)=λ(ηK)(σ预单子映射)=Ke((K<$A)forλ)λ(σK)(μK)=λ(μK)(σHK)(HσK)(σ前单子映射)=(Km)(λM)(Hλ)(σHK)(HσK)((K<$B)forλ)=(Km)(λ^M)(σKM)(Hλ^)(HσK)(σnatural)如所期望的。若K∈(MX,mX) =(KMX,γX),则存在唯一的H^-代数(KMX,γ^X)关于γ XσKMXγ−→是一单子,λ^X=H^KMXHKe−−−−→ H^KMXγ−→KMX。 然后我们可以检查λ是其定义如下(10)。λXσKX=γX(HKEX)σKX=γXσKMX(HKEX)(σ自然)=γX(HKEX)到目前为止,(9,10)的段落定义得很好。如果λ→λ1,则γX=(KmX)λMX,所以λ1,X=(KmX)λMX(HKEX)=(KmX)(KMeX)λX(λnatural)=idKMXλX(mX代数)=λXδ若K<$λ <$→K·,设K<$(X,<$)=(KX,HKX−→KX)。以K的M-同态<$:(MX,mX)→(X,<$)给出一个交换平方HKMX香港赛马会)HKXγXδV V)的方式KMXKKX296E. Manes,P.Mulry/Electronic Notes in Theoretical Computer Science 341(2018)277则K·(X,λ)=(KX,λ),其中=(K=(K)γX(KHeX)=δ(HK(X))=δ(X代数)Q
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功