functional-kmp-0.1.0.0: KMP implemented on haskell's built-in cons-cell-based lists.

Data.List.Kmp

Description

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.

Synopsis

# Documentation

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

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

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

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

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

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] Source

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 Source

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 Source

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] Source

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

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

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