Deriving a functional Knuth-Morris-Pratt algorithm by transformation

Masato Takeichi, Yoji Akama

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


We show how a functional program for the Knuth-Morris-Pratt algorithm can be derived from a naive algorithm in a few transformation steps. Included also in an implementation technique for efficient memo-ization. The idea behind the transformation is simple but novel and specific to functional programming; we use partial parametrization of higher-order functions and memo-ization by data structures. Partial parametrization corresponds to precomputation, which is a common optimization technique in procedural programming, and memo-ization is similar to tabulation, which replaces an expensive computation by a simple table lookup. Mathematical reasoning is provided for the transformation rules.

Original languageEnglish
Pages (from-to)522-528
Number of pages7
JournalJournal of Information Processing
Issue number4
Publication statusPublished - 1990


Dive into the research topics of 'Deriving a functional Knuth-Morris-Pratt algorithm by transformation'. Together they form a unique fingerprint.

Cite this