RepLib: a library for derivable type classes

ABSTRACT

Some type class instances can be automatically derived from the structure of types. As a result, the Haskell language includes the "deriving" mechanism to automatic generates such instances for a small number of built-in type classes. In this paper, we present RepLib, a GHC library that enables a similar mechanism for arbitrary type classes. Users of RepLib can define the relationship between the structure of a datatype and the associated instance declaration by a normal Haskell functions that pattern-matches a representation type. Furthermore, operations defined in this manner are extensible-instances for specific types not defined by type structure may also be incorporated. Finally, this library also supports the definition of operations defined by parameterized types.

REFERENCES

• 1: Martín Abadi , Luca Cardelli , Benjamin Pierce , Gordon Plotkin, Dynamic typing in a statically typed language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.237-268, April 1991 [doi>10.1145/103135.103138]
• 2: James Cheney and Ralf Hinze. First-class phantom types. CUCIS TR2003-1901, Cornell University, 2003.
• 3: Dave Clarke, Ralf Hinze, Johan Jeuring, Andres Löh, and Jan de Wit. The Generic Haskell user's guide. Technical Report UU-CS-2001-26, Utrecht University, 2001.
• 4: Karl Crary , Stephanie Weirich , Greg Morrisett, Intensional polymorphism in type-erasure semantics, Journal of Functional Programming, v.12 n.6, p.567-600, November 2002 [doi>10.1017/S0956796801004282]
• 5: Bruno C. d. S. Oliveira , Jeremy Gibbons, TypeCase: a design pattern for type-indexed functions, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.98-109, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088358]
• 6: DrIFT User Manual, April 2006. Available at http://repetae.net/~john/computer/haskell/DrIFT/.
• 7: The GHC Team. The Glasgow Haskell Compiler User's Guide, version 5.02 edition, 2002. Available at http://www.haskell.org/ghc/.
• 8: Cordelia V. Hall , Kevin Hammond , Simon L. Peyton Jones , Philip L. Wadler, Type classes in Haskell, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.109-138, March 1996 [doi>10.1145/227699.227700]
• 9: Ralf Hinze, Polytypic Values Possess Polykinded Types, Proceedings of the 5th International Conference on Mathematics of Program Construction, p.2-27, July 03-05, 2000
• 10: Ralf Hinze, Generics for the masses, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 11: Ralf Hinze and Simon Peyton Jones. Derivable type classes. In Graham Hutton, editor, Proceedings of the Fourth Haskell Workshop, Montreal, Canada, September 17, 2000, volume 41.1 of Electronic Notes in Theoretical Computer Science. Elsevier Science, August 2000.
• 12: Ralf Hinze and Andres Löh. Scrap Your Boilerplate revolutions. In 8th International Conference on Mathematics of Program Construction, MPC 2006, Kuressaare, Estonia, July 2006.
• 13: Ralf Hinze, Andres Löh, and Bruno C. d. S. Oliveira. Scrap Your Boilerplate reloaded. In Eighth International Symposium on Functional and Logic Programming, FLOPS 2006, April 2005.
• 14: Ralf Hinze, Andres Löh, and Bruno C. d. S. Oliveira. Scrap Your Boilerplate reloaded (extended version). Technical report, 2005. Available at http://www.informatik.uni-bonn.de/~loeh/SYB0-TR.pdf.
• 15: Ralf Hinze and Simon Peyton Jones. Derivable type classes. In Graham Hutton, editor, Proceedings of the 2000 Haskell Workshop, Montreal, number NOTTCS-TR-00-1 in Technical Reports, September 2000.
• 16: Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriguez. Generic views on data types. In 8th International Conference on Mathematics of Program Construction, MPC 2006, Kuressaare, Estonia, July 2006.
• 17: John Hughes. Restricted datatypes in Haskell. In Haskell Workshop, number UU-CS-1999-28, 1999.
• 18: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 19: Wolfram Kahl and Jan Scheffczyk. Named instances for haskell type classes. In Haskell Workshop 2001, Firenze, Italy, September 2001.
• 20: Oleg Kiselyov , Ralf Lämmel , Keean Schupke, Strongly typed heterogeneous collections, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017488]
• 21: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate: a practical design pattern for generic programming, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 22: Ralf Lämmel , Simon Peyton Jones, Scrap more boilerplate: reflection, zips, and generalised casts, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 23: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate with class: extensible generic functions, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 24: Andres Löh , Dave Clarke , Johan Jeuring, Dependency-style generic haskell, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.141-152, August 25-29, 2003, Uppsala, Sweden
• 25: Erik Meijer , Graham Hutton, Bananas in space: extending fold and unfold to exponential types, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.324-333, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224225]
• 26: Martin Odersky , Konstantin Läufer, Putting type annotations to work, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.54-67, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237729]
• 27: Bruno C.d.S. Oliveira, Ralf Hinze, and Andres Löh. Generics as a library. In Seventh Symposium on Trends in Functional Programming, TFP 2006, Nottingham, UK, April 2006.
• 28: Simon Peyton Jones , Dimitrios Vytiniotis , Stephanie Weirich , Geoffrey Washburn, Simple unification-based type inference for GADTs, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 29: Simon L. Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Mark Shields. Practical type inference for arbitrary-rank types. Journal of Functional Programming, 2006. To appear.
• 30: Tim Sheard , Simon Peyton Jones, Template meta-programming for Haskell, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.1-16, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581691]
• 31: Mark Shields and Simon Peyton Jones. Lexically scoped type variables. Microsoft Research, 2002.
• 32: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 33: Geoffrey Washburn , Stephanie Weirich, Good advice for type-directed programming aspect-oriented programming and extensible generic functions, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159867]
• 34: Stephanie Weirich, Encoding Intensional Type Analysis, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.92-106, April 02-06, 2001
• 35: Stephanie Weirich, Higher-Order Intensional Type Analysis, Proceedings of the 11th European Symposium on Programming Languages and Systems, p.98-114, April 08-12, 2002
• 36: Stephanie Claudene Weirich , Greg Morrisett, Programming with types, 2002
• 37: Stephanie Weirich. Higher-order intensional type analysis in type erasure semantics, July 2003. At http://www.cis.upenn.edu/ ~sweirich/papers/erasure/erasure-paper-july03.pdf.
• 38: Stephanie Weirich, Type-FUNCTIONAL PEARL safe cast, Journal of Functional Programming, v.14 n.6, p.681-695, November 2004 [doi>10.1017/S0956796804005179]
• 39: Stephanie Weirich, Type-safe run-time polytypic programming, Journal of Functional Programming, v.16 n.6, p.681-710, November 2006 [doi>10.1017/S0956796806005879]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Design, Languages

Keywords:
GADT, datatype-generic programming, representation types, type-indexed programming