Copyright  (C) 2015 mniip 

License  BSD3 
Maintainer  mniip <mniip@mniip.com> 
Stability  experimental 
Portability  portable 
Safe Haskell  SafeInferred 
Language  Haskell2010 
Implementation of the prefixfunction on conscells.
prefixfunction 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 tyingtheknot data passing
structure, however no complicated laziness mechanisms are used: a ZState
only depends on previous ZState
s and therefore this algorithm can be safely
implemented in a strict language with pointers.
 data ZState a = ZState {}
 data GenericZState i a = GenericZState {
 gzTail :: [a]
 gzLength :: Maybe i
 gzPrev :: [GenericZState i a]
 zTraverse :: Eq a => [a] > [ZState a]
 zTraverseBy :: (a > a > Bool) > [a] > [ZState a]
 gzTraverse :: (Num i, Eq a) => [a] > [GenericZState i a]
 gzTraverseBy :: Num i => (a > a > Bool) > [a] > [GenericZState i a]
Documentation
data GenericZState i a Source
ZState
generalized of the number type. Nothing
represents zero and is
used to avoid the Eq
constraint
GenericZState  

zTraverse :: Eq a => [a] > [ZState a] Source
O(N). Compute the list of prefixfunction states for a given input.
zTraverseBy :: (a > a > Bool) > [a] > [ZState a] Source
O(N) and O(N) calls to the predicate. Compute the list of prefixfunction states using a given equality predicate. See "Data.List.Zalgo.prefixFunBy" for a detailed explanation of what predicates are allowed.
gzTraverse :: (Num i, Eq a) => [a] > [GenericZState i a] Source
O(N) and O(N) plus1's. Compute the list of prefixfunction states using a given number type.
gzTraverseBy :: Num i => (a > a > Bool) > [a] > [GenericZState i a] Source
O(N), O(N) calls to the predicate, and O(N) plus1's. Compute the list of prefixfunction states using a given number type and a given equality predicate.