Combining Datatypes and Effects | SpringerLink
Skip to main content
Springer Nature Link
Log in

Combining Datatypes and Effects

  • Conference paper
Advanced Functional Programming

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3622))

  • 970 Accesses

Abstract

Recursion schemes over datatypes constitute a powerful tool to structure functional programs. Standard schemes, like map and fold, have traditionally been studied in the context of purely-functional programs. In this paper we propose the generalization of well-known recursion schemes with the aim to obtain structuring mechanisms for programs with effects, assuming that effects are modelled by monads. We analyze the definition as well as the algebraic laws associated with the new recursion schemes. The way monads encapsulate effects plays an important role in the definition of the monadic recursion schemes, as it permits to focus on the structure of the recursive programs with effects disregarding the specific details of the effects involved. We illustrate the use of the recursion schemes and their laws with some traversal algorithms on graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abramsky, S., Jung, A.: Domain theory. In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol. 3, pp. 1–168. Clarendon Press, Oxford (1994)

    Google Scholar 

  2. Benton, N., Hughes, J., Moggi, E.: Monads and effects. In: Barthe, G., Dybjer, P., Pinto, L., Saraiva, J. (eds.) APPSEM 2000. LNCS, vol. 2395, p. 42. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  3. Bird, R.: Introduction to Functional Programming using Haskell, 2nd edn. Prentice Hall, UK (1998)

    Google Scholar 

  4. Bird, R.S., de Moor, O.: Algebra of Programming. Prentice Hall, UK (1997)

    MATH  Google Scholar 

  5. Chen, C.-P., Hudak, P.: Rolling Your Own Mutable ADT—A Connection Between Linear Types and Monads. In: 24th Symposium on Principles of Programming Languages, January 1997, pp. 54–66. ACM, New York (1997)

    Google Scholar 

  6. Fokkinga, M.M.: Law and Order in Algorithmics. PhD thesis, Universiteit Twente, The Netherlands (1992)

    Google Scholar 

  7. Fokkinga, M.M.: Monadic maps and folds for arbitrary datatypes. Memoranda Informatica 94-28, University of Twente (June 1994)

    Google Scholar 

  8. Gibbons, J.: Calculating Functional Programs. In: Blackhouse, R., Crole, R.L., Gibbons, J. (eds.) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. LNCS, vol. 2297, pp. 148–203. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  9. Gibbons, J., Jones, G.: The Under-Appreciated Unfold. In: 3rd. International Conference on Functional Programming, September 1998. ACM, New York (1998)

    Google Scholar 

  10. Gill, A.: Cheap Deforestation for Non-strict Functional Languages. PhD thesis, Department of Computing Science, University of Glasgow, UK (1996)

    Google Scholar 

  11. Gill, A., Launchbury, J., Jones, S.P.: A Shortcut to Deforestation. In: Conference on Functional Programming and Computer Architecture (1993)

    Google Scholar 

  12. Hutton, G.: Fold and Unfold for Program Semantics. In: 3rd International Conference on Functional Programming, September 1998. ACM, New York (1998)

    Google Scholar 

  13. Jones, S.P.: Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign language calls in Haskell. In: Engineering theories of software construction, Marktoberdorf Summer School 2000. NATO ASI Series. IOS Press, Amsterdam (2001)

    Google Scholar 

  14. Jones, S.P., Launchbury, J.: Lazy functional state threads. In: Symposium on Programming Language Design and Implementation (PLDI 1994), pp. 24–35. ACM, New York (1994)

    Google Scholar 

  15. King, D.: Functional Programming and Graph Algorithms. PhD thesis, Department of Computing Science, University of Glasgow, UK (March 1996)

    Google Scholar 

  16. King, D., Launchbury, J.: Structuring depth-first search algorithms in Haskell. In: 22nd Symposium on Principles of Programming Languages, pp. 344–354. ACM, New York (1995)

    Google Scholar 

  17. Launchbury, J.: Graph Algorithms with a Functional Flavour. In: Advanced Functional Programming. LNCS, vol. 925. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  18. Meijer, E., Fokkinga, M., Paterson, R.: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. In: Functional Programming Languages and Computer Architecture 1991, August 1991. LNCS, vol. 523. Springer, Heidelberg (1991)

    Google Scholar 

  19. Meijer, E., Hutton, G.: Bananas in space: Extending fold and unfold to exponential types. In: Functional Programming Languages and Computer Architecture 1995, pp. 324–333 (1995)

    Google Scholar 

  20. Meijer, E., Jeuring, J.: Merging Monads and Folds for Functional Programming. In: Advanced Functional Programming. LNCS, vol. 925, pp. 228–266. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  21. Moggi, E.: Notions of Computation and Monads. Information and Computation 93, 55–92 (1991)

    Article  MathSciNet  Google Scholar 

  22. Mulry, P.S.: Lifting Theorems for Kleisli Categories. In: Main, M.G., Melton, A.C., Mislove, M.W., Schmidt, D., Brookes, S.D. (eds.) MFPS 1993. LNCS, vol. 802, pp. 304–319. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

  23. Onoue, Y., Hu, Z., Iwasaki, H., Takeichi, M.: A Calculational Fusion System HYLO. In: IFIP TC 2 Working Conference on Algorithmic Languages and Calculi, Le Bischenberg, France, February 1997, pp. 76–106. Chapman & Hall, Boca Raton (1997)

    Chapter  Google Scholar 

  24. Pardo, A.: A Calculational Approach to Recursive Programs with Effects. PhD thesis, Technische Universität Darmstadt (October 2001)

    Google Scholar 

  25. Pardo, A.: Fusion of Recursive Programs with Computational Effects. Theoretical Computer Science 260, 165–207 (2001)

    Article  MathSciNet  Google Scholar 

  26. Peyton-Jones, S., Wadler, P.: Imperative Functional Programming. In: 20th Annual Symposium on Principles of Programming Languages, Charlotte, North Carolina. ACM, New York (1993)

    Google Scholar 

  27. Takano, A., Meijer, E.: Shortcut to Deforestation in Calculational Form. In: Functional Programming Languages and Computer Architecture 1995 (1995)

    Google Scholar 

  28. Tuijnman, D.: A Categorical Approach to Functional Programming. PhD thesis, Fakultät für Informatik, Universität Ulm, Germany (January 1996)

    Google Scholar 

  29. Wadler, P.: Theorems for free. In: 4th International Conference on Functional Programming and Computer Architecture, London (1989)

    Google Scholar 

  30. Wadler, P.: Deforestation: transforming programs to eliminate trees. Theoretical Computer Science 73, 231–248 (1990)

    Article  MathSciNet  Google Scholar 

  31. Wadler, P.: Monads for functional programming. In: Advanced Functional Programming. LNCS, vol. 925. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Instituto de Computación, Universidad de la República, Julio Herrera y Reissig 565, 11300, Montevideo, Uruguay

    Alberto Pardo

Authors
  1. Alberto Pardo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. of Computer Science, Univ. of Tartu, J. Liivi 2, EE-50409, Tartu, Estonia

    Varmo Vene

  2. Institute of Cybernetics at Tallinn University of Technology, Akadeemia tee 21, EE-12618, Tallinn, Estonia

    Tarmo Uustalu

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Pardo, A. (2005). Combining Datatypes and Effects. In: Vene, V., Uustalu, T. (eds) Advanced Functional Programming. Lecture Notes in Computer Science, vol 3622. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11546382_4

Download citation

  • DOI: https://doi.org/10.1007/11546382_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-28540-3

  • Online ISBN: 978-3-540-31872-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation