Copyright | (C) 2015 mniip |
---|---|

License | BSD3 |

Maintainer | mniip <mniip@mniip.com> |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

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.

- prefixFun :: Eq a => [a] -> [Int]
- isInfixOf :: Eq a => [a] -> [a] -> Bool
- indexOf :: Eq a => [a] -> [a] -> Maybe Int
- prefixFunBy :: (a -> a -> Bool) -> [a] -> [Int]
- isInfixBy :: (a -> a -> Bool) -> [a] -> [a] -> Bool
- indexBy :: (a -> a -> Bool) -> [a] -> [a] -> Maybe Int
- 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

# Documentation

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, 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
cusom 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

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