Kleene.Classes

Documentation

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

Minimal complete definition

char, star

Methods

empty :: k

Empty regex. Doesn't accept anything.

eps :: k

Empty string. Note: different than empty

char :: c -> k

Single character

appends :: [k] -> k

Concatenation.

unions :: [k] -> k

Union.

star :: k -> k

Kleene star

Instances

(Ord c, Enum c, Bounded c) => Kleene c (ERE c)

Methods

empty :: ERE c

eps :: ERE c

char :: c -> ERE c

appends :: [ERE c] -> ERE c

unions :: [ERE c] -> ERE c

star :: ERE c -> ERE c

Kleene c (M c)

Methods

empty :: M c

eps :: M c

char :: c -> M c

appends :: [M c] -> M c

unions :: [M c] -> M c

star :: M c -> M c

(Ord c, Enum c, Bounded c) => Kleene c (RE c)

Methods

empty :: RE c

eps :: RE c

char :: c -> RE c

appends :: [RE c] -> RE c

unions :: [RE c] -> RE c

star :: RE c -> RE c

Kleene c (r c) => Kleene c (Equiv r c)

Methods

empty :: Equiv r c

eps :: Equiv r c

char :: c -> Equiv r c

appends :: [Equiv r c] -> Equiv r c

unions :: [Equiv r c] -> Equiv r c

star :: Equiv r c -> Equiv r c

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

One of the characters.

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

Minimal complete definition

charRange, fromRSet, anyChar

Methods

everything :: k

Everything. \(\Sigma^\star\).

charRange :: c -> c -> k

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

fromRSet :: RSet c -> k

Generalisation of charRange.

dot :: c ~ Char => k

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

anyChar :: k

Any character. Note: different than dot!

Instances

(Ord c, Enum c, Bounded c) => FiniteKleene c (ERE c)

Methods

everything :: ERE c

charRange :: c -> c -> ERE c

fromRSet :: RSet c -> ERE c

dot :: ERE c

anyChar :: ERE c

(Ord c, Enum c, Bounded c) => FiniteKleene c (RE c)

Methods

everything :: RE c

charRange :: c -> c -> RE c

fromRSet :: RSet c -> RE c

dot :: RE c

anyChar :: RE c

class Derivate c k | k -> c where

Minimal complete definition

nullable, derivate

Methods

nullable :: k -> Bool

Does language contain an empty string?

derivate :: c -> k -> k

Derivative of a language.

Instances

(Ord c, Enum c) => Derivate c (ERE c)

Methods

nullable :: ERE c -> Bool

derivate :: c -> ERE c -> ERE c

(Eq c, Enum c, Bounded c) => Derivate c (M c)

Methods

nullable :: M c -> Bool

derivate :: c -> M c -> M c

(Ord c, Enum c, Bounded c) => Derivate c (RE c)

Methods

nullable :: RE c -> Bool

derivate :: c -> RE c -> RE c

Derivate c (r c) => Derivate c (Equiv r c)

Methods

nullable :: Equiv r c -> Bool

derivate :: c -> Equiv r c -> Equiv r c

class Match c k | k -> c where

An f can be used to match on the input.

Minimal complete definition

match

Methods

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

Instances

(Ord c, Enum c) => Match c (ERE c)

Methods

match :: ERE c -> [c] -> Bool

(Eq c, Enum c, Bounded c) => Match c (M c)

Methods

match :: M c -> [c] -> Bool

(Ord c, Enum c, Bounded c) => Match c (RE c)

Methods

match :: RE c -> [c] -> Bool

Ord c => Match c (DFA c)

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

Match c (r c) => Match c (Equiv r c)

Methods

match :: Equiv r c -> [c] -> Bool

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

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

Instances

(Ord c, Enum c, Bounded c) => Equivalent c (ERE c)

Methods

equivalent :: ERE c -> ERE c -> Bool

(Ord c, Enum c, Bounded c) => Equivalent c (RE c)

Methods

equivalent :: RE c -> RE c -> Bool

Equivalent c (r c) => Equivalent c (Equiv r c)

Methods

equivalent :: Equiv r c -> Equiv r c -> Bool

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

Transition map.

Minimal complete definition

transitionMap

Methods

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

Instances

(Ord c, Enum c, Bounded c) => TransitionMap c (ERE c)

Methods

transitionMap :: ERE c -> Map (ERE c) (SF c (ERE c))

(Ord c, Enum c, Bounded c) => TransitionMap c (RE c)

Methods

transitionMap :: RE c -> Map (RE c) (SF c (RE c))

class Complement c k | k -> c where

Complement of the language.

Law:

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

Minimal complete definition

complement

Methods

complement :: k -> k

Instances

Complement c (ERE c)

Methods

complement :: ERE c -> ERE c

Complement c (DFA c)

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

Complement c (r c) => Complement c (Equiv r c)

Methods

complement :: Equiv r c -> Equiv r c