Johan Jeuring
Abstract:
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