Polytypic Pattern Matching

Johan Jeuring


The {exact} pattern matching problem can be informally specified as follows: given a pattern and a text, find all occurrences of the pattern in the text. The pattern and the text may both be lists, or they may both be trees, or they may both be multi-dimensional arrays, etc. This paper describes a general pattern-matching algorithm for all datatypes definable as an initial object in a category of F-algebras, where F is a regular functor. This class of datatypes includes mutual recursive datatypes and lots of different kinds of trees. The algorithm is a generalisation of the Knuth, Morris, Pratt like pattern-matching algorithm on trees first described by Hoffmann and O'Donnell.
Last modified: Tue Aug 17 15:26:20 MET DST 1999 by
Patrik Jansson / NOpatrikjSP@AMchalmers.se