Copyright	(C) 2015 mniip
License	BSD3
Maintainer	mniip <mniip@mniip.com>
Stability	experimental
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Data.List.Kmp

Contents

Custom predicates
Generic functions

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