Data.List.Zalgo

License: BSD3 Portability: portable Stability: experimental

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

(z 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

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

_O(N)._ Compute the Z-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.

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

Custom predicates

The '...By' set of functions takes a custom equality predicate, and due to the optimized nature of the algorithm, 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.

_O(N) and O(N) calls to the predicate._ Compute the Z-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 cusom equality predicate.

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

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.

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

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

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