Coproducts of Ideal Monads

Neil Ghani; Tarmo Uustalu

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 38, Issue: 4, page 321-342
  • ISSN: 0988-3754

Abstract

top
The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly  [Bull.  Austral. Math. Soc.22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell.2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc.223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads.

How to cite

top

Ghani, Neil, and Uustalu, Tarmo. "Coproducts of Ideal Monads." RAIRO - Theoretical Informatics and Applications 38.4 (2010): 321-342. <http://eudml.org/doc/92746>.

@article{Ghani2010,
abstract = { The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly  [Bull.  Austral. Math. Soc.22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell.2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc.223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads. },
author = {Ghani, Neil, Uustalu, Tarmo},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {monad; ideal monad; coproduct; programming langage},
language = {eng},
month = {3},
number = {4},
pages = {321-342},
publisher = {EDP Sciences},
title = {Coproducts of Ideal Monads},
url = {http://eudml.org/doc/92746},
volume = {38},
year = {2010},
}

TY - JOUR
AU - Ghani, Neil
AU - Uustalu, Tarmo
TI - Coproducts of Ideal Monads
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 38
IS - 4
SP - 321
EP - 342
AB - The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly  [Bull.  Austral. Math. Soc.22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell.2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc.223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads.
LA - eng
KW - monad; ideal monad; coproduct; programming langage
UR - http://eudml.org/doc/92746
ER -

References

top
  1. P. Aczel, J. Adámek, S. Milius and J. Velebil, Infinite trees and completely iterative theories: a coalgebraic view. Theor. Comput. Sci.300 (2003) 1–45.  Zbl1028.68077
  2. J. Adámek, S. Milius and J. Velebil, Free iterative theories: a coalgebraic view. Math. Struct. Comput. Sci.13 (2003) 259–320.  Zbl1030.18004
  3. J. Adámek and J. Rosický, Locally Presentable and Accessible Categories. London Math. Soc. Lect. Note Ser.189 (1994).  Zbl0795.18007
  4. M. Barr, Coequalizers and free triples. Math. Z.116 (1970) 307–322.  Zbl0194.01701
  5. M. Barr and C. Wells, Toposes, Triples and Theories. Grundlehren der mathematischen Wissenschaften275 (1985).  Zbl0567.18001
  6. J. Beck, Distributive laws, in Seminar on Triples and Categorical Homology Theory (ETH, 1966/67), edited by B. Eckmann, Springer-Verlag, Berlin. Lect. Notes Math.80 (1969) 119–140.  
  7. M. Fiore, G. Plotkin and D. Turi, Abstract syntax and variable binding, in Proc. of 14th Ann. IEEE Symp. on Logic in Computer Science, LICS'99, Trento, July 1999, IEEE CS Press, Los Alamitos, CA (1999) 193–202.  
  8. N. Ghani, C. Lüth, F. de Marchi and J. Power, Dualising initial algebras. Math. Struct. Comput. Sci.13 (2003) 349–370.  Zbl1049.18005
  9. N. Ghani, C. Lüth and F. De Marchi, Coalgebraic monads, in Proc. of 5th Wksh. on Coalgebraic Methods in Computer Science, CMCS'02, Grenoble, Apr. 2002, edited by L.S. Moss, Elsevier, Amsterdam. Electr. Notes in Theor. Comput. Sci.65 (2002).  Zbl1270.18011
  10. N. Ghani and T. Uustalu, Explicit substitutions and higher-order syntax, in Proc. of 2nd ACM SIGPLAN Wksh. on Mechanized Reasoning about Languages with Variable Binding, MERLIN'03, Uppsala, Aug. 2003, edited by F. Honsell, M. Miculan, A. Momigliano, ACM Press, New York (2003).  Zbl1105.68021
  11. J.A. Goguen, A categorical manifesto. Math. Struct. Comput. Sci.1 (1991) 49–67.  Zbl0747.18001
  12. M. Hyland, G. Plotkin and J. Power, Combining computational effects: commutativity and sum, in Proc. of IFIP 17th World Computer Congress, TC1 Stream / 2nd IFIP Int. Conf. on Theoretical Computer Science, TCS 2002, Montreal, Aug. 2002, edited by A. Baeza-Yates, U. Montanari, and N. Santoro, Kluwer Academic Publishers, Dordrecht. IFIP Conf. Proc.223 (2002) 474–484.  
  13. C. Jones and G.D. Plotkin, A probabilistic powerdomain of evaluations, in Proc. of 4th Ann. IEEE Symp. Logic in Computer Science, LICS'89, Pacific Grove, CA, June 1989, IEEE CS Press, Washington, DC (1989) 186–195.  Zbl0716.06003
  14. M. Jones and L. Duponcheel, Composing monads,Techn. report RR-1004. Dept. of Comp. Sci. Yale Univ. (1993).  
  15. G.M. Kelly, A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves and so on. Bull. Austral. Math. Soc.22 (1980) 1–83.  Zbl0437.18004
  16. G.M. Kelly and J. Power, Adjunctions whose counits are equalizers, and presentations of finitary monads. J. Pure Appl. Algebra89 (1993) 163–179.  Zbl0779.18003
  17. F.E.J. Linton, Some aspects of equational categories, in Proc. of Conf. on Categorical Algebra, La Jolla, CA, June 1965, edited by S. Eilenberg, D. K. Harrison, S. Mac Lane, H. Röhrl, Springer-Verlag, Berlin (1966) 84–94.  
  18. C. Lüth, Categorical Term Rewriting: Monads and Modularity. Ph.D. Thesis, Lab. for Foundations of Comp. Sci., Univ. of Edinburgh (1998).  
  19. C. Lüth and N. Ghani, Monads and modularity, in Proc. of 4th Int. Wksh. on Frontiers of Combining Systems, FroCoS 2002, Santa Margherita Ligure, Apr. 2002, edited by A. Armando, Springer-Verlag, Berlin. Lect. Notes Artif. Intell.2309 (2002) 18–32.  Zbl1057.68063
  20. C. Lüth and N. Ghani, Monads and modular term rewriting, in Proc. of 7th Int. Conf. on Category Theory in Computer Science, CTCS'97, Santa Margherita Ligure, Sept. 2002, edited by E. Moggi and G. Rosolini, Springer-Verlag, Berlin. Lect. Notes Comput. Sci.1290 (1997) 69–86.  Zbl0889.68084
  21. E.G. Manes, Algebraic Theories. Springer-Verlag, Berlin, Grad. Texts in Math.26 (1976).  Zbl0353.18007
  22. R. Matthes and T. Uustalu, Substitution in non-wellfounded syntax with variable binding, in Proc. of 6th Wksh. on Coalgebraic Methods in Computer Science, CMCS'03, Warsaw, Apr. 2003, edited by H. P. Gumm, Elsevier, Amsterdam. Electr. Notes Theor. Comput. Sci.82 (2003).  Zbl1270.68089
  23. M. Mislove, Nondeterminism and probabilistic choice: obeying the laws, in Proc. 11 Int. Conf. on Concurrency Theory, CONCUR 2000, University Park, PA, Aug. 2000, edited by C. Palamidessi, Springer-Verlag, Berlin. Lect. Notes comput. Sci.1877 (2000) 350–364.  Zbl0999.68147
  24. E. Moggi, Computational lambda-calculus and monads, in Proc. of 4th Ann. IEEE Symp. on Logic in Computer Science, LICS'89, Pacific Grove, CA, June 1989, IEEE CS Press, Washington, DC (1989) 14–23.  Zbl0716.03007
  25. E. Moggi, An abstract view of programming languages. Techn. report ECS-LFCS-90-113, Lab. for Foundations of Comp. Sci., Univ. of Edinburgh (1990).  
  26. L. Moss, Parametric corecursion. Theor. Comput. Sci.260 (2001) 139–163.  Zbl0973.68134
  27. R. Tix, Continuous D-cones: convexity and powerdomain constructions. Ph.D. Thesis, Techn. Univ. Darmstadt (1999).  Zbl0998.68533
  28. D. Varacca, The powerdomain of indexed valuations, in Proc. of 17th Ann. IEEE Symp. on Logic in Computer Science, LICS'02, Copenhagen, July 2002, IEEE CS Press, Los Alamitos, CA (2002) 299–308.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.