zalgo-0.2.0.0: Z-algorithm implemented on haskell's built-in cons-cell-based lists.

Copyright (C) 2015 mniip BSD3 mniip experimental portable Safe-Inferred Haskell2010

Data.List.Zalgo.Internal

Description

Implementation of the prefix-function on cons-cells.

prefix-function 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 tying-the-knot 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.

Synopsis

# Documentation

data ZState a Source

A state of the Z-function computation. `zTail` points to the tail of the input at the state's position, `zLength` is the value of the prefix-function, and `zPrev` is a reference to the list of `ZState`s starting from position described by `zLength`.

Constructors

 ZState FieldszTail :: [a] zLength :: !Int zPrev :: [ZState a]

data GenericZState i a Source

`ZState` generalized of the number type. `Nothing` represents zero and is used to avoid the `Eq` constraint

Constructors

 GenericZState FieldsgzTail :: [a] gzLength :: Maybe i gzPrev :: [GenericZState i a]

zTraverse :: Eq a => [a] -> [ZState a] Source

O(N). Compute the list of prefix-function 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 prefix-function 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) plus-1's. Compute the list of prefix-function 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) plus-1's. Compute the list of prefix-function states using a given number type and a given equality predicate.