Uniform boilerplate and list processing

ABSTRACT

Generic traversals over recursive data structures are often referred to as boilerplate code. The definitions of functions involving such traversals may repeat very similar patterns, but with variations for different data types and different functionality. Libraries of operations abstracting away boilerplate code typically rely on elaborate types to make operations generic. The motivating observation for this paper is that most traversals have value-specific behaviour for just one type. We present the design of a new library exploiting this assumption. Our library allows concise expression of traversals with competitive performance.

REFERENCES

• 1: Björn Bringert , Aarne Ranta, A pattern for almost compositional functions, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 2: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000
• 3: Dimitry Golubovsky, Neil Mitchell, and Matthew Naylor. Yhc.Core - from Haskell to Core. The Monad.Reader, (7):45--61, April 2007.
• 4: 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
• 5: Ralf Hinze and Johan Jeuring. Generic Haskell: Practice and theory. In Summer School on Generic Programming, volume 2793 of LNCS, pages 1--56. Springer-Verlang, 2003.
• 6: Mark P. Jones, Type Classes with Functional Dependencies, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.230-244, April 02, 2000
• 7: Ralf Lämmel , Joost Visser, A Strafunski Application Letter, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.357-375, January 13-14, 2003
• 8: Ralf Lämmel. The sketch of a polymorphic symphony. In Proc. of International Workshop on Reduction Strategies in Rewriting and Programming(WRS 2002), volume 70 of ENTCS. Elsevier Science, 2002.
• 9: Ralf Lämmel. Typed generic traversal with term rewriting strategies. Journal of Logic and Algebraic Programming, 54:1--64, 2003.
• 10: 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
• 11: 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
• 12: 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
• 13: Conor Mcbride , Ross Paterson, Applicative programming with effects, Journal of Functional Programming, v.18 n.1, p.1-13, January 2008 [doi>10.1017/S0956796807006326]
• 14: Lambert G. L. T. Meertens. Paramorphisms. Formal Aspects of Computing, 4(5):413--424, 1992.
• 15: Neil Mitchell and Stefan O'Rear. Derive - project home page. http://www.cs.york.ac.uk/~ndm/derive/, March 2007.
• 16: Neil Mitchell and Colin Runciman. A static checker for safe pattern matching in Haskell. In Trends in Functional Programming (2005 Symposium), volume 6, pages 15--30. Intellect, 2007.
• 17: Markus Mohnen, Context Patterns in Haskell, Selected Papers from the 8th International Workshop on Implementation of Functional Languages, p.41-57, September 16-18, 1996
• 18: Matthew Naylor , Colin Runciman, Finding Inputs that Reach a Target Expression, Proceedings of the Seventh IEEE International Working Conference on Source Code Analysis and Manipulation, p.133-142, September 30-October 01, 2007 [doi>10.1109/SCAM.2007.11]
• 19: Simon Peyton-Jones, Andrew Tolmach, and Tony Hoare. Playing by the rules: Rewriting as a practical optimisation technique in GHC. In Proc. Haskell '01, pages 203--233. ACM Press, 2001.
• 20: 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
• 21: Deling Ren , Martin Erwig, A generic recursion toolbox for Haskell or: scrap your boilerplate systematically, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159845]
• 22: 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]
• 23: Eelco Visser. Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9. In Domain-Specific Program Generation, volume 3016 of LNCS, pages 216--238. Spinger-Verlag, June 2004.
• 24: Philip Wadler. List comprehensions. In Simon Peyton Jones, editor, Implementation of Functional Programming Languages. Prentice Hall, 1987.
• 25: Stephanie Weirich, RepLib: a library for derivable type classes, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159844]
• 26: Noel Winstanley. Reflections on instance derivation. In 1997 Glasgow Workshop on Functional Programming. BCS Workshops in Computer Science, September 1997.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Languages, Performance