Data.List.Kmp.Internal

Implementation of the prefix-function on cons-cells.

prefix-function has a simple implementation using arrays, the challenge, however was to implement it on haskell lists (which are cons cells) without losing any complexity. The following code uses a tying-the-knot data passing structure, however no complicated laziness mechanisms are used: a KmpState only depends on previous KmpStates and therefore this algorithm can be safely implemented in a strict language using pointers.

Documentation

data KmpState a

A state of the prefix-function computation. kmpTail points to the tail of the input at the state's position, kmpLength is the value of the prefix-function, and kmpPrev is a reference to the list of KmpStates starting from position described by kmpLength.

Constructors

KmpState

Fields

kmpTail :: [a]

kmpLength :: !Int

kmpPrev :: [KmpState a]

data GenericKmpState i a

KmpState generalized over the number type. Nothing represents zero and is used to avoid the Eq constraint

Constructors

GenericKmpState

Fields

gKmpTail :: [a]

gKmpLength :: Maybe i

gKmpPrev :: [GenericKmpState i a]

kmpTraverse :: Eq a => [a] -> [KmpState a]

O(N). Compute the list of prefix-function states for a given input.

kmpTraverseBy :: (a -> a -> Bool) -> [a] -> [KmpState a]

O(N) and O(N) calls to the predicate. Compute the list of prefix-function states using a given equality predicate. See prefixFunBy for a detailed explanation of what predicates are allowed.

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

O(N) and O(N) plus-1's. Compute the list of prefix-function states using a given number type.

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

O(N), O(N) calls to the predicate, and O(N) plus-1's. Compute the list of prefix-function states using a given number type and a given equality predicate.