Polymorphic string matching

Abstract

Calculational developments of functional programs have been likened to conjuring tricks: enjoyable to watch but often a mystery as to how they are done. This pearl explains the trick. The aim is to give new calculations of two famous algorithms in string matching, the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm. The string matching problem is formulated polymorphically, so the only available property of elements of the alphabet is an equality test.