Data.List.Kmp

A few efficient list-processing functions using the prefix-function, which is defined as:

(prefixFun xs) !! i

is the length of the largest proper substring of xs ending at position i, such that it equals the beginning of xs.

For example:

.-----.             .-----.
a b a c a b a a a b a b a c d
0 0 1 0 1 2 3 1 1 2 3 2 3 4 0
                          ^

The marked substrings are equal, hence the value at the marked location is their length, 4.

Documentation

prefixFun :: Eq a => [a] -> [Int]

O(N). Compute the prefix-function for a list.

isInfixOf :: Eq a => [a] -> [a] -> Bool

O(N+H). isInfixOf needle haystack tests whether needle is fully contained somewhere in haystack.

indexOf :: Eq a => [a] -> [a] -> Maybe Int

O(N+H). indexOf needle haystack returns the index at which needle is found in haystack, or Nothing if it's not.

Custom predicates

The ...By set of functions takes a custom equality predicate, and due to the optimized nature of the algorithm, the passed predicate must conform to some laws:

Commutativity: a == b  =>  b == a
Inverse commutativity: a /= b  =>  b /= a
Transitivity: a == b and b == c  =>  a == c
Inverse transitivity: a == b and b /= c  =>  a /= c

If these laws do not hold, the behavior is undefined.

prefixFunBy :: (a -> a -> Bool) -> [a] -> [Int]

O(N) and O(N) calls to the predicate. Compute the prefix-function using a custom equality predicate.

isInfixBy :: (a -> a -> Bool) -> [a] -> [a] -> Bool

O(N+H) and O(N+H) calls to the predicate. Compute isInfixOf using a custom equality predicate.

indexBy :: (a -> a -> Bool) -> [a] -> [a] -> Maybe Int

O(N+H) and O(N+H) calls to the predicate. Compute indexOf using a custom equality predicate.

Generic functions

Some of the functions are generalized over the type of the numbers they return, but keep in mind that the amount of arithmetic operations is linear.

genericPrefixFun :: (Num i, Eq a) => [a] -> [i]

genericIndexOf :: (Eq i, Num i, Eq a) => [a] -> [a] -> Maybe i

genericPrefixFunBy :: Num i => (a -> a -> Bool) -> [a] -> [i]

genericIndexBy :: (Eq i, Num i) => (a -> a -> Bool) -> [a] -> [a] -> Maybe i