Algorithms.DFA.KMP.Automaton

KMP algorithm implementation based on Deterministic Finite Automaton Automata lpws = the longets suffix which is a prefix length

Documentation

newtype Index

Index to select the DFA states

Constructors

Index Int

Instances

Enum Index

Methods

succ :: Index -> Index

pred :: Index -> Index

toEnum :: Int -> Index

fromEnum :: Index -> Int

enumFrom :: Index -> [Index]

enumFromThen :: Index -> Index -> [Index]

enumFromTo :: Index -> Index -> [Index]

enumFromThenTo :: Index -> Index -> Index -> [Index]

Eq Index

Methods

(==) :: Index -> Index -> Bool

(/=) :: Index -> Index -> Bool

Integral Index

Methods

quot :: Index -> Index -> Index

rem :: Index -> Index -> Index

div :: Index -> Index -> Index

mod :: Index -> Index -> Index

quotRem :: Index -> Index -> (Index, Index)

divMod :: Index -> Index -> (Index, Index)

toInteger :: Index -> Integer

Num Index

Methods

(+) :: Index -> Index -> Index

(-) :: Index -> Index -> Index

(*) :: Index -> Index -> Index

negate :: Index -> Index

abs :: Index -> Index

signum :: Index -> Index

fromInteger :: Integer -> Index

Ord Index

Methods

compare :: Index -> Index -> Ordering

(<) :: Index -> Index -> Bool

(<=) :: Index -> Index -> Bool

(>) :: Index -> Index -> Bool

(>=) :: Index -> Index -> Bool

max :: Index -> Index -> Index

min :: Index -> Index -> Index

Real Index

Methods

toRational :: Index -> Rational

data Jump a

Target of a transition

Constructors

Accept

final state

Hold a

hold on the stream

Step a

step the stream

Instances

Functor Jump

Methods

fmap :: (a -> b) -> Jump a -> Jump b

(<$) :: a -> Jump b -> Jump a

type Process a = a -> Jump (Automaton a)

Machine transition

newtype Automaton a

A wrapper do deal with cycle

Constructors

Automaton (Process a)

data Interface a

API

Constructors

Interface

Fields

• _targets :: [(a, Index)]

  where to go on occurrencies

• _fallback :: Either Index Index

  Left is retake, Right is step ahead

• _accepts :: [a]

  finals, accept states

type Query a = Index -> Automaton a

backend

core

Arguments

:: Eq a

=> Query a

backend

-> Interface a

behavior definition

-> Process a

create a Resolve

run

Arguments

:: Automaton a

initial machine state

-> [a]

stream of input

-> Maybe (Automaton a)

reached machine state

run the automata against a stream . Nothing represent an Accept state

automaton :: Eq a => NonEmpty (Interface a) -> Automaton a

build a Automaton from a pattern zipeed with the prefix