Regular expression patterns

ABSTRACT

We extend Haskell with regular expression patterns. Regular expression patterns provide means for matching and extracting data which goes well beyond ordinary pattern matching as found in Haskell. It has proven useful for string manipulation and for processing structured data such as XML. Regular expression patterns can be used with arbitrary lists, and work seamlessly together with ordinary pattern matching in Haskell. Our extension is lightweight, it is little more than syntactic sugar. We present a semantics and a type system, and show how to implement it as a preprocessor to Haskell.

REFERENCES

• 1: Lennart Augustsson, Compiling pattern matching, Proc. of a conference on Functional programming languages and computer architecture, p.368-381, January 1985, Nancy, France
• 2: Véronique Benzaken , Giuseppe Castagna , Alain Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.51-63, August 25-29, 2003, Uppsala, Sweden
• 3: Martin Erwig and Simon Peyton Jones. Pattern Guards and Transformational Patterns. In Haskell Workshop, 2000.
• 4: Karl-Filip Faxén, A static semantics for Haskell, Journal of Functional Programming, v.12 n.5, p.295-357, July 2002 [doi>10.1017/S0956796802004380]
• 5: A. Frisch. Regular Tree Language Recognition with Static Information. In 3rd IFIP International Conference on Theoretical Computer Science, 2004.
• 6: Haruo Hosoya and Makoto Murata. Boolean Operations and Inclusion Test for Attribute-Element Constraints. In Eighth International Conference on Implementation and Application of Automata, volume 2759 of Lecture Notes in Computer Science, pages 201--212. Springer-Verlag, 2003.
• 7: Haruo Hosoya , Benjamin C. Pierce, XDuce: A statically typed XML processing language, ACM Transactions on Internet Technology (TOIT), v.3 n.2, p.117-148, May 2003 [doi>10.1145/767193.767195]
• 8: Haruo Hosoya , Jérôme Vouillon , Benjamin C. Pierce, Regular expression types for XML, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.11-22, September 2000
• 9: Michael Y. Levin, Compiling regular patterns, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.65-77, August 25-29, 2003, Uppsala, Sweden
• 10: Kenny Zhuo Ming Lu and Martin Sulzmann. XHaskell: Regular Expression Types for Haskell. http://www.comp.nus.edu.sg/ sulzmann/, 2004.
• 11: Luc Maranget, Compiling lazy pattern matching, Proceedings of the 1992 ACM conference on LISP and functional programming, p.21-31, June 22-24, 1992, San Francisco, California, United States
• 12: Luc Maranget. Two Techniques for Compiling Lazy Pattern Matching. Research report 2385, INRIA, 1994.
• 13: Erik Meijer and Mark Shields. XM : A Functional Language for Constructing and Manipulating XML Documents. (Draft), 1999.
• 14: Erik Meijer and Danny van Velzen. Haskell Server Pages. In Graham Hutton, editor, Electronic Notes in Theoretical Computer Science, volume 41. Elsevier, 2001.
• 15: www.perl.org.
• 16: Martin Odersky et.al. The Scala Programming Language. http://scala.epfl.ch/.
• 17: Philip Wadler. The Implementation of Functional Programming Languages, chapter Efficient Compilation of Pattern Matching. Prentice Hall, 1987.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Patterns

General Terms:
Languages

Keywords:
haskell, pattern matching, regular expressions