Fundamental algorithms for a declarative pattern matching system
S.E. Kurtz · OpenGrey (Institut de l'Information Scientifique et Technique) · 1995
The present thesis provides a systematic and detailed consideration on the embedding of fundamental string algorithms in the functional programming paradigm. In particular, a thorough development and complete implementation of several string searching and comparison algorithms is given applying the structuring methods of functional languages to construct implementations from individual reusable components. A high degree of modularity is achieved by using higher order functions and lazy-evaluation to combine the program components. The lazy functional language Miranda is used for program notation. Based on these language features various forms of A"+-trees have been represented and constructed in a unified way. It is shown that all functional programs achieve the same asymptotic running time as their imperative counterparts. (WEN)