没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记308(2014)273-288www.elsevier.com/locate/entcs共诱导恢复单子MaciejPir'og1,Jerem yGibbons2牛津大学计算机科学系摘要恢复作为一种方便的抽象以多种形式出现,例如在并发的语义和作为编程模式。在本文中,我们介绍了广义的范畴理论,coalgebraic上下文中,并显示其基本性质:他们形成一个单子,他们配备了一个corecursionscheme的意义上的Ad′amek等人。的概念完全迭代的单子(cims),他们享有一定的普适属性,专门用于与自由cims的范畴的余积cims保留字:选择,完全迭代单子,余代数1介绍1.1续会Milner [32]引入恢复来表示并发理论中通信代理的外部行为。在范畴术语中,如Abramsky [1]所给出的,恢复是SET上函子RX=(X×O)I的最终余代数νR的载体的元素,其中I和O分别是可能的输入和输出的集合。非正式地说,恢复是一个函数,它消耗一些输入并返回一些输出,并与另一个恢复配对,而finality意味着消费和生产的过程可以无限迭代。有许多可能的推广,例如,对于具有有限分支非确定性行为的主体,可以推广到函子Pfin((-)×O)I的最终余代数,或者,根据主体实现的计算效果,可以推广到任何单子来代替Pfin,正如Hasuo和Jacobs [24]所研究的那样“可并行”计算的思想也出现在计算效应和一元编程的背景下。Cenciarelli和Moggi[13]定义了什么1maciej. cs.ox.ac.uk2jeremy. cs.ox.ac.ukhttp://dx.doi.org/10.1016/j.entcs.2014.10.0151571-0661/© 2014 Elsevier B. V.保留所有权利。274M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273他们将广义恢复单子Transformer称为TA=μX.M(μX +A),其中M是单子,μ X是内函子,A是变量的对象,这允许顺序地组合子。恢复单子可以由M(M)M++给出,M ++是由M ++和M ++生成的自由单子。它是规范的,因为它是单子范畴和单子态射范畴中M和M的余积,如Hyland,Plotkin和Power所示[26]。恢复单子是由一个初始代数,所以它不完全是一个generalisation的研究米尔纳和其他人。直观地说,它对只能无限次迭代的选择进行建模。因此,很自然地要问M(-)+A)形函子的最终余代数。事实上,Goncharov和S chr?oder[21]使用了形状为TA=νX的单子。M(X+A)是给具有类属效应的并发过程赋予语义的,而单子TA=νX.M(νX +A)是作者[39]以“共归纳恢复单子”的名义讨论的在本文中,我们进一步推广后者的建设,并仔细研究其性质。1.2共诱导通常,如果一个无集合的数据结构是由一个最终余代数的载体给出的,那么它被称为余归纳的非正式地,finality意味着描述一个步骤的余代数c:X→FX可以无限地重复以逐层构建类型为νF的结构。然而,在一元世界中,这些步骤通常是相互作用的显然,在这个意义上,并不是每个单子都是共归纳的,因为无限多层乘法的概念并不总是很好地定义的。因此,捕捉的概念,共归纳在一元上下文中,我们采用了一个属性,称为完全迭代,介绍了埃尔戈特等人。 [16]后来被Ad'amek等人研究。 [4、30]。一个单子M是完全迭代的(是一个“cim”),如果它配备了一个额外的A是参数(最终值)的对象,具有唯一解e<$:X→MA,与M的一元结构一致。不太令人惊讶的是,共同归纳的通常概念被自由的完全迭代单子(非正式地说:层不相互作用)捕获。由闭函子F生成的自由完全迭代单子为F∞A=νX.FX+A,其单子结构由A中的代换给出.一个普通的余代数X→FX可以看作是一个守护态射X→F∞(X+0),其中0是初始对象的基函数y的唯一解X→F∞0<$=νF。M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273275μπ·fM=f·μ:MM→Mπ。1.3贡献单子TA=νX.M(<$X+A)也可以表示为M(<$M)∞。 在第3节中,我们将这种构造推广到MS∞,其中S是M的任意右模(所有必要的定义和符号都在第2节中给出)。我们给它一个单子结构,并证明它是完全迭代的。此外,如果M也是一个cim,MS∞是一个cim在第4节中,我们将注意力转回实例M(M)∞。我们证明了它具有一定的普适性质,这就意味着它是cims范畴中M与M在第5节中,我们讨论了我们的构造在语义和编程中的我们只提出一些证明的简短大纲。有关完整的证明,请参阅相关的技术附录 , 可 在 www.example.com people/maciej.pirog/crm-appendix.pdf 上 在 线http://www.cs.ox.ac.uk/查阅。2理想化和完全迭代单子在本文的其余部分,我们在具有有限余积的基范畴B中工作。为了简洁起见,我们假设余积双函子是严格结合的。左和右喷射分别称为inl和inr。对于一个内函子F:B→B,我们将初始F-代数的载体记为μF,将最终F-余代数的载体记为νF。从余代数 <$A , g : A→F A<$ 到 最 终 余 代 数<$νF , g : νF→FνF<$ 的唯 一 态 射 记 为[(g)]。 我们用字母M,N,T表示单子。它们的单子结构总是表示为η(单位)和μ(乘法),可能带有上标以将自然变换分配给适当的单子。单子和单子态射的范畴记为MND,而单子M的Eilenberg-Moore代数的范畴记为M-MALG。定义2.1设M是单子。一个内函子M与一个自然变换(作用)μ:MM→M一起称为(右)M-模,如果μ·Mη = id:M→M且μ·μM = μ·Mμ:MM2→M.我们定义了两个M-模<$M,μm与<$M<$,μm之间的态射为自然变换f:M→M<$,稍微滥用一下符号,我们可以把一个模μM,μM简单地记为M。示例2.2以下是模块的示例:(i) 对于单子M,对μM,μM是M-模.(ii) 设m:M→T是一个单子态射。则对T,μT·T m是M-模块。(iii) 设μM,μ M是M-模,F是闭函子. 那么,是一个M模。(iv) 有了上面的定义,设λ:TM→MT是一个分布律,276M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273˜˜˜˜˜˜˜→−−−−−−−−−−−−−→单子。对<$MT,(μM<$μT)·MλT<$是诱导单子的模山(v) 如果M,μ M,μ M,μ M是两个M-模,则对M + M,μ M+ μ M,μ M也是一个M-模.(vi) 设F是具有右伴随U的闭函子。则F是一个UF-模,其作用为εF:FUF→F,其中ε是其邻接的计数定义2.3一个理想单子是一个三元组,由一个单子M,一个M-模<$M,μ M <$M,和一个模同态σ:<$M,μ M<$M → <$M,μ M <$M组成。我们说M用<$M,μM<$理想化。如果M = M + Id,我们说M是理想的。对于一个内函子F,一个自然变换k:F → M是理想的,如果它通过σ因子分解。如果没有特别说明,对于理想单子M,我们总是用μM表示相联模M的作用,用σM表示相联模同态。例2.4扩展例2.2(iv)和(v),我们认为:(i) 设M是M的理想化,λ:TM→MT是单子之间的分配律.诱导的单子MT与MT理想化。伴随的模态射由σ MT:MT→MT给出。(ii) 让M与M一起理想化,也与M一起理想化。然后,M被识别为M+M。伴随模态射由[σ,σJ]:M+M M给出,其中σ和σJ是两个模各自的伴随态射。定义2.5设M是一个用M理想化的单子。 一个态射e:X → M(X +A)被称为守护方程态射,如果它的因子如下:X−−·M(X+A)+A[σX+A,ηX+A·inrX,A]M(X+A)我们称一个态射e<$:X→MA为e的解,e†X MAeM(X+A)M[e<$,ηA]μAM2A一个理想单子M是完全迭代的(是一个“cim ”),如果每个守护方程态射有一个唯一的解决方案。一个单子态射m:M → T,其中T被理想化为<$T,μ T<$T,称为保解,如果存在一个自然变换m:M → T,使得m·σ M= σ T·m:M→T。我们把所有的Cims和保解单子态射的范畴记为CIM。注意,我们在cims和Ad′amek之间使用了不同的态射概念等人 [5],其态射-称为理想化单子态射-也保持M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273277∞−−→∞模块的结构“保解”这个名字5.9])。cim的一个重要例子是由闭函子生成的自由cim∞。直觉上,它捕捉到了非良基项的单子。给定一个endo函子(一个签名),如果最终余代数<$νX. <$X+A,<$A<$对所有对象A都存在,则我们定义<$ A = νX。X+A。 可以证明它在A中是函子的, 它在态射上具有明显的作用,并且它具有由A中的代换给出的一元结构,我们记为η∞和μ∞。Monad∞是理想的和完全迭代的。我们定义一个自然变换emb:n→n∞为:实施例AΣη∞−−−→ A−i→nlA+A−1∞A正如Aczel等人所讨论的那样。 [4],∞是由生成的自由cim。直观地说,这意味着,对cimM中的所有结构的每一个理想解释都以一种独特的方式延伸到对M中整个结构的解释。形式上:定理2.6对于cim M和理想自然变换k:n→M,存在唯一的单子态射i(k):n ∞→M使得k=i(k)·emb.此外,态射I(k)保持解。我们还需要以下取消属性:引理2.7对于cim M和保解单子态射m:∞→M,合成m·emb是理想的自然变换,且i(m·emb)= m。3一元结构与完全迭代性设μS是右M-模,使得S∞存在.我们通过一个分配律给出MS的一元结构[11]。这个结构是Hyland、Plotkin和Power的证明[ 26 ]的一个改编,证明了归纳推理M(M(M))构成一个单子。我们利用Ada′mek,Milius和Velebil[7]的结论,即完备Elgot代数的范畴在基范畴B上是严格一元的.注意,我们不能在参数化单子上使用Uustalu我们首先回顾一下 Elgot代数[7]。定义3.1设H是闭函子。对于两个对象A和X,我们称一个态射e:X→HX + A为一个代数方程态射。 我们称态射e<$:X→A为H-代数a:HA→A中的解,如果下面的图.=A.A.278M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273id+h−−−→−→第二个,,展开at方程态射“并行”:通勤:e†X AeHX+AHe+id[a,id]HA+A就像在cims的情况下,我们用(-)†或(-)表示埃尔戈代数中的解。这种重载不应该造成任何混乱,因为我们总是清楚类型。定义3.2对于非线性方程态射e:X→HX + Y和f:Y→HY + A,以及态射h:Y → Z,我们定义两个运算。 第一个,a,使用态射h '重命名'参数Y:哈 埃=.X−→e HX+Y−−−→ HX+Z系列fe=.X+Y[e,inr]id+fHX+Y−−→公司简介[Hinl,Hinr]+id−→H(X+Y) +A定义3.3对于闭函子H,完备ElgotH-代数是三元组A,a:HA→A,(-)<$A,其中(-)<$A赋予每个方程态射e:X→HX+A是解e+:X→A,使得以下两个条件成立:• 设两个方程态射e:X → HX + A和f:Y → HY +A为H(-)+A余代数,设h:X →Y为余代数同态,即f·h=(Hh+idA)·e.那么,e<$= f<$·h。• (复合性)对于两个方程态射e:X→HX+Y和f:Y→HY+A成立,(f<$ae)<$=(fe)<$·inl.定义3.4F或两个完全的ElgotH-代数为A,a,(-)和B,b,(-),a称态射h:A → B保持解,如果对于每个非线性方程态射e:X→HX + A,它保持(ha e)ε= h·e<$。完备Elgot H-代数与保解态射构成一个范畴,记为H-Elgot。定理3.5(Ad′amek,Milius,Velebil[7])明显有效函子UElg : H-E LGOT→B 是 严 格 H∞-monadic ( 或 在 Mac Lane 的 术 语 中 简 称 为'monadic'[ 29,Ch. 6]),则H-ELGOT=H∞-MALG.构造3.6回想一下,μ S是右M-模。 对于一个完备的Elgot代数<$A,a:SA→A,(-)<$$>,我们定义一个代数<$MA,aJ:SMA→MA,(-)<$A如下:aJ=.SMAμSSA−→aηMA−−→ MAΣM. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273279121214341121423X−→SX+MA−−→SX+A+MA−→A+MA−→MA→⎤∗22x·········11设e:X→SX + MA是一个非齐次方程态射.我们定义一个辅助态射|e|和解决方案E:|= .|=.SX+A−S−e+−→idS(SX+MA) +A−t−a−t+−→idS(SX+A) +A- 是的ee =inl+id|† +id|†+ id[ηM,id]其中,A,B处的Δ t给出为:S(ηM+id)S[Minl,Minr]μSS(A+MB)−→S(MA+MB)−−→SM(A+B)−→S(A+B)引理3.7来自构造式3.6的三重Elgot,a,J,(-)Elgot是一个完备Elgot代数。此外,对象上的赋值<$A,a,(-)<$A → <$MA,AJ,(-)<$A和态射上的赋值f <$→Mf是S-Elgot上的一个闭函子,其一元结构由M的一元结构给出.定理3.8合成MS∞是单子。证据引 理 3 . 7 的赋值是一个 单子,所以它是M 的提升,关于UElg的S-ELGOT。因此,在本发明中, 根据定理3.5, 这是M的提升,S∞-M算法这导致了单子λ:S∞M MS∞之间的分配律,它给出了MS∞的一个单子结构。Q∗⎡∗1 1⎢ ⎥···a联系我们···abc=中国11亿bc·· ·······Fig. 1. D(O×D(-))∞单子中的一个替换例子例3.9设B为S ET,D为离散概率分布的单子,O ={a,b,. . }是一个集合,并且<$X=O×X是一个闭函子。单子的载体的一个元素D(D)∞X是一个可数分支的,可能是无限的决策树,其中节点(除了根)用集合O的元素标记,边用概率标记,叶用X的元素标记。 这样的结构可以理解为一个可能非终止的概率过程的表示,该过程产生O的元素流作为其输出。从技术的角度来看,重要的是根没有标签1323280M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273X→→到达一片叶子。这样,当我们用树替换变量时,在生成标签或到达叶子之前,我们需要两D(D)∞X的一元结构通过将相邻的分布相乘来将这些分布简化为一个概率步骤;参见图1的示例。例3.10在一个Carnival闭范畴中,我们可以定义一个跟踪所有(可能是无限多个)中间状态的状态单子。 它与[ 39 ]中给出的“状态”相似但不完全相同(也可以比较Ahman和Uustalu的更新单子[ 8 ])。 固定一个状态为A的对象,并考虑读取器monad RX = X A。作者WX=X×A是R-模.动作可以被给出为:EvA,outrEv:WRX= X A×A→X×A = WX,其中ev是指数对象的求值态射,outr是右投影,而Ev-,-Ev是乘积中介。直觉上,对于一个初始状态,单子RW∞ =((-× A)∞)A产生一个(可能无限的)中间状态流W∞。如果流是有限的,则它以计算的最终值终止单子RW∞是恢复单子的一个例子,它通常不是由最终余代数给出现在,假设M关于一个模M是完全迭代的。注意,一个证明了MS∞是关于模MS∞+MSS∞的cim.这意味着每一个共归纳步骤都可以定义3.11对于一个单子T,一个T-模T在一个单子M上的分配律是一个单子λ:TM →MT之间的分配律,加上一个自然变换λ:TM MT,使得单子之间的分配律的图的明显类似物可交换(除了ηT的图,因为一般来说T不是单子)。此外,如果T与T理想化,我们说元组如果Mσ T·λ = λ·σ TM:TM → MT,则λ λ保持模.引理3.12设T是一个理想单子,且λ ∈λ,λ ∈ λ是T在M上的保模分配律。然后用MT将诱导单子MT理想化我们可以证明定理3.8中的λ:S∞MS∞可以推广到M上SS∞的保模分配律。因此,引理3.12与例2.4一起将我们引向以下推论:推论3.13单子MS∞是关于MS∞+ MSS∞理想化的。我们将MS∞中的解描述为两步过程。直觉上,给定一个方程态射e:X→MS∞(X+A),我们首先通过M的完全迭代结构“水平”展开我们只剩下可以看作是M的Kleisli范畴中分配律λ诱导的单子中的方程态射。这个态射(首先,我们需要以下技术引理:M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273281−−−−−−−−−−−−→−−−−−−−−−→^Bf:A→MB在Kl(M)中,我们定义了一个B-态射f^=μ·Sf:SA→SB.我们K→[σ,Mσ,η·inr]M[σ,M(inl·inr),η·inr]引理3.14设M是cim。令e:X→M(X + A + B)因子如下:X−−·M(X+A+B)+MA+B[σ,M(inl·inr),η·inr]M(X+A+B)态射e有一个唯一解e†:X → M(A + B)。单子NS∞具有以下性质,这比cim更强:引理3.15设e:X→MS∞(X+A)是一个态射,其因子如下:X−−·M(SS∞(X+A) +A)M[σ∞,η∞·inr]那么,e在MS ∞中有唯一解e∞。MS∞(X+A)证据 考虑M 的Kleisli范畴,记为l(M)。对于态射,SB在Kl(M)上定义一个闭函子G,给定GA=SA,G(f:A→MB)= η M·Sf:SA→MSB。分配律λ在Kl(M)上诱导出一个单子S∞,给出了S∞A=S∞A和S∞(f:A→MB)=λB·S∞f:S∞A→MS∞B. 我们可以证明,在Kl(M)中的G。态射e是S∞中的守护方程态射,因此它有唯一解e:X→MS∞A。可以验证它是所需的态射,并且它是唯一的。Q现在,我们可以证明主要定理:定理3.16单子MS∞关于模完全迭代MS∞+ MSS∞。证据 在这个证明中,为了简洁起见,我们将S∞记为T,将其模SS∞记为T。让e:XMT(X+A)是一个守护方程态射.这意味着它的因素,M TX−−·MT(X+A)+MT(X+A)+A−− →MT(X+A)。因为T是理想Monad,存在同构T(X+A)<$=T(X+A)+X+A<$=X+T(X+A)+A.因此,e因子为X−−·M(X+T(X+A)+A)+MT(X+A)+A−→M(X+T(X+A)+A),并且在引理3.14的意义下,它是单子M中的一个守护方程态射。因此,存在唯一解e†:X→M(T(X+A)+A)。态射M[σT,ηT·inr]·e<$:X→MT(X+A)在引理3.15的意义下是一个守护方程态射,因此它有唯一解(M[σT,ηT·inr]·e<$)<$:X→MTA。可以证明它是MT中e的唯一解。Q例3.17考虑例3.9中的单子D(D)∞。这是一个cim,它为我们提供了一个具有顺序组合的概率过程的语义。方程态射e:X→ D(D)∞(X+A)可以理解为一个转移系统,其中X是状态空间。解e<$:X→ D(D)∞A是一个定义语义:对于初始状态,它给我们决策树,而所有中间状态都被遗忘(它们是计算的内部解决方案图是充分的。282M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273FG∞·−−−→对于水平和垂直完全迭代的例子,考虑终端对象1的单子DJX=D(1 +X 它是关于模块的cim,由D j的值组成,这些值以至少为0的概率失败。5.一个过程的每一个转移都可以从集合O中产生一个输出,或者执行一个无声的步骤,但是失败的概率至少为0。5.4泛性质与余积MS∞的一个特别有趣的例子是M(M)∞。在这一节中,我们研究了它的普适性质:对于cimN,一个单子态射M→N和一个理想自然变换<$N,存在唯一的相干单子态射M(<$M)∞→N.非正式地说,在另一个cim中“解释”恢复结构的每一个层次的态射首先,我们定义三种liftl=.Σm(embmM)−→(M)ηM(μM)∞−→M(M)liftr=.MMη∞M(M)∞liftf=.−e−m→b∞−l−if→tlM(M)∞很容易看出liftl和liftr是单子态射(liftl是两个单子态射的合成)。它们也是保解的,前者通过M<$M(<$M)∞,后者通过M(<$M)∞。定义4.1用φ/CIM表示以下范畴:对象是理想的自然的,F一般变换(T−→T),其中T是一个正态射;态射是一个正态射(不是必然的保解的)单子态射k:T→N使得下面的图交换:不克NF我们定义了一个有效函子U:n/Cm→MND为U(n-→M)=M和Uk = k关于态射。定义4.2一个单子M称为可分解的,如果(M)∞存在。我们用R-Res表示M ND的以可解的cim为对象的全子范畴. 我们将包含函子记为I:Res →MND。我们根据I-相对附加建立了泛性质.关于相对伴随的讨论,例如参见Altenkirch et al.[9]的文件。定理4.3函子U有一个I-相对左伴随F:RES→Res/CM由对象上的 FM=(f−l−if→tfM(fM)∞)和Fm=m<$[((fM(fM)∞+id)·[1]= m i(emb·m)。∞∞ΣM. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273283M−→−→−→证据可以证明态射Fm是单子态射,所以F确实是函子。设M是一个可解的单子,N是一个cim,g:n→N是一个理想的自然变换.我们定义同构G[-π :π/CIM[FM,(π−→通过N)]n=MND[IM,U(N)]N)]:[-|Fk:(f−l−if→tfM(fM)∞)→(fM)FN)m:M→U(N−→N)fliftff[k:M→U(−→N)[m|:(<$−−→M(<$M)∞)→(<$N)[k = k·Mη(M)∞[m|= μ N·(m i(μ N·(f m)对于[m|是一个定义良好的态射在/C IM,我们注意到,[m|·liftf = f。 利用M(M_M)_∞和自由cims的性质,可以证明[-cims]在M和g中是自然的,并且有[-cims]和[-cims].|是相互矛盾的。Q定理4.3的另一种解读是,(−l−if→tfM(M)∞)是自由的由可编译的cimM生成的可编译/CIM中的对象。 这意味着,对于cim N,理想自然变换g:n → N和单子态射m:M → N,存在唯一的单子态射j:M(n M)∞→N,使得下图互换(人们可以很容易地看到liftr是相对附加的单位):国际电梯联合会ΣGM(M)∞J升降机MN请注意,如果M=Id,上图实例化了一个事实,即∞确实是由生成的自由cim。更准确地说,单位元单子Id是MND中的初始值(唯一的单子态射!:Id→N由N的单位给出),所以上图的右边变得平凡,而左边恰好是定理2.6的图。此外,对于保解单子态射n:n∞→N,合成n·emb:n ∞→N是理想自然变换。对一个保解的单子态射m:M→N,存在唯一的单子态射j:M(M)∞→N使得m=j·liftr且n·emb=j·liftf=j·liftl·emb. 这意味着i(n·emb)=i(j·liftl·emb),因此,通过引理2.7,我们得到n=j·liftl。因此,态射j唯一地使得下面的图可交换:升降机ΣM(M)∞升降机M(1)Mn∞284M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273NM. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273285˜˜对于一个理想N,存在一个双边理想N(由NN给出)和一个多边理想态射j=U[m|M,n·emb不一定保持解,即使liftl,liftr,m和n保持解。 非正式地,j在M(<$M)∞ 然而,如果我们知道N是关于一个双边模的cim,定义4.4一个单子N的一个双边模是它的右模<$N,μR与一个自然变换μL:NN → N连在一起,使得与定义2.1的图相对应的明显的图是可交换的,并且μR·μLN =μL·NμR:NNN→N。同样,我们调整了模和理想单子之间同态的定义。 我们将关于双侧理想和保解单子态射完全迭代的单子范畴记为TC IM。在本文所研究的性质的上下文中,我们可以从CIM免费赠送TCIM定理4.5范畴TC_IM是C_im的一个满相对子范畴。换句话说,显嵌入函子UTC:TCIM→ C IM有一个左伴随FTC。实际上,这意味着对于单子N,同态N→N(也就是说,通过N保护的每个方程态射也是通过N保护),使得N关于N完全迭代。在这种情况下,由于图(1)中的j等于μN·(mi(μN·((n·emb)m),并且最左边的顶点的右侧幅角保持解(定理2.6),态射j也是解保持的,这可以通过一个简单的图追踪来验证。一般地说,M(M)∞的模是双边的,但M(M)∞的模并不自由因此,取图(1)在TCIM中的反射,我们得到以下推论,这是Hyland,Plotkin和Power的结果的推论4.6对于一个闭函子M和一个单子M关于一个双边理想完全迭代,M(M)∞(即M(M)∞被M(M)∞(M(M)∞+ M M(M)∞)理想化的M(M)∞)的F TC -象是∞和M在TC IM中的余积。5讨论5.1完全迭代性本文的结果是对完全迭代单子研究的一般贡献[4]。我们给出了新的cims的例子,并描述了自由cims的余积。注意,如果M是理想的,那么MS∞也是理想的,这意味着我们的构造可以扩展到理想cims的范畴,如果人们喜欢在这样的设置中工作的话。我们的结果表明,在普通monad和cims之间存在一种“最小与最大不动点”的对偶形式 F∞A=νX.FX+A,以及与自由对象的余积M(λM)λ,286M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273M(M)∞.在单子上还有其他涉及初始代数的构造,例如两个理想单子的余积,如Ghani和Uustalu [20]所示我们猜想,用ν代替μ的类似构造在理想cims范畴A d'ameketal. [5,6]考虑一个有限的情况:他们定义一个迭代单子(没有“完全”)作为一个局部有限可表示范畴上的有限单子,使得所有具有变量的有限可表示对象的守护方程态射都类似地,存在完备埃尔戈代数的一个有限版本(即埃尔戈代数)以及定理3.5的类似物。这表明,所提出的结构应该扩展到无穷大的情况,但我们还没有制定出细节。埃尔戈的原始结果是在代数理论的背景下,而不是一般的范畴理论。作为未来的研究方向,从代数规范(操作和方程)的角度来看待基于约束的结构将是很有趣的,特别是那些可以用于语义和编程的结构,比如例3.10中的日志单子。5.2语义和编程正如本作者在以前的论文中所建议的那样,Moggi [34]风格的产生可观察行为(如I/O)的模型需要一种完全迭代的形式,因为程序不需要终止。因此,通过了解cims的范畴,人们希望能更好地理解这些效应。例如,如果追求模块化,两个cim的MND中的余积一般不是完全迭代的。因此,这些效应的“最小”混合物的一个更好的概念这有一个实际的方面:Haskell编程语言配备了一个类似恢复的结构被用作进程的表示,即在执行过程中表现出可观察行为的程序(参见Abramsky [1])。一个单子结构捕获了组合的概念,这允许恢复单子作为Moggi风格的编程演算的基础[34]。例如,Goncharov和Schr?oder[21]给出了一个简单的语义,用于使用monadMM∞的异步并行进程。我们希望MS∞的更丰富的结构可以用来描述更高级的过程和同步过程,沿着Abramsky在纯函数式编程中,monad通常被用作嵌入式领域特定语言(EDSL),用于表示计算对象,使用函数性和monadic结构从原子操作构建。通常,这样的一元值描述不一定终止(因此,在某种意义上,共归纳)具有非平凡并行资源管理的程序,如懒惰I/O;例如,参见KiselyovM. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273287[28]第二十八话这样的程序通常由类似于monadic命令的数据结构来表示,它们与外部的“命令式”monad有着密切的关系这两者之间的关系可以通过本文中讨论的操作来形式化:IO操作可以被提升到选择级别(liftr),而整个EDSL程序可以被执行,也就是说,可以被转换回IO,这可以通过通用属性来建模5.3相关工作完全迭代性的概念是由Elgot [16]引入的,后来由Aczel等人 [4,30]研究Moss [35]和Ghani等人也研究了单子的性质。 [19 ]第10段。Milius和Moss使用Elgot代数[7]来描述递归程序方案的解决方案[31]。先前已知组合物M(M_M)_∞模M<$M(<$M)∞)[21,39]。与这些结果相反,我们的证明并不依赖于恢复单子由final余代数给出恢复用于许多不同形状和不同名称下的并发语义。Milner [32]、Plotkin [40]和Papaspyrou [37]采用了一种域理论的方法来解决选择问题相互作用树,即SET上P((-)×O)I形函子的最终余代数,其中P是幂集函子,在Abramsky的相互作用范畴[ 2 ]中得到了广泛的应用在程序设计中,不同形式的选择已经被独立地重新发现了几十次,并用于程序的灵活结构,尽管通常没有太多的正式处理。在Lisp社区中,函数被称为Claessen[14]、Kiselyov [28]、Harrison [23]和本书作者[38]讨论了涉及选择的不同编程模式Filinski和Støvring [ 17 ]以及Atkey等人也研究了代数背景下的数据和结果的交织。 [10 ]第10段。在类型论中,类似的结构被用来建模交互式程序(Hancock和Setzer [22]),通过 保 护 的 上 递 归 ( Capretta [12] ) 或 命 令 式 语 言 的 语 义 ( Nakata 和 Uustalu[36])。确认我们要感谢Stefan Milius对本文早期草稿的评论,以及匿名审稿人的详细评论和有益建议。这里报告的工作得到了英国EPSRC资助的项目“可重用性和依赖类型”(EP/G 034516/1)的部分支持。288M. Piróg,J.Gibbons/Electronic Notes in Theoretical Computer Science 308(2014)273引用[1] 萨姆森·艾布拉姆斯基进程代数中的若干路径回溯。Ugo Montanari和Vladimiro Sassone,编辑,国际并发理论会议(CONCUR),计算机科学讲义(LNCS)第1119卷,第1-17页。Springer,1996年。[2] Samson Abramsky,Simon Gay,and Rajagopal Nagarajan.交互作用类别和类型化并发编程的基础。1994年马克托伯多夫暑期学校演绎程序设计论文集,第35Springer-Verlag,1996.[3] 彼得·阿采尔。 非良基集。 第14话笔记笔记斯坦福大学语言与信息研究中心,1988年。[4] 彼得·阿 采 尔, J iramek , StefanMilius 和 J irVelebil 。 无 限 树 与 完 全 迭代理 论 : 一 个 共 代 数 观 点 。Theoretical Computer Science,300(1-3):1[5] 我的朋友,斯特凡·米利厄斯,还有我的朋友,埃莱比尔。 论理性单子和自由迭代理论。 理论计算机科学电子笔记(ENTCS),69:23 -46,2002.[6] J ir'Ad'amek,StefanMilius,andJ ir'Velebil. 自由迭代理论:一个共代数观点. 计算机科学中的数学结构,13(2):259 -320 , 2003 .[7] 我的朋友,斯特凡·米利厄斯,还有我的朋友,埃莱比尔。 Elgot代数计算机科学中的方法,2(5),2006。[8] 丹尼尔·阿曼和塔尔莫·乌斯塔鲁更新monads:共同解释有向容器。在第19次会议的“证明和程序的类型”的摘要书[9] Thorsten Altenkirch,James Chapman,and Tarmo Uustalu.单子不一定是闭函子。在FOSSACS中,计算机科学讲义(Lecture Notes in Computer Science,LNCS)第6014卷,第297-311页。 Springer,2010.[10] Robert Atkey,Neil Ghani,Bart Jacobs,and Patricia Johann.纤维诱导符合预期。在FOSSACS,计算机科学讲义(Lecture Notes in第7213卷,第42Springer,2012.[11] 乔恩贝克分配法律为在研讨会对三元组和分类同源性理论,数学讲义第80卷,第119-140页。施普林格柏林/海德堡,1969年。10.1007/BFb0083084。[12] Venanzio Capretta通过共归纳类型的一般递归。计算机科学中的逻辑方法,1(2),2005。[13] 彼得罗·森恰雷利和尤金尼奥·莫吉。 指称语义学中模块性的句法方法。《范畴理论与计算机科学》,荷兰阿姆斯特丹,1993年。[14] 科恩·克莱森穷人的并发单子。Journal of Functional Programming,9(3):313[15] R.作者声明:Robert Hieb.发动机的延续。Computer Languages,14(2):109-123,1989.[16] 卡尔文·C.斯蒂芬·埃尔戈特布鲁姆和拉尔夫·廷德尔关于有根树的代数结构。J.计算机系统科学,16:362[17] 安杰伊·菲林斯基和克里斯蒂安·斯托夫林关于有效数据类型的归纳推理。函数式编程国际会议(ICFP),第97-110页。ACM,2007年。[18] Steven E. Ganz,Daniel P. Friedman,and Mitchell Wand.蹦床风格。函数式编程国际会议(ICFP),第18-27页。ACM,1999年。[19] NeilGhani,ChristophLüth,Fed
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功