Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T23:18:59.920Z Has data issue: false hasContentIssue false
  • English
  • Français

Categorical semantics for arrows

Part of: JFP Research Articles

Published online by Cambridge University Press:  01 July 2009

BART JACOBS ,
CHRIS HEUNEN  and
ICHIRO HASUO
BART JACOBS
Affiliation:
Institute for Computing and Information Sciences, Radboud University Nijmegen, Postbus 9010, NL-6500 GL Nijmegen, The Netherlands (e-mail: [email protected], [email protected], [email protected])
CHRIS HEUNEN
Affiliation:
Institute for Computing and Information Sciences, Radboud University Nijmegen, Postbus 9010, NL-6500 GL Nijmegen, The Netherlands (e-mail: [email protected], [email protected], [email protected])
ICHIRO HASUO
Affiliation:
Institute for Computing and Information Sciences, Radboud University Nijmegen, Postbus 9010, NL-6500 GL Nijmegen, The Netherlands (e-mail: [email protected], [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Arrows are an extension of the well-established notion of a monad in functional-programming languages. This paper presents several examples and constructions and develops denotational semantics of arrows as monoids in categories of bifunctors Cop × C → C. Observing similarities to monads – which are monoids in categories of endofunctors C → C – it then considers Eilenberg–Moore and Kleisli constructions for arrows. The latter yields Freyd categories, mathematically formulating the folklore claim ‘Arrows are Freyd categories.’

Type
Articles
Information
Journal of Functional Programming , Volume 19 , Issue 3-4 , July 2009 , pp. 403 - 438
Copyright
Copyright © Cambridge University Press 2009

References

Alimarine, A., Smetsers, S., van Weelden, A., van Eekelen, M. & Plasmeijer, R. (2005) There and back again: arrows for invertible programming. In Proceedings of the 2005 ACM SIGPLAN Workshop on Haskell, Haskell '05 (Tallinn, September 2005). ACM Press, pp. 86–97.CrossRefGoogle Scholar
Bénabou, J. (2000) Distributors at work. Lecture notes written by Thomas Streicher. http://www.mathematik.tu-darmstadt.de/~streicher/FIBR/Diwo.pdf.gz (Accessed 4 May 2009).Google Scholar
Benton, N. & Hyland, M. (2003) Traced premonoidal categories, Theoret. Inform. Appl., 37 (4): 273–299.CrossRefGoogle Scholar
Borceux, F. (1994a) Handbook of Categorical Algebra, Volume 1: Basic Category Theory, Encyclopedia of Mathematics and Its Applications, vol. 50. Cambridge University Press.Google Scholar
Borceux, F. (1994b) Handbook of Categorical Algebra, Volume 2: Categories and Structures, Encyclopedia of Mathematics and Its Applications, vol. 51. Cambridge University Press.Google Scholar
Cattani, G. L. & Winskel, G. (2005) Profunctors, open maps and bisimulation, Math. Struct. Comput. Sci., 15 (3): 553–614.CrossRefGoogle Scholar
Day, B. J. (1970) Closed categories of functors. In Reports of the Midwest Category Seminar, Dold, A. & Eckmann, B. (eds), Lecture Notes in Mathematics, vol. 137. Springer, pp. 1–38.Google Scholar
Erkök, L. & Launchbury, J. (2002) A recursive do for Haskell. In Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell, Haskell '02 (Pittsburgh, PA, October 2002). ACM Press, pp. 29–37.CrossRefGoogle Scholar
Freyd, P. J. (1964) Abelian Categories: An Introduction to the Theory of Functors. Harper and Row.Google Scholar
Heunen, C. & Jacobs, B. (2006) Arrows, like monads, are monoids. In Proceedings of the 22nd Annual Conference on Mathematical Foundations of Programming Semantics, MFPS-XXII (Genova, May 2006), Brookes, S. & Mislove, M. (eds), Electronic Notes in Theoretical Computer Science, vol. 158. Elsevier, pp. 219–236.Google Scholar
Hughes, J. (2000) Generalising monads to arrows, Sci. Comput. Program., 37 (1–3): 67–111.CrossRefGoogle Scholar
Hughes, J. (2005) Programming with arrows. In Revised Lectures from 5th International School on Advanced Functional Programming, AFP 2004 (Tartu, August 2004), Vene, V. & Uustalu, T. (eds), Lecture Notes in Computer Science, vol. 3622. Springer, pp. 73–129.Google Scholar
Hyland, J. M. E. (1988) A small complete category, Ann. Pure Appl. Logic, 40 (2): 135–165.CrossRefGoogle Scholar
Jacobs, B. (1999) Categorical Logic and Type Theory, Studies in Logic and the Foundations of Mathematics, vol. 141. North-Holland.Google Scholar
Jacobs, B. (2006) Distributive laws for the coinductive solution of recursive equations. Inform. Comput., 204 (4): 561–587.CrossRefGoogle Scholar
Jacobs, B. & Hasuo, I. (2006) Freyd is Kleisli, for arrows. In Proceedings of the Workshop on Mathematically Structured Functional Programming, MSFP 2006 (Kuressaare, July 2006), McBride, C. & Uustalu, T. (eds), Electronic Workshops in Computing. BCS, article 9.Google Scholar
Kelly, G. M. (1982) Basic Concepts of Enriched Category Theory. London Mathematical Society Lecture Notes Series, vol. 64. Cambridge University Press.Google Scholar
Levy, P. B., Power, J. & Thielecke, H. (2003) Modelling environments in call-by-value programming languages, Inform. Comput., 185 (2): 182–210.CrossRefGoogle Scholar
Li, P. & Zdancewic, S. (2008) Arrows for Secure Information Flow, Technical Report MS-CIS-08-02. School of Computer and Information Sciences, University of Pennsylvania.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5. Springer.CrossRefGoogle Scholar
Moggi, E. (1989) Computational lambda-calculus and monads. In Proceedings of the 4th Annual IEEE Symposium on Logic in Computer Science, LICS '89 (Pacific Grove, CA, June 1989). IEEE CS Press, pp. 14–23.Google Scholar
Paterson, R. (2001) A new notation for arrows. In Proceedings of the 6th ACM SIGPLAN International Conference on Functional Programming, ICFP '01 (Florence, September 2001). ACM Press, pp. 229–240.CrossRefGoogle Scholar
Paterson, R. (2003) Arrows and computation. In The Fun of Programming, Gibbons, J. & de Moor, O. (eds), Cornerstones of Computing. Palgrave MacMillan, pp. 201–222.CrossRefGoogle Scholar
Peyton Jones, S. L. (ed.) (2003) Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press.Google Scholar
Power, J. & Thielecke, H. (1997) Environments, continuation semantics and indexed categories. In Proceedings of the 3rd International Symposium on Theoretical Aspects of Computer Software. TACS '97 (Sendai, September 1997), Abadi, M. & Ito, T. (eds), Lecture Notes in Computer Science, vol. 1281. Springer, pp. 391–414.Google Scholar
Robinson, E. P. & Power, J. (1997) Premonoidal categories and notions of computation, Math. Struct. Comput. Sci., 7 (5): 453–468.Google Scholar
Street, R. (1972) The formal theory of monads, J. Pure Appl. Algebra, 2: 149–169.CrossRefGoogle Scholar
Swierstra, S. D. & Duponcheel, L. (1996) Deterministic, error-correcting combinator parsers. In Tutorial Text from Second International School on Advanced Functional Programming (Olympia, WA, August 1996), Launchbury, J., Meijer, E. & Sheard, T. (eds), Lecture Notes in Computer Science, vol. 1129. Springer, pp. 184–207.Google Scholar
Uustalu, T. & Vene, V. (2005) Signals and comonads, J. Univ. Comput. Sci., 11 (7): 1310–1326.Google Scholar
Vizzotto, J. K., Altenkirch, T. & Sabry, A. (2006) Structuring quantum effects: superoperators as arrows, Math. Struct. Comput. Sci., 16 (3): 453–468.CrossRefGoogle Scholar
Wadler, P. (1993) Monads for functional programming. In Proceedings of the NATO ASI on Program Design Calculi (Marktoberdorf, July/August 1992), Broy, M. (ed.), NATO ASI Series F, vol. 118. Springer, pp. 233–264.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.