Safe Haskell	Safe
Language	Haskell2010

Kleene.Classes

Synopsis

Documentation

class (BoundedJoinSemiLattice k, Semigroup k, Monoid k) => Kleene c k | k -> c where Source #

Minimal complete definition

char, star

Methods

empty :: k Source #

Empty regex. Doesn't accept anything.

eps :: k Source #

Empty string. Note: different than empty

char :: c -> k Source #

Single character

appends :: [k] -> k Source #

Concatenation.

unions :: [k] -> k Source #

Union.

star :: k -> k Source #

Kleene star

Instances

(Ord c, Enum c, Bounded c) => Kleene c (ERE c) Source #
Methods empty :: ERE c Source # eps :: ERE c Source # char :: c -> ERE c Source # appends :: [ERE c] -> ERE c Source # unions :: [ERE c] -> ERE c Source # star :: ERE c -> ERE c Source #
Kleene c (M c) Source #
Methods empty :: M c Source # eps :: M c Source # char :: c -> M c Source # appends :: [M c] -> M c Source # unions :: [M c] -> M c Source # star :: M c -> M c Source #
(Ord c, Enum c, Bounded c) => Kleene c (RE c) Source #
Methods empty :: RE c Source # eps :: RE c Source # char :: c -> RE c Source # appends :: [RE c] -> RE c Source # unions :: [RE c] -> RE c Source # star :: RE c -> RE c Source #
Kleene c (r c) => Kleene c (Equiv r c) Source #
Methods empty :: Equiv r c Source # eps :: Equiv r c Source # char :: c -> Equiv r c Source # appends :: [Equiv r c] -> Equiv r c Source # unions :: [Equiv r c] -> Equiv r c Source # star :: Equiv r c -> Equiv r c Source #

oneof :: (Kleene c k, Foldable f) => f c -> k Source #

One of the characters.

class Kleene c k => FiniteKleene c k | k -> c where Source #

Minimal complete definition

charRange, fromRSet, anyChar

Methods

everything :: k Source #

Everything. $\Sigma^\star$.

charRange :: c -> c -> k Source #

charRange a z = ^[a-z]$.

fromRSet :: RSet c -> k Source #

Generalisation of charRange.

dot :: c ~ Char => k Source #

.$. Every character except new line \n@.

anyChar :: k Source #

Any character. Note: different than dot!

Instances

(Ord c, Enum c, Bounded c) => FiniteKleene c (ERE c) Source #
Methods everything :: ERE c Source # charRange :: c -> c -> ERE c Source # fromRSet :: RSet c -> ERE c Source # dot :: ERE c Source # anyChar :: ERE c Source #
(Ord c, Enum c, Bounded c) => FiniteKleene c (RE c) Source #
Methods everything :: RE c Source # charRange :: c -> c -> RE c Source # fromRSet :: RSet c -> RE c Source # dot :: RE c Source # anyChar :: RE c Source #

class Derivate c k | k -> c where Source #

Minimal complete definition

nullable, derivate

Methods

nullable :: k -> Bool Source #

Does language contain an empty string?

derivate :: c -> k -> k Source #

Derivative of a language.

Instances

(Ord c, Enum c) => Derivate c (ERE c) Source #
Methods nullable :: ERE c -> Bool Source # derivate :: c -> ERE c -> ERE c Source #
(Eq c, Enum c, Bounded c) => Derivate c (M c) Source #
Methods nullable :: M c -> Bool Source # derivate :: c -> M c -> M c Source #
(Ord c, Enum c, Bounded c) => Derivate c (RE c) Source #
Methods nullable :: RE c -> Bool Source # derivate :: c -> RE c -> RE c Source #
Derivate c (r c) => Derivate c (Equiv r c) Source #
Methods nullable :: Equiv r c -> Bool Source # derivate :: c -> Equiv r c -> Equiv r c Source #

class Match c k | k -> c where Source #

An f can be used to match on the input.

Minimal complete definition

match

Methods

match :: k -> [c] -> Bool Source #

Instances

(Ord c, Enum c) => Match c (ERE c) Source #
Methods match :: ERE c -> [c] -> Bool Source #
(Eq c, Enum c, Bounded c) => Match c (M c) Source #
Methods match :: M c -> [c] -> Bool Source #
(Ord c, Enum c, Bounded c) => Match c (RE c) Source #
Methods match :: RE c -> [c] -> Bool Source #
Ord c => Match c (DFA c) Source #	Run `DFA` on the input. Because we have analysed a language, in some cases we can determine an input without traversing all of the input. That's not the cases with `RE` `match`. `>>>` `let dfa = fromRE $ RE.star "abc"``>>>` `map (match dfa) ["", "abc", "abcabc", "aa", 'a' : 'a' : undefined]`[True,True,True,False,False] Holds: `match` (`fromRE` re) xs == `match` re xs all (match (fromRE r)) $ take 10 $ RE.generate (curry QC.choose) 42 (r :: RE.RE Char)
Methods match :: DFA c -> [c] -> Bool Source #
Match c (r c) => Match c (Equiv r c) Source #
Methods match :: Equiv r c -> [c] -> Bool Source #

class Match c k => Equivalent c k | k -> c where Source #

Equivalence induced by Matches.

Law:

equivalent re1 re2 = forall s. matches re1 s == matches re1 s

Minimal complete definition

equivalent

Methods

equivalent :: k -> k -> Bool Source #

Instances

(Ord c, Enum c, Bounded c) => Equivalent c (ERE c) Source #
Methods equivalent :: ERE c -> ERE c -> Bool Source #
(Ord c, Enum c, Bounded c) => Equivalent c (RE c) Source #
Methods equivalent :: RE c -> RE c -> Bool Source #
Equivalent c (r c) => Equivalent c (Equiv r c) Source #
Methods equivalent :: Equiv r c -> Equiv r c -> Bool Source #

class Derivate c k => TransitionMap c k | k -> c where Source #

Transition map.

Minimal complete definition

transitionMap

Methods

transitionMap :: k -> Map k (SF c k) Source #

Instances

(Ord c, Enum c, Bounded c) => TransitionMap c (ERE c) Source #
Methods transitionMap :: ERE c -> Map (ERE c) (SF c (ERE c)) Source #
(Ord c, Enum c, Bounded c) => TransitionMap c (RE c) Source #
Methods transitionMap :: RE c -> Map (RE c) (SF c (RE c)) Source #

class Complement c k | k -> c where Source #

Complement of the language.

Law:

matches (complement f) xs = not (matches f) xs

Minimal complete definition

complement

Methods

complement :: k -> k Source #

Instances

Complement c (ERE c) Source #
Methods complement :: ERE c -> ERE c Source #
Complement c (DFA c) Source #	Complement DFA. Complement of `DFA` is way easier than of `RE`: complement accept states. `>>>` `let dfa = complement $ fromRE $ RE.star "abc"``>>>` `putPretty dfa`0 -> \x -> if \| x <= '`' -> 3 \| x <= 'a' -> 2 \| otherwise -> 3 1+ -> \x -> if \| x <= 'b' -> 3 \| x <= 'c' -> 0 \| otherwise -> 3 2+ -> \x -> if \| x <= 'a' -> 3 \| x <= 'b' -> 1 \| otherwise -> 3 3+ -> \_ -> 3 -- black hole `>>>` `map (match dfa) ["", "abc", "abcabc", "aa","abca", 'a' : 'a' : undefined]`[False,False,False,True,True,True]
Methods complement :: DFA c -> DFA c Source #
Complement c (r c) => Complement c (Equiv r c) Source #
Methods complement :: Equiv r c -> Equiv r c Source #