kleene-0.1: Kleene algebra

Safe HaskellSafe
LanguageHaskell2010

Kleene.Classes

Synopsis

Documentation

class Kleene k where Source #

Kleene algebra.

If k is Monoid it's expected that appends = mappend; if k is Lattice it's expected that unions = joins.

Wikipedia: Kleene Algebra.

Methods

empty :: k Source #

Empty regex. Doesn't accept anything.

eps :: k Source #

Empty string. Note: different than empty.

appends :: [k] -> k Source #

Concatenation.

unions :: [k] -> k Source #

Union.

star :: k -> k Source #

Kleene star.

Instances
(Ord c, Enum c, Bounded c) => Kleene (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

empty :: RE c Source #

eps :: RE c Source #

appends :: [RE c] -> RE c Source #

unions :: [RE c] -> RE c Source #

star :: RE c -> RE c Source #

(Ord c, Enum c, Bounded c) => Kleene (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

empty :: ERE c Source #

eps :: ERE c Source #

appends :: [ERE c] -> ERE c Source #

unions :: [ERE c] -> ERE c Source #

star :: ERE c -> ERE c Source #

Kleene (M c) Source # 
Instance details

Defined in Kleene.Monad

Methods

empty :: M c Source #

eps :: M c Source #

appends :: [M c] -> M c Source #

unions :: [M c] -> M c Source #

star :: M c -> M c Source #

Kleene (r c) => Kleene (Equiv r c) Source # 
Instance details

Defined in Kleene.Equiv

Methods

empty :: Equiv r c Source #

eps :: 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 #

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

Minimal complete definition

char

Methods

char :: c -> k Source #

Single character

string :: [c] -> k Source #

Instances
(Ord c, Enum c, Bounded c) => CharKleene c (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

char :: c -> RE c Source #

string :: [c] -> RE c Source #

(Ord c, Enum c, Bounded c) => CharKleene c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

char :: c -> ERE c Source #

string :: [c] -> ERE c Source #

CharKleene c (M c) Source # 
Instance details

Defined in Kleene.Monad

Methods

char :: c -> M c Source #

string :: [c] -> M c Source #

CharKleene c (r c) => CharKleene c (Equiv r c) Source # 
Instance details

Defined in Kleene.Equiv

Methods

char :: c -> Equiv r c Source #

string :: [c] -> Equiv r c Source #

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

One of the characters.

class CharKleene 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!

notChar :: c -> k Source #

notChar :: (Ord c, Enum c, Bounded c) => c -> k Source #

Instances
(Ord c, Enum c, Bounded c) => FiniteKleene c (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

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 #

notChar :: c -> RE c Source #

(Ord c, Enum c, Bounded c) => FiniteKleene c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

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 #

notChar :: c -> ERE c Source #

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

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, Bounded c) => Derivate c (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

nullable :: RE c -> Bool Source #

derivate :: c -> RE c -> RE c Source #

(Ord c, Enum c) => Derivate c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

nullable :: ERE c -> Bool Source #

derivate :: c -> ERE c -> ERE c Source #

Ord c => Derivate c (DFA c) Source # 
Instance details

Defined in Kleene.DFA

Methods

nullable :: DFA c -> Bool Source #

derivate :: c -> DFA c -> DFA c Source #

(Eq c, Enum c, Bounded c) => Derivate c (M c) Source # 
Instance details

Defined in Kleene.Monad

Methods

nullable :: M c -> Bool Source #

derivate :: c -> M c -> M c Source #

Derivate c (r c) => Derivate c (Equiv r c) Source # 
Instance details

Defined in Kleene.Equiv

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 #

match8 :: c ~ Word8 => k -> ByteString -> Bool Source #

Instances
(Ord c, Enum c, Bounded c) => Match c (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

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

match8 :: RE c -> ByteString -> Bool Source #

(Ord c, Enum c) => Match c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

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

match8 :: ERE c -> ByteString -> 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 a result 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)
Instance details

Defined in Kleene.DFA

Methods

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

match8 :: DFA c -> ByteString -> Bool Source #

(Eq c, Enum c, Bounded c) => Match c (M c) Source # 
Instance details

Defined in Kleene.Monad

Methods

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

match8 :: M c -> ByteString -> Bool Source #

Match c (r c) => Match c (Equiv r c) Source # 
Instance details

Defined in Kleene.Equiv

Methods

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

match8 :: Equiv r c -> ByteString -> Bool Source #

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

Equivalence induced by Match.

Law:

equivalent re1 re2 = forall s. match re1 s == match re1 s

Methods

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

Instances
(Ord c, Enum c, Bounded c) => Equivalent c (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

equivalent :: RE c -> RE c -> Bool Source #

(Ord c, Enum c, Bounded c) => Equivalent c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

equivalent :: ERE c -> ERE c -> Bool Source #

Equivalent c (r c) => Equivalent c (Equiv r c) Source # 
Instance details

Defined in Kleene.Equiv

Methods

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

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

Transition map.

Methods

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

Instances
(Ord c, Enum c, Bounded c) => TransitionMap c (RE c) Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

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

(Ord c, Enum c, Bounded c) => TransitionMap c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

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

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

Complement of the language.

Law:

match (complement f) xs = not (match f) xs

Methods

complement :: k -> k Source #

Instances
Complement c (ERE c) Source # 
Instance details

Defined in Kleene.ERE

Methods

complement :: ERE c -> ERE c Source #

(Ord c, Enum c, Bounded c) => Complement c (RE c) Source # 
Instance details

Defined in Kleene.DFA

Methods

complement :: RE c -> RE 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]
Instance details

Defined in Kleene.DFA

Methods

complement :: DFA c -> DFA c Source #

Complement c (r c) => Complement c (Equiv r c) Source # 
Instance details

Defined in Kleene.Equiv

Methods

complement :: Equiv r c -> Equiv r c Source #

class ToLatin1 k where Source #

Methods

toLatin1 :: k Char -> k Word8 Source #

Instances
ToLatin1 RSet Source # 
Instance details

Defined in Kleene.Classes

Methods

toLatin1 :: RSet Char -> RSet Word8 Source #

ToLatin1 RE Source # 
Instance details

Defined in Kleene.Internal.RE

Methods

toLatin1 :: RE Char -> RE Word8 Source #

ToLatin1 ERE Source # 
Instance details

Defined in Kleene.ERE

Methods

toLatin1 :: ERE Char -> ERE Word8 Source #