Abstract
We introduce a generalisation of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed λ-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between monads and relative monads. Arrows are also an instance of relative monads.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abbott, M., Altenkirch, T., Ghani, N.: Containers—constructing strictly positive types. Theor. Comput. Sci. 342(1), 3–27 (2005)
Abramsky, S., Coecke, B.: A categorical semantics of quantum protocols. In: Proc. of 19th Ann. IEEE Symp. on Logic in Computer Science, LICS 2004, pp. 415–425. IEEE CS Press, Los Alamitos (2004)
Agda team: Agda (2009), http://appserv.cs.chalmers.se/users/ulfn/wiki/agda.php
Altenkirch, T., Green, A.: The Quantum IO Monad. In: Gay, S., McKie, I. (eds.) Semantic Techniques in Quantum Computation, pp. 173–205. Cambridge Univ. Press, Cambridge (2009)
Altenkirch, T., Reus, B.: Monadic presentations of lambda terms using generalized inductive types. In: Flum, J., Rodríguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol. 1683, pp. 453–468. Springer, Heidelberg (1999)
Fiore, M.: Semantic analysis of normalisation by evaluation for typed lambda calculus. In: Proc. of 4th ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming, PPDP 2002, pp. 26–37. ACM Press, New York (2002)
Fiore, M., Plotkin, G., Turi, D.: Abstract syntax and variable binding. In: Proc. of 14th Ann. IEEE Symp. on Logic in Computer Science, LICS 1999, pp. 193–202. IEEE CS Press, Los Alamitos (1999)
Heunen, C., Jacobs, B.: Arrows, like monads, are monoids. In: Brookes, S., Mislove, M. (eds.) Proc. of 22nd Ann. Conf. on Mathematical Foundations of Programming Semantics, MFPS XXII. Electron. Notes in Theor. Comput. Sci, vol. 158, pp. 219–236. Elsevier, Amsterdam (2006)
Hughes, J.: Generalising monads to arrows. Sci. of Comput. Program. 37(1-3), 67–111 (2000)
Jacobs, B., Heunen, C., Hasuo, I.: Categorical semantics for arrows. J. of Funct. Program. 19(3-4), 403–438 (2009)
Jaskelioff, M.: Lifting of Operations in Modular Monadic Semantics. PhD thesis, University of Nottingham (2009)
Manes, E.G.: Algebraic Theories. Springer, Heidelberg (1976)
McBride, C., Paterson, R.: Applicative programming with effects. J. of Funct. Program. 18(1), 1–13 (2008)
Morris, P., Altenkirch, T.: Indexed containers. In: Proc. of 24th Ann. IEEE Symp. on Logic in Computer Science, LICS 2009, pp. 277–285. IEEE CS Press, Los Alamitos (2009)
Piponi, D.: Commutative monads, diagrams and knots. In: Proc. of 14th Int. Conf. on Functinal Programming, ICFP 2009, p. 231. ACM Press, New York (2009) (see the video)
Power, J., Robinson, E.: Premonoidal categories and notions of computation. Math. Struct. in Comput. Sci. 7(5), 453–468 (1997)
Spivey, J.M.: Algebras for combinatorial search. J. of Funct. Program. 19(3-4), 469–487 (2009)
Uustalu, T., Vene, V.: Comonadic notions of computation. In: Adamék, J., Kupke, C. (eds.) Proc. of 9th Int. Wksh. on Coalgebraic Methods in Computer Science, CMCS 2008. Electron. Notes in Theor. Comput. Sci., vol. 203(5), pp. 263–284. Elsevier, Amsterdam (2008)
Vizzotto, J.K., Altenkirch, T., Sabry, A.: Structuring quantum effects: Superoperators as arrows. Math. Struct. in Comput. Sci. 16(3), 453–468 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Altenkirch, T., Chapman, J., Uustalu, T. (2010). Monads Need Not Be Endofunctors. In: Ong, L. (eds) Foundations of Software Science and Computational Structures. FoSSaCS 2010. Lecture Notes in Computer Science, vol 6014. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12032-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-12032-9_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12031-2
Online ISBN: 978-3-642-12032-9
eBook Packages: Computer ScienceComputer Science (R0)