Abstract
A polytypic (or generic) program captures a common pattern of computation over different datatypes by abstracting over the structure of the datatype. Examples of algorithms that can be defined polytypically are equality tests, mapping functions and pretty printers.
A commonly used technique to implement polytypic programming is specialization, where a specialized version of a polytypic function is generated for every datatype it is used at. In this paper we describe an alternative technique that allows polytypic functions to be defined using Haskell’s class system (extended with multi-parameter type classes and functional dependencies). This technique brings the power of polytypic programming inside Haskell allowing us to define a Haskell library of polytypic functions. It also increases our flexibility, reducing the dependency on a polytypic language compiler.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alimarine, A., Plasmeijer, R.: A generic programming extension for Clean. In: Arts, T., Mohnen, M. (eds.) IFL 2002. LNCS, vol. 2312, pp. 168–185. Springer, Heidelberg (2002)
Clarke, D., Löh, A.: Generic haskell, specifically. In: Gibbons, J., Jeuring, J. (eds.) Proceedings of the IFIP TC2 Working Conference on Generic Programming, pp. 21–48. Kluwer, Dordrecht (2003)
Cockett, R., Fukushima, T.: About Charity. Yellow Series Report No. 92/480/18, Dep. of Computer Science, Univ. of Calgary (1992)
Furuse, J.: Generic polymorphism in ML. In: Journées Francophones des Langages Applicatifs (2001)
Hinze, R., Jeuring, J.: Generic Haskell: practice and theory. In: Backhouse, R., Gibbons, J. (eds.) Generic Programming. LNCS, vol. 2793, pp. 1–56. Springer, Heidelberg (2003)
Hinze, R., Peyton Jones, S.: Derivable type classes. In: Hutton, G. (ed.) Proceedings of the 2000 ACM SIGPLAN Haskell Workshop. Electronic Notes in Theoretical Computer Science, vol. 41.1, Elsevier Science, Amsterdam (2001)
Jansson, P.: The WWW home page for polytypic programming. (2003), Available from http://www.cs.chalmers.se/~patrikj/poly/
Jansson, P., Jeuring, J.: PolyP — a polytypic programming language extension. In: POPL 1997, pp. 470–482. ACM Press, New York (1997)
Jansson, P., Jeuring, J.: PolyLib – a polytypic function library. Workshop on Generic Programming, Marstrand, Available from the Polytypic programming WWW, page [7] (June 1998)
Jay, C., Steckler, P.: The functional imperative: shape! In: Hankin, C. (ed.) ESOP 1998. LNCS, vol. 1381, pp. 139–153. Springer, Heidelberg (1998)
Lämmel, R., Peyton Jones, S.: Scrap your boilerplate: a practical design pattern for generic programming. SIGPLAN Not 38(3), 26–37 (2003)
Lämmel, R., Visser, J.: Typed Combinators for Generic Traversal. In: Krishnamurthi, S., Ramakrishnan, C.R. (eds.) PADL 2002. LNCS, vol. 2257, pp. 137–154. Springer, Heidelberg (2002)
Lämmel, R., Visser, J.: Typed Combinators for Generic Traversal. In: Krishnamurthi, S., Ramakrishnan, C.R. (eds.) PADL 2002. LNCS, vol. 2257, pp. 137–154. Springer, Heidelberg (2002)
Norell, U.: Functional generic programming and type theory. Master’s thesis, Computing Science, Chalmers University of Technology (2002), Available from http://www.cs.chalmers.se/~ulfn
Sheard, T.: Generic unification via Two-Level types and parameterized modules. In: ICFP 2001, pp. 86–97 (2001)
Sheard, T., Jones, S.P.: Template meta-programming for Haskell. In: Proceedings of the Haskell workshop, pp. 1–16. ACM Press, New York (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Norell, U., Jansson, P. (2004). Polytypic Programming in Haskell. In: Trinder, P., Michaelson, G.J., Peña, R. (eds) Implementation of Functional Languages. IFL 2003. Lecture Notes in Computer Science, vol 3145. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27861-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-27861-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23727-3
Online ISBN: 978-3-540-27861-0
eBook Packages: Computer ScienceComputer Science (R0)