Copyright | (C) 2015 mniip |
---|---|
Maintainer | mniip <mniip@mniip.com> |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Data.List.Zalgo
Description
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.
- zFun :: Eq a => [a] -> [Int]
- isInfixOf :: Eq a => [a] -> [a] -> Bool
- indexOf :: Eq a => [a] -> [a] -> Maybe Int
- zFunBy :: (a -> a -> Bool) -> [a] -> [Int]
- isInfixBy :: (a -> a -> Bool) -> [a] -> [a] -> Bool
- indexBy :: (a -> a -> Bool) -> [a] -> [a] -> Maybe Int
- genericZFun :: (Num i, Eq a) => [a] -> [i]
- 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
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.
zFunBy :: (a -> a -> Bool) -> [a] -> [Int] Source
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 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.
genericZFun :: (Num i, Eq a) => [a] -> [i] Source
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.
genericZFunBy :: Num i => (a -> a -> Bool) -> [a] -> [i] Source