Safe Haskell	Safe
Language	Haskell2010

Kleene.Classes

Synopsis

class (BoundedJoinSemiLattice k, Semigroup k, Monoid k) => Kleene c k | k -> c where
oneof :: (Kleene c k, Foldable f) => f c -> k
class Kleene c k => FiniteKleene c k | k -> c where
class Derivate c k | k -> c where
class Match c k | k -> c where
class Match c k => Equivalent c k | k -> c where
class Derivate c k => TransitionMap c k | k -> c where
class Complement c k | k -> c where

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) #
Instance details Defined in Kleene.ERE 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) #
Instance details Defined in Kleene.Monad 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) #
Instance details Defined in Kleene.RE 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) #
Instance details Defined in Kleene.Equiv 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) #
Instance details Defined in Kleene.ERE 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) #
Instance details Defined in Kleene.RE 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) #
Instance details Defined in Kleene.ERE Methods nullable :: ERE c -> Bool # derivate :: c -> ERE c -> ERE c #
(Eq c, Enum c, Bounded c) => Derivate c (M c) #
Instance details Defined in Kleene.Monad Methods nullable :: M c -> Bool # derivate :: c -> M c -> M c #
(Ord c, Enum c, Bounded c) => Derivate c (RE c) #
Instance details Defined in Kleene.RE Methods nullable :: RE c -> Bool # derivate :: c -> RE c -> RE c #
Derivate c (r c) => Derivate c (Equiv r c) #
Instance details Defined in Kleene.Equiv 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) #
Instance details Defined in Kleene.ERE Methods match :: ERE c -> [c] -> Bool #
(Eq c, Enum c, Bounded c) => Match c (M c) #
Instance details Defined in Kleene.Monad Methods match :: M c -> [c] -> Bool #
(Ord c, Enum c, Bounded c) => Match c (RE c) #
Instance details Defined in Kleene.RE 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)
Instance details Defined in Kleene.DFA Methods match :: DFA c -> [c] -> Bool #
Match c (r c) => Match c (Equiv r c) #
Instance details Defined in Kleene.Equiv 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) #
Instance details Defined in Kleene.ERE Methods equivalent :: ERE c -> ERE c -> Bool #
(Ord c, Enum c, Bounded c) => Equivalent c (RE c) #
Instance details Defined in Kleene.RE Methods equivalent :: RE c -> RE c -> Bool #
Equivalent c (r c) => Equivalent c (Equiv r c) #
Instance details Defined in Kleene.Equiv 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) #
Instance details Defined in Kleene.ERE Methods transitionMap :: ERE c -> Map (ERE c) (SF c (ERE c)) #
(Ord c, Enum c, Bounded c) => TransitionMap c (RE c) #
Instance details Defined in Kleene.RE 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) #
Instance details Defined in Kleene.ERE 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]
Instance details Defined in Kleene.DFA Methods complement :: DFA c -> DFA c #
Complement c (r c) => Complement c (Equiv r c) #
Instance details Defined in Kleene.Equiv Methods complement :: Equiv r c -> Equiv r c #