Polytypic pattern matching
Johan T. Jeuring · 1995
The 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.