Generic Matching of Tree Regular Expressions over Haskell Data Types

详细信息    查看全文

• 关键词：Tree regular expressions ; Generic programming ; Haskell
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9585
• 期：1
• 页码：83-98
• 全文大小：242 KB
• 参考文献：1.Bagrak, I., Shivers, O.: trx: regular-tree expressions, now in scheme. In: Fifth Workshop on Scheme and Functional Programming (2004)
  2.Broberg, N., Farre, A., Svenningsson, J.: Regular expression patterns. In: Proceedings of the Ninth ACM SIGPLAN International Conference on Functional Programming. ICFP 2004, pp. 67–78. ACM, New York (2004)
  3.Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications, release October, 12th 2007 (2007). http://​www.​grappa.​univ-lille3.​fr/​tata
  4.Fähndrich, M., Boyland, J.: Statically checkable pattern abstractions. In: Jones, S.L.P., Tofte, M., Berman, A.M. (eds.) Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming (ICFP 1997), Amsterdam, The Netherlands, 9–11 June 1997, pp. 75–84. ACM (1997)
  5.Leroy, X., Doligez, D., Frisch, A., Garrigue, J., Rémy, D., Vouillon, J.: The OCaml system release 4.02. http://​caml.​inria.​fr/​pub/​docs/​manual-ocaml/​
  6.Magalhães, J.P., Dijkstra, A., Jeuring, J., Löh, A.: A generic deriving mechanism for Haskell. In: Proceedings of the Third ACM Haskell Symposium on Haskell, Haskell 2010, pp. 37–48. ACM, New York (2010)
  7.Marlow, S.: An extensible dynamically-typed hierarchy of exceptions. In: Haskell 2006: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell
  8.Marlow, S., et al.: Haskell 2010 language report. https://​www.​haskell.​org/​onlinereport/​haskell2010/​
  9.Van Noort, T., Rodriguez, A., Holdermans, S., Jeuring, J., Heeren, B.: A lightweight approach to datatype-generic rewriting. In: Proceedings of the ACM SIGPLAN Workshop on Generic Programming, WGP 2008, pp. 13–24. ACM, New York (2008)
  10.Pfenning, F., Elliott, C.: Higher-order abstract syntax. SIGPLAN Not. 23(7), 199–208 (1988)CrossRef
  11.Rhiger, M.: Type-safe pattern combinators. J. Funct. Programm. 19(2), 145–156 (2009)CrossRef MATH
  12.Sheard, T., Peyton Jones, S.: Template meta-programming for Haskell. SIGPLAN Not. 37(12), 60–75 (2002)CrossRef
  
• 作者单位：Alejandro Serrano (15)
  Jurriaan Hage (15)
  
  15. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
  
• 丛书名：Practical Aspects of Declarative Languages
• ISBN：978-3-319-28228-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Tree regular expressions are a generalization of string regular expressions to tree-shaped data. In this paper we apply the theory of tree regular expressions to extend pattern matching on Haskell data types. We define the operations in a data type-generic way, looking at data types as fixed-points of pattern functors and using the Generic implementation available in the GHC Haskell compiler.