Safe Haskell	Safe
Language	Haskell2010

Kleene

Contents

Regular expressions
Equivalence (and partial order)
Deterministic finite automaton
Classes
Functor

Description

Kleene algebra.

This package provides means to work with kleene algebra, at the moment specifically concentrating on regular expressions over Char.

Implements ideas from Regular-expression derivatives re-examined by Scott Owens, John Reppy and Aaron Turon https://doi.org/10.1017/S0956796808007090.

>>> :set -XOverloadedStrings
>>> import Algebra.Lattice
>>> import Algebra.PartialOrd
>>> import Data.Semigroup
>>> import Kleene.Internal.Pretty (putPretty)

Kleene.RE module provides RE type. Kleene.Classes module provides various classes to work with the type. All of that is re-exported from Kleene module.

First let's construct a regular expression value:

>>> let re = star "abc" <> "def" <> ("x" \/ "yz") :: RE Char
>>> putPretty re
^(abc)*def(x|yz)$

We can convert it to DFA (there are 8 states)

>>> let dfa = fromTM re
>>> putPretty dfa
0 -> \x -> if
    | x <= '`'  -> 8
    | x <= 'a'  -> 5
    | x <= 'c'  -> 8
    | x <= 'd'  -> 3
    | otherwise -> 8
1 -> \x -> if
    | x <= 'w'  -> 8
    | x <= 'x'  -> 6
    | x <= 'y'  -> 7
    | otherwise -> 8
2 -> ...
...

It's also possible to graphically visualise DFAs

λ> writeFile "example.dot' (toDot dfa)
%  dot -Tpng -oexample.png example.dot

And we can convert back from DFA to RE:

>>> let re' = toKleene dfa :: RE Char
>>> putPretty re'
^(a(bca)*bcdefx|defx|(a(bca)*bcdefy|defy)z)$

As you see, we don't get what we started with. Yet, these regular expressions are equivalent;

>>> equivalent re re'
True

or using Equiv wrapper

>>> Equiv re == Equiv re'
True

(The paper doesn't outline decision procedure for the equivalence, though it's right there - seems to be fast enough at least for toy examples like here).

We can use regular expressions to generate word examples in the language:

>>> import Data.Foldable
>>> import qualified Test.QuickCheck as QC
>>> import Kleene.RE (generate)

>>> traverse_ print $ take 5 $ generate (curry QC.choose) 42 re
"abcdefx"
"abcabcdefx"
"abcdefyz"
"abcabcabcabcabcabcabcdefyz"
"abcabcabcabcabcabcabcdefyz"

In addition to the "normal" regular expressions, there are extended regular expressions. Regular expressions which we can complement, and therefore intersect:

>>> let ere = star "aa" /\ star "aaa" :: ERE Char
>>> putPretty ere
^~(~((aa)*)|~((aaa)*))$

We can convert ERE to RE via DFA:

>>> let re'' = toKleene (fromTM ere) :: RE Char
>>> putPretty re''
^(a(aaaaaa)*aaaaa)?$

Machine works own ways, we don't (always) get as pretty results as we'd like:

>>> equivalent re'' (star "aaaaaa")
True

Another feature of the library is an Applciative Functor,

>>> import Control.Applicative
>>> import qualified Kleene.Functor as F

>>> let f = (,) <$> many (F.char 'x') <* F.few F.anyChar <*> many (F.char 'z')
>>> putPretty f
^x*[^]*z*$

By relying on http://hackage.haskell.org/package/regex-applicative library, we can match and capture with regular expression.

>>> F.match f "xyyzzz"
Just ("x","zzz")

Where with RE we can only get True or False:

>>> match (F.toRE f) "xyyzzz"
True

Which in this case is not even interesting because:

>>> equivalent (F.toRE f) everything
True

Converting from RE to K is also possible, which may be handy:

>>> let g = (,) <$> F.few F.anyChar <*> F.fromRE re''
>>> putPretty g
^[^]*(a(aaaaaa)*aaaaa)?$

>>> F.match g (replicate 20 'a')
Just ("aa","aaaaaaaaaaaaaaaaaa")

We got longest divisible by 6 prefix of as. That's because fromRE uses many for star.

Synopsis

data RE c
data ERE c
newtype Equiv (r :: Type -> Type) c = Equiv (r c)
data DFA c = DFA {
- dfaTransition :: !(IntMap (SF c Int))
- dfaInitial :: !Int
- dfaAcceptable :: !IntSet
- dfaBlackholes :: !IntSet
}
fromTM :: (Ord k, Ord c, TransitionMap c k) => k -> DFA c
fromTMEquiv :: (Ord k, Ord c, TransitionMap c k, Equivalent c k) => k -> DFA c
toKleene :: forall k c. (Ord c, Enum c, Bounded c, FiniteKleene c k) => DFA c -> k
toDot :: DFA Char -> String
class Kleene k where
- empty :: k
- eps :: k
- appends :: [k] -> k
- unions :: [k] -> k
- star :: k -> k
class Kleene k => CharKleene c k | k -> c where
- char :: c -> k
- string :: [c] -> k
class CharKleene c k => FiniteKleene c k | k -> c where
- everything :: k
- charRange :: c -> c -> k
- fromRSet :: RSet c -> k
- dot :: k
- anyChar :: k
- notChar :: c -> k
class Derivate c k | k -> c where
- nullable :: k -> Bool
- derivate :: c -> k -> k
class Match c k | k -> c where
- match :: k -> [c] -> Bool
- match8 :: k -> ByteString -> Bool
class Match c k => Equivalent c k | k -> c where
- equivalent :: k -> k -> Bool
class Derivate c k => TransitionMap c k | k -> c where
- transitionMap :: k -> Map k (SF c k)
class Complement c k | k -> c where
- complement :: k -> k
class ToLatin1 (k :: Type -> Type) where
- toLatin1 :: k Char -> k Word8
data K c a

Regular expressions

data RE c Source #

Regular expression

Constructors are exposed, but you should use smart constructors in this module to construct RE.

The Eq and Ord instances are structural. The Kleene etc constructors do "weak normalisation", so for values constructed using those operations Eq witnesses "weak equivalence". See equivalent for regular-expression equivalence.

Structure is exposed in Kleene.RE module but consider constructors as half-internal. There are soft-invariants, but violating them shouldn't break anything in the package. (e.g. transitionMap will eventually terminate, but may create more redundant states if starting regexp is not "weakly normalised").

Instances

Instances details

ToLatin1 RE Source #
Instance details Defined in Kleene.Internal.RE Methods toLatin1 :: RE Char -> RE Word8 Source #
(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) => Complement c (RE c) Source #
Instance details Defined in Kleene.DFA Methods complement :: RE c -> RE c Source #
(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, 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) => 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) => 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, 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, Arbitrary c) => Arbitrary (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods arbitrary :: Gen (RE c) shrink :: RE c -> [RE c]
CoArbitrary c => CoArbitrary (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods coarbitrary :: RE c -> Gen b -> Gen b
c ~ Char => IsString (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods fromString :: String -> RE c
Eq c => Monoid (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods mempty :: RE c mappend :: RE c -> RE c -> RE c mconcat :: [RE c] -> RE c
Eq c => Semigroup (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods (<>) :: RE c -> RE c -> RE c sconcat :: NonEmpty (RE c) -> RE c stimes :: Integral b => b -> RE c -> RE c
Show c => Show (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods showsPrec :: Int -> RE c -> ShowS show :: RE c -> String showList :: [RE c] -> ShowS
Eq c => Eq (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods (==) :: RE c -> RE c -> Bool (/=) :: RE c -> RE c -> Bool
Ord c => Ord (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods compare :: RE c -> RE c -> Ordering (<) :: RE c -> RE c -> Bool (<=) :: RE c -> RE c -> Bool (>) :: RE c -> RE c -> Bool (>=) :: RE c -> RE c -> Bool max :: RE c -> RE c -> RE c min :: RE c -> RE c -> RE c
(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 #
c ~ Char => Pretty (RE c) Source #
Instance details Defined in Kleene.Internal.RE Methods pretty :: RE c -> String Source # prettyS :: RE c -> ShowS Source #
(Ord c, Enum c, Bounded c) => BoundedJoinSemiLattice (RE c)
Instance details Defined in Kleene.DFA Methods bottom :: RE c
(Ord c, Enum c, Bounded c) => BoundedMeetSemiLattice (RE c)
Instance details Defined in Kleene.DFA Methods top :: RE c
(Ord c, Enum c, Bounded c) => Lattice (RE c)	WARNING: The `/\` is inefficient, it actually computes the conjunction: `>>>` `putPretty $ asREChar $ "a" /\ "b"`^[]$ `>>>` `putPretty $ asREChar $ "a" /\ star "a"`^a$ `>>>` `putPretty $ asREChar $ star "aa" /\ star "aaa"`^(a(aaaaaa)*aaaaa)?$
Instance details Defined in Kleene.DFA Methods (\/) :: RE c -> RE c -> RE c (/\) :: RE c -> RE c -> RE c

data ERE c Source #

Extended regular expression

It's both, Kleene and Boolean algebra. (If we add only intersections, it wouldn't be Boolean).

Note: we don't have special constructor for intersections. We use de Morgan formula $a \land b = \neg (\neg a \lor \neg b)$.

>>> putPretty $ asEREChar $ "a" /\ "b"
^~(~a|~b)$

There is no generator, as intersections makes it hard.

Instances

Instances details

ToLatin1 ERE Source #
Instance details Defined in Kleene.ERE Methods toLatin1 :: ERE Char -> ERE Word8 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 #
Complement c (ERE c) Source #
Instance details Defined in Kleene.ERE Methods complement :: ERE c -> ERE 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, Enum c, Bounded c) => Equivalent c (ERE c) Source #
Instance details Defined in Kleene.ERE Methods equivalent :: ERE c -> ERE c -> Bool 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 #
(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, 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 #
(Ord c, Enum c, Bounded c, Arbitrary c) => Arbitrary (ERE c) Source #
Instance details Defined in Kleene.ERE Methods arbitrary :: Gen (ERE c) shrink :: ERE c -> [ERE c]
CoArbitrary c => CoArbitrary (ERE c) Source #
Instance details Defined in Kleene.ERE Methods coarbitrary :: ERE c -> Gen b -> Gen b
c ~ Char => IsString (ERE c) Source #
Instance details Defined in Kleene.ERE Methods fromString :: String -> ERE c
Eq c => Monoid (ERE c) Source #
Instance details Defined in Kleene.ERE Methods mempty :: ERE c mappend :: ERE c -> ERE c -> ERE c mconcat :: [ERE c] -> ERE c
Eq c => Semigroup (ERE c) Source #
Instance details Defined in Kleene.ERE Methods (<>) :: ERE c -> ERE c -> ERE c sconcat :: NonEmpty (ERE c) -> ERE c stimes :: Integral b => b -> ERE c -> ERE c
Show c => Show (ERE c) Source #
Instance details Defined in Kleene.ERE Methods showsPrec :: Int -> ERE c -> ShowS show :: ERE c -> String showList :: [ERE c] -> ShowS
Eq c => Eq (ERE c) Source #
Instance details Defined in Kleene.ERE Methods (==) :: ERE c -> ERE c -> Bool (/=) :: ERE c -> ERE c -> Bool
Ord c => Ord (ERE c) Source #
Instance details Defined in Kleene.ERE Methods compare :: ERE c -> ERE c -> Ordering (<) :: ERE c -> ERE c -> Bool (<=) :: ERE c -> ERE c -> Bool (>) :: ERE c -> ERE c -> Bool (>=) :: ERE c -> ERE c -> Bool max :: ERE c -> ERE c -> ERE c min :: ERE c -> ERE c -> ERE c
(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 #
c ~ Char => Pretty (ERE c) Source #
Instance details Defined in Kleene.ERE Methods pretty :: ERE c -> String Source # prettyS :: ERE c -> ShowS Source #
(Ord c, Enum c) => BoundedJoinSemiLattice (ERE c) Source #
Instance details Defined in Kleene.ERE Methods bottom :: ERE c
(Ord c, Enum c) => BoundedMeetSemiLattice (ERE c) Source #
Instance details Defined in Kleene.ERE Methods top :: ERE c
(Ord c, Enum c) => Lattice (ERE c) Source #
Instance details Defined in Kleene.ERE Methods (\/) :: ERE c -> ERE c -> ERE c (/\) :: ERE c -> ERE c -> ERE c

Equivalence (and partial order)

newtype Equiv (r :: Type -> Type) c Source #

Regular-expressions for which == is equivalent.

>>> let re1 = star "a" <> "a" :: RE Char
>>> let re2 = "a" <> star "a" :: RE Char

>>> re1 == re2
False

>>> Equiv re1 == Equiv re2
True

Equiv is also a PartialOrd (but not Ord!)

>>> Equiv "a" `leq` Equiv (star "a" :: RE Char)
True

Not all regular expessions are comparable:

>>> let reA = Equiv "a" :: Equiv RE Char
>>> let reB = Equiv "b" :: Equiv RE Char
>>> (leq reA reB, leq reB reA)
(False,False)

Constructors

Equiv (r c)

Instances

Instances details

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 #
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 #
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 #
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 #
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 #
Monoid (r c) => Monoid (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods mempty :: Equiv r c mappend :: Equiv r c -> Equiv r c -> Equiv r c mconcat :: [Equiv r c] -> Equiv r c
Semigroup (r c) => Semigroup (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods (<>) :: Equiv r c -> Equiv r c -> Equiv r c sconcat :: NonEmpty (Equiv r c) -> Equiv r c stimes :: Integral b => b -> Equiv r c -> Equiv r c
Show (r c) => Show (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods showsPrec :: Int -> Equiv r c -> ShowS show :: Equiv r c -> String showList :: [Equiv r c] -> ShowS
Equivalent c (r c) => Eq (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods (==) :: Equiv r c -> Equiv r c -> Bool (/=) :: Equiv r c -> Equiv r c -> Bool
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 #
Pretty (r c) => Pretty (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods pretty :: Equiv r c -> String Source # prettyS :: Equiv r c -> ShowS Source #
BoundedJoinSemiLattice (r c) => BoundedJoinSemiLattice (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods bottom :: Equiv r c
BoundedMeetSemiLattice (r c) => BoundedMeetSemiLattice (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods top :: Equiv r c
Lattice (r c) => Lattice (Equiv r c) Source #
Instance details Defined in Kleene.Equiv Methods (\/) :: Equiv r c -> Equiv r c -> Equiv r c (/\) :: Equiv r c -> Equiv r c -> Equiv r c
(Lattice (r c), Equivalent c (r c)) => PartialOrd (Equiv r c) Source #	$a \preceq b := a \lor b = b $
Instance details Defined in Kleene.Equiv Methods leq :: Equiv r c -> Equiv r c -> Bool comparable :: Equiv r c -> Equiv r c -> Bool

Deterministic finite automaton

data DFA c Source #

Deterministic finite automaton.

A deterministic finite automaton (DFA) over an alphabet $\Sigma$ (type variable c) is 4-tuple $Q$, $q_0$ , $F$, $\delta$, where

$Q$ is a finite set of states (subset of s),
$q_0 \in Q$ is the distinguised start state (dfaInitial),
$F \subset Q$ is a set of final (or accepting) states (dfaAcceptable), and
$\delta : Q \times \Sigma \to Q$ is a function called the state transition function (dfaTransition).

Constructors

DFA
Fields dfaTransition :: !(IntMap (SF c Int)) transition function dfaInitial :: !Int initial state dfaAcceptable :: !IntSet accept states dfaBlackholes :: !IntSet states we cannot escape

Instances

Instances details

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 #
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 #
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 #
Show c => Show (DFA c) Source #
Instance details Defined in Kleene.DFA Methods showsPrec :: Int -> DFA c -> ShowS show :: DFA c -> String showList :: [DFA c] -> ShowS
Show c => Pretty (DFA c) Source #
Instance details Defined in Kleene.DFA Methods pretty :: DFA c -> String Source # prettyS :: DFA c -> ShowS Source #

fromTM :: (Ord k, Ord c, TransitionMap c k) => k -> DFA c Source #

Create from TransitionMap.

See fromRE for a specific example.

fromTMEquiv :: (Ord k, Ord c, TransitionMap c k, Equivalent c k) => k -> DFA c Source #

Create from TransitonMap minimising states with Equivalent.

See fromERE for an example.

toKleene :: forall k c. (Ord c, Enum c, Bounded c, FiniteKleene c k) => DFA c -> k Source #

Convert to any Kleene.

See toRE for a specific example.

toDot :: DFA Char -> String Source #

Get Graphviz dot-code of DFA.

>>> let dfa = fromRE $ RE.star "abc"
>>> putStr $ toDot dfa
digraph dfa {
rankdir=LR;
// states
"0" [shape=doublecircle];
"1" [shape=circle];
"2" [shape=circle];
// initial state
"" [shape=none];
"" -> "0";
// transitions
"0" -> "2"[label="a"]
"1" -> "0"[label="c"]
"2" -> "1"[label="b"]
}

Classes

Most operations are defined in following type-classes.

See Kleene.RE module for a specific version with examples.

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

Instances details

(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 #
(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 #
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

Instances details

(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 #
(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 #
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 #

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 :: k Source #

. Every character except new line \n.

anyChar :: k Source #

Any character. Note: different than dot!

notChar :: c -> k Source #

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

Instances

Instances details

(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 #
(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 #

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

Instances details

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 #
(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, 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 #
(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 :: k -> ByteString -> Bool Source #

Instances

Instances details

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 #
(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, 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 #
(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

Instances details

(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 #
(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 #
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

Instances details

(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 #
(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 #

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

Instances details

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 (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 (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 :: Type -> Type) where Source #

Methods

toLatin1 :: k Char -> k Word8 Source #

Instances

Instances details

ToLatin1 ERE Source #
Instance details Defined in Kleene.ERE Methods toLatin1 :: ERE Char -> ERE Word8 Source #
ToLatin1 RE Source #
Instance details Defined in Kleene.Internal.RE Methods toLatin1 :: RE Char -> RE Word8 Source #
ToLatin1 RSet Source #
Instance details Defined in Kleene.Classes Methods toLatin1 :: RSet Char -> RSet Word8 Source #

Functor

Only the type is exported so it can be referred to.

See Kleene.Functor for operations.

data K c a Source #

Applicative Functor regular expression.

Instances

Instances details

Alternative (K c) Source #
Instance details Defined in Kleene.Internal.Functor Methods empty :: K c a (<\|>) :: K c a -> K c a -> K c a some :: K c a -> K c [a] many :: K c a -> K c [a]
Applicative (K c) Source #
Instance details Defined in Kleene.Internal.Functor Methods pure :: a -> K c a (<>) :: K c (a -> b) -> K c a -> K c b liftA2 :: (a -> b -> c0) -> K c a -> K c b -> K c c0 (>) :: K c a -> K c b -> K c b (<*) :: K c a -> K c b -> K c a
Functor (K c) Source #
Instance details Defined in Kleene.Internal.Functor Methods fmap :: (a -> b) -> K c a -> K c b (<$) :: a -> K c b -> K c a
Alt (K c) Source #
Instance details Defined in Kleene.Internal.Functor Methods (<!>) :: K c a -> K c a -> K c a some :: Applicative (K c) => K c a -> K c [a] many :: Applicative (K c) => K c a -> K c [a]
Apply (K c) Source #
Instance details Defined in Kleene.Internal.Functor Methods (<.>) :: K c (a -> b) -> K c a -> K c b (.>) :: K c a -> K c b -> K c b (<.) :: K c a -> K c b -> K c a liftF2 :: (a -> b -> c0) -> K c a -> K c b -> K c c0
(c ~ Char, IsString a) => IsString (K c a) Source #
Instance details Defined in Kleene.Internal.Functor Methods fromString :: String -> K c a
c ~ Char => Pretty (K c a) Source #	Convert to non-matching JavaScript string which can be used as an argument to `new RegExp` `>>>` `putPretty ("foobar" :: K Char String)`^foobar$ `>>>` `putPretty $ many ("foobar" :: K Char String)`^(foobar)*$
Instance details Defined in Kleene.Internal.Functor Methods pretty :: K c a -> String Source # prettyS :: K c a -> ShowS Source #