-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Kleene algebra -- -- Kleene algebra -- -- Think: Regular expressions -- -- Implements ideas from Regular-expression derivatives -- re-examined by Scott Owens, John Reppy and Aaron Turon -- https://doi.org/10.1017/S0956796808007090 @package kleene @version 0 module Kleene.Internal.Partition -- | Partition devides type into disjoint connected partitions. -- -- Note: we could have non-connecter partitions too, but that -- would be more complicated. This variant is correct by construction, -- but less precise. -- -- It's enought to store last element of each piece. -- -- Partition (fromList [x1, x2, x3]) :: Partition -- s describes a partition of Set s, as -- -- <math> -- -- Note: it's enough to check upper bound conditions only if -- checks are performed in order. -- -- Invariant: maxBound is not in the set. newtype Partition a Partition :: Set a -> Partition a [unPartition] :: Partition a -> Set a -- | Check invariant. invariant :: (Ord a, Bounded a) => Partition a -> Bool -- | 
--   invariant (asPartitionChar p)
--
-- | See wedge. fromSeparators :: (Enum a, Bounded a, Ord a) => [a] -> Partition a -- | Construct Partition from list of RSets. -- -- RSet intervals are closed on both sides. fromRSets :: (Enum a, Bounded a, Ord a) => [RSet a] -> Partition a fromRSet :: (Enum a, Bounded a, Ord a) => RSet a -> Partition a whole :: Partition a -- | Count of sets in a Partition. -- -- 
--   >>> size whole
--   1
--
-- -- 
--   >>> size $ split (10 :: Word8)
--   2
--
-- -- 
--   size (asPartitionChar p) >= 1
--
size :: Partition a -> Int -- | Extract examples from each subset in a Partition. -- -- 
--   >>> examples $ split (10 :: Word8)
--   fromList [10,255]
--
-- -- 
--   >>> examples $ split (10 :: Word8) <> split 20
--   fromList [10,20,255]
--
-- -- 
--   invariant p ==> size (asPartitionChar p) === length (examples p)
--
examples :: (Bounded a, Enum a, Ord a) => Partition a -> Set a -- | 
--   all (curry (<=)) $ intervals $ asPartitionChar p
--
intervals :: (Enum a, Bounded a, Ord a) => Partition a -> NonEmpty (a, a) -- | Wedge partitions. -- -- 
--   >>> split (10 :: Word8) <> split 20
--   fromSeparators [10,20]
--
-- -- 
--   whole `wedge` (p :: Partition Char) === p
--
-- -- 
--   (p :: Partition Char) <> whole === p
--
-- -- 
--   asPartitionChar p <> q === q <> p
--
-- -- 
--   asPartitionChar p <> p === p
--
-- -- 
--   invariant $ asPartitionChar p <> q
--
wedge :: Ord a => Partition a -> Partition a -> Partition a -- | Simplest partition: given x partition space into [min..x) -- and [x .. max] -- -- 
--   >>> split (128 :: Word8)
--   fromSeparators [128]
--
split :: (Enum a, Bounded a, Eq a) => a -> Partition a -- | Make a step function. toSF :: (Enum a, Bounded a, Ord a) => (a -> b) -> Partition a -> SF a b instance GHC.Classes.Ord a => GHC.Classes.Ord (Kleene.Internal.Partition.Partition a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Kleene.Internal.Partition.Partition a) instance GHC.Show.Show a => GHC.Show.Show (Kleene.Internal.Partition.Partition a) instance (GHC.Enum.Enum a, GHC.Enum.Bounded a, GHC.Classes.Ord a, Test.QuickCheck.Arbitrary.Arbitrary a) => Test.QuickCheck.Arbitrary.Arbitrary (Kleene.Internal.Partition.Partition a) instance (GHC.Enum.Enum a, GHC.Enum.Bounded a, GHC.Classes.Ord a) => Data.Semigroup.Semigroup (Kleene.Internal.Partition.Partition a) instance (GHC.Enum.Enum a, GHC.Enum.Bounded a, GHC.Classes.Ord a) => GHC.Base.Monoid (Kleene.Internal.Partition.Partition a) -- | Character sets. module Kleene.Internal.Sets -- | All but the newline. dotRSet :: RSet Char module Kleene.Internal.Pretty -- | Pretty class. -- -- For pretty :: RE -> String gives a -- representation accepted by many regex engines. class Pretty a pretty :: Pretty a => a -> String prettyS :: Pretty a => a -> ShowS -- | 
--   putStrLn . pretty
--
putPretty :: Pretty a => a -> IO () instance c ~ GHC.Types.Char => Kleene.Internal.Pretty.Pretty (Data.RangeSet.Map.RSet c) instance Kleene.Internal.Pretty.Pretty GHC.Types.Char instance Kleene.Internal.Pretty.Pretty GHC.Types.Bool instance Kleene.Internal.Pretty.Pretty () module Kleene.Classes class (BoundedJoinSemiLattice k, Semigroup k, Monoid k) => Kleene c k | k -> c -- | Empty regex. Doesn't accept anything. empty :: Kleene c k => k -- | Empty string. Note: different than empty eps :: Kleene c k => k -- | Single character char :: Kleene c k => c -> k -- | Concatenation. appends :: Kleene c k => [k] -> k -- | Union. unions :: Kleene c k => [k] -> k -- | Kleene star star :: Kleene c k => k -> k -- | One of the characters. oneof :: (Kleene c k, Foldable f) => f c -> k class Kleene c k => FiniteKleene c k | k -> c -- | Everything. <math>. everything :: FiniteKleene c k => k -- | charRange a z = ^[a-z]$. charRange :: FiniteKleene c k => c -> c -> k -- | Generalisation of charRange. fromRSet :: FiniteKleene c k => RSet c -> k -- | .$. Every character except new line \n@. dot :: (FiniteKleene c k, c ~ Char) => k -- | Any character. Note: different than dot! anyChar :: FiniteKleene c k => k class Derivate c k | k -> c -- | Does language contain an empty string? nullable :: Derivate c k => k -> Bool -- | Derivative of a language. derivate :: Derivate c k => c -> k -> k -- | An f can be used to match on the input. class Match c k | k -> c match :: Match c k => k -> [c] -> Bool -- | Equivalence induced by Matches. -- -- Law: -- -- 
--   equivalent re1 re2 = forall s. matches re1 s == matches re1 s
--
class Match c k => Equivalent c k | k -> c equivalent :: Equivalent c k => k -> k -> Bool -- | Transition map. class Derivate c k => TransitionMap c k | k -> c transitionMap :: TransitionMap c k => k -> Map k (SF c k) -- | Complement of the language. -- -- Law: -- -- 
--   matches (complement f) xs = not (matches f) xs
--
class Complement c k | k -> c complement :: Complement c k => k -> k module Kleene.Equiv -- | 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)
--
newtype Equiv r c Equiv :: (r c) -> Equiv r c -- | <math> instance Kleene.Internal.Pretty.Pretty (r c) => Kleene.Internal.Pretty.Pretty (Kleene.Equiv.Equiv r c) instance Algebra.Lattice.JoinSemiLattice (r c) => Algebra.Lattice.JoinSemiLattice (Kleene.Equiv.Equiv r c) instance Algebra.Lattice.BoundedJoinSemiLattice (r c) => Algebra.Lattice.BoundedJoinSemiLattice (Kleene.Equiv.Equiv r c) instance GHC.Base.Monoid (r c) => GHC.Base.Monoid (Kleene.Equiv.Equiv r c) instance Data.Semigroup.Semigroup (r c) => Data.Semigroup.Semigroup (Kleene.Equiv.Equiv r c) instance GHC.Show.Show (r c) => GHC.Show.Show (Kleene.Equiv.Equiv r c) instance Kleene.Classes.Kleene c (r c) => Kleene.Classes.Kleene c (Kleene.Equiv.Equiv r c) instance Kleene.Classes.Derivate c (r c) => Kleene.Classes.Derivate c (Kleene.Equiv.Equiv r c) instance Kleene.Classes.Match c (r c) => Kleene.Classes.Match c (Kleene.Equiv.Equiv r c) instance Kleene.Classes.Equivalent c (r c) => Kleene.Classes.Equivalent c (Kleene.Equiv.Equiv r c) instance Kleene.Classes.Complement c (r c) => Kleene.Classes.Complement c (Kleene.Equiv.Equiv r c) instance Kleene.Classes.Equivalent c (r c) => GHC.Classes.Eq (Kleene.Equiv.Equiv r c) instance (Algebra.Lattice.JoinSemiLattice (r c), Kleene.Classes.Equivalent c (r c)) => Algebra.PartialOrd.PartialOrd (Kleene.Equiv.Equiv r c) module Kleene.ERE -- | 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 <math>. -- -- 
--   >>> putPretty $ asEREChar $ "a" /\ "b"
--   ^~(~a|~b)$
--
-- -- There is no generator, as intersections makes it hard. data ERE c -- | Single character EREChars :: (RSet c) -> ERE c -- | Concatenation EREAppend :: [ERE c] -> ERE c -- | Union EREUnion :: (RSet c) -> (Set (ERE c)) -> ERE c -- | Kleene star EREStar :: (ERE c) -> ERE c -- | Complement ERENot :: (ERE c) -> ERE c -- | Empty regex. Doesn't accept anything. -- -- 
--   >>> putPretty (empty :: ERE Char)
--   ^[]$
--
-- -- 
--   >>> putPretty (bottom :: ERE Char)
--   ^[]$
--
-- -- 
--   match (empty :: ERE Char) (s :: String) === False
--
empty :: ERE c -- | Empty string. Note: different than empty. -- -- 
--   >>> putPretty eps
--   ^$
--
-- -- 
--   >>> putPretty (mempty :: ERE Char)
--   ^$
--
-- -- 
--   match (eps :: ERE Char) s === null (s :: String)
--
eps :: ERE c -- | 
--   >>> putPretty (char 'x')
--   ^x$
--
char :: c -> ERE c -- | 
--   >>> putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--
charRange :: Ord c => c -> c -> ERE c -- | Any character. Note: different than dot! -- -- 
--   >>> putPretty anyChar
--   ^[^]$
--
anyChar :: Bounded c => ERE c -- | Concatenate regular expressions. -- -- 
--   asEREChar r <> empty === empty
--
-- -- 
--   empty <> asEREChar r === empty
--
-- -- 
--   (asEREChar r <> s) <> t === r <> (s <> t)
--
-- -- 
--   asEREChar r <> eps === r
--
-- -- 
--   eps <> asEREChar r === r
--
appends :: Eq c => [ERE c] -> ERE c -- | Union of regular expressions. -- -- 
--   asEREChar r \/ r === r
--
-- -- 
--   asEREChar r \/ s === s \/ r
--
-- -- 
--   (asEREChar r \/ s) \/ t === r \/ (s \/ t)
--
-- -- 
--   empty \/ asEREChar r === r
--
-- -- 
--   asEREChar r \/ empty === r
--
-- -- 
--   everything \/ asREChar r === everything
--
-- -- 
--   asREChar r \/ everything === everything
--
unions :: (Ord c, Enum c) => [ERE c] -> ERE c -- | Intersection of regular expressions. -- -- 
--   asEREChar r /\ r === r
--
-- -- 
--   asEREChar r /\ s === s /\ r
--
-- -- 
--   (asEREChar r /\ s) /\ t === r /\ (s /\ t)
--
-- -- 
--   empty /\ asEREChar r === empty
--
-- -- 
--   asEREChar r /\ empty === empty
--
-- -- 
--   everything /\ asREChar r === r
--
-- -- 
--   asREChar r /\ everything === r
--
intersections :: (Ord c, Enum c) => [ERE c] -> ERE c -- | Kleene star. -- -- 
--   star (star r) === star (asEREChar r)
--
-- -- 
--   star eps     === asEREChar eps
--
-- -- 
--   star empty   === asEREChar eps
--
-- -- 
--   star anyChar === asEREChar everything
--
-- -- 
--   star (asREChar r \/ eps) === star r
--
-- -- 
--   star (char c \/ eps) === star (char (c :: Char))
--
-- -- 
--   star (empty \/ eps) === eps
--
star :: (Ord c, Bounded c) => ERE c -> ERE c -- | Literal string. -- -- 
--   >>> putPretty ("foobar" :: ERE Char)
--   ^foobar$
--
-- -- 
--   >>> putPretty ("(.)" :: ERE Char)
--   ^\(\.\)$
--
string :: [c] -> ERE c -- | Complement. -- -- 
--   complement (complement r) === asEREChar r
--
complement :: ERE c -> ERE c -- | We say that a regular expression r is nullable if the language it -- defines contains the empty string. -- -- 
--   >>> nullable eps
--   True
--
-- -- 
--   >>> nullable (star "x")
--   True
--
-- -- 
--   >>> nullable "foo"
--   False
--
-- -- 
--   >>> nullable (complement eps)
--   False
--
nullable :: ERE c -> Bool -- | Intuitively, the derivative of a language <math> with respect to -- a symbol <math> is the language that includes only those -- suffixes of strings with a leading symbol <math> in -- <math>. -- -- 
--   >>> putPretty $ derivate 'f' "foobar"
--   ^oobar$
--
-- -- 
--   >>> putPretty $ derivate 'x' $ "xyz" \/ "abc"
--   ^yz$
--
-- -- 
--   >>> putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--
derivate :: (Ord c, Enum c) => c -> ERE c -> ERE c -- | Transition map. Used to construct DFA. -- -- 
--   >>> void $ Map.traverseWithKey (\k v -> putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: ERE Char)
--   ^[]$ : \_ -> "^[]$"
--   ^b$ : \x -> if
--       | x <= 'a'  -> "^[]$"
--       | x <= 'b'  -> "^$"
--       | otherwise -> "^[]$"
--   ^$ : \_ -> "^[]$"
--   ^ab$ : \x -> if
--       | x <= '`'  -> "^[]$"
--       | x <= 'a'  -> "^b$"
--       | otherwise -> "^[]$"
--
transitionMap :: forall c. (Ord c, Enum c, Bounded c) => ERE c -> Map (ERE c) (SF c (ERE c)) -- | Leading character sets of regular expression. -- -- 
--   >>> leadingChars "foo"
--   fromSeparators "ef"
--
-- -- 
--   >>> leadingChars (star "b" <> star "e")
--   fromSeparators "abde"
--
-- -- 
--   >>> leadingChars (charRange 'b' 'z')
--   fromSeparators "az"
--
leadingChars :: (Ord c, Enum c, Bounded c) => ERE c -> Partition c -- | Whether two regexps are equivalent. -- -- 
--   equivalent re1 re2 = forall s. match re1 s == match re1 s
--
-- -- 
--   >>> let re1 = star "a" <> "a"
--   
--   >>> let re2 = "a" <> star "a"
--
-- -- These are different regular expressions, even we perform some -- normalisation-on-construction: -- -- 
--   >>> re1 == re2
--   False
--
-- -- They are however equivalent: -- -- 
--   >>> equivalent re1 re2
--   True
--
-- -- The algorithm works by executing states on "product" regexp, -- and checking whether all resulting states are both accepting or -- rejecting. -- -- 
--   re1 == re2 ==> equivalent re1 re2
--
-- --

More examples

-- -- 
--   >>> let example re1 re2 = putPretty re1 >> putPretty re2 >> return (equivalent re1 re2)
--   
--   >>> example re1 re2
--   ^a*a$
--   ^aa*$
--   True
--
-- -- 
--   >>> example (star "aa") (star "aaa")
--   ^(aa)*$
--   ^(aaa)*$
--   False
--
-- -- 
--   >>> example (star "aa" <> star "aaa") (star "aaa" <> star "aa")
--   ^(aa)*(aaa)*$
--   ^(aaa)*(aa)*$
--   True
--
-- -- 
--   >>> example (star ("a" \/ "b")) (star $ star "a" <> star "b")
--   ^[a-b]*$
--   ^(a*b*)*$
--   True
--
equivalent :: forall c. (Ord c, Enum c, Bounded c) => ERE c -> ERE c -> Bool -- | Whether ERE is (structurally) equal to empty. isEmpty :: ERE c -> Bool -- | Whether ERE is (structurally) equal to everything. isEverything :: ERE c -> Bool instance GHC.Show.Show c => GHC.Show.Show (Kleene.ERE.ERE c) instance GHC.Classes.Ord c => GHC.Classes.Ord (Kleene.ERE.ERE c) instance GHC.Classes.Eq c => GHC.Classes.Eq (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Kleene c (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.FiniteKleene c (Kleene.ERE.ERE c) instance Kleene.Classes.Complement c (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Kleene.Classes.Derivate c (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Kleene.Classes.Match c (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.TransitionMap c (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Equivalent c (Kleene.ERE.ERE c) instance GHC.Classes.Eq c => Data.Semigroup.Semigroup (Kleene.ERE.ERE c) instance GHC.Classes.Eq c => GHC.Base.Monoid (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Algebra.Lattice.JoinSemiLattice (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Algebra.Lattice.BoundedJoinSemiLattice (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Algebra.Lattice.MeetSemiLattice (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Algebra.Lattice.BoundedMeetSemiLattice (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Algebra.Lattice.Lattice (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c) => Algebra.Lattice.BoundedLattice (Kleene.ERE.ERE c) instance c ~ GHC.Types.Char => Data.String.IsString (Kleene.ERE.ERE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c, Test.QuickCheck.Arbitrary.Arbitrary c) => Test.QuickCheck.Arbitrary.Arbitrary (Kleene.ERE.ERE c) instance Test.QuickCheck.Arbitrary.CoArbitrary c => Test.QuickCheck.Arbitrary.CoArbitrary (Kleene.ERE.ERE c) instance c ~ GHC.Types.Char => Kleene.Internal.Pretty.Pretty (Kleene.ERE.ERE c) module Kleene.Monad -- | Regular expression which has no restrictions on the elements. -- Therefore we can have Monad instance, i.e. have a regexp where -- characters are regexps themselves. -- -- Because there are no optimisations, it's better to work over small -- alphabets. On the other hand, we can work over infinite alphabets, if -- we only use small amount of symbols! -- -- 
--   >>> putPretty $ string [True, False]
--   ^10$
--
-- -- 
--   >>> let re  = string [True, False, True]
--   
--   >>> let re' = re >>= \b -> if b then char () else star (char ())
--   
--   >>> putPretty re'
--   ^..*.$
--
data M c -- | One of the characters MChars :: [c] -> M c -- | Concatenation MAppend :: [M c] -> M c -- | Union MUnion :: [c] -> [M c] -> M c -- | Kleene star MStar :: (M c) -> M c -- | Empty regex. Doesn't accept anything. -- -- 
--   >>> putPretty (empty :: M Bool)
--   ^[]$
--
-- -- 
--   >>> putPretty (bottom :: M Bool)
--   ^[]$
--
-- -- 
--   match (empty :: M Bool) (s :: String) === False
--
empty :: M c -- | Empty string. Note: different than empty. -- -- 
--   >>> putPretty (eps :: M Bool)
--   ^$
--
-- -- 
--   >>> putPretty (mempty :: M Bool)
--   ^$
--
-- -- 
--   match (eps :: M Bool) s === null (s :: String)
--
eps :: M c -- | 
--   >>> putPretty (char 'x')
--   ^x$
--
char :: c -> M c -- | Note: we know little about c. -- -- 
--   >>> putPretty $ charRange 'a' 'z'
--   ^[abcdefghijklmnopqrstuvwxyz]$
--
charRange :: Enum c => c -> c -> M c -- | Any character. Note: different than dot! -- -- 
--   >>> putPretty (anyChar :: M Bool)
--   ^[01]$
--
anyChar :: (Bounded c, Enum c) => M c -- | Concatenate regular expressions. appends :: [M c] -> M c -- | Union of regular expressions. -- -- Lattice laws don't hold structurally: unions :: [M c] -> M c -- | Kleene star. star :: M c -> M c -- | Literal string. -- -- 
--   >>> putPretty ("foobar" :: M Char)
--   ^foobar$
--
-- -- 
--   >>> putPretty ("(.)" :: M Char)
--   ^\(\.\)$
--
-- -- 
--   >>> putPretty $ string [False, True]
--   ^01$
--
string :: [c] -> M c -- | We say that a regular expression r is nullable if the language it -- defines contains the empty string. -- -- 
--   >>> nullable eps
--   True
--
-- -- 
--   >>> nullable (star "x")
--   True
--
-- -- 
--   >>> nullable "foo"
--   False
--
nullable :: M c -> Bool -- | Intuitively, the derivative of a language <math> with respect to -- a symbol <math> is the language that includes only those -- suffixes of strings with a leading symbol <math> in -- <math>. -- -- 
--   >>> putPretty $ derivate 'f' "foobar"
--   ^oobar$
--
-- -- 
--   >>> putPretty $ derivate 'x' $ "xyz" \/ "abc"
--   ^yz$
--
-- -- 
--   >>> putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--
derivate :: (Eq c, Enum c, Bounded c) => c -> M c -> M c -- | Generate random strings of the language M c describes. -- -- 
--   >>> let example = traverse_ print . take 3 . generate 42
--   
--   >>> example "abc"
--   "abc"
--   "abc"
--   "abc"
--
-- -- 
--   >>> example $ star $ "a" \/ "b"
--   "ababbb"
--   "baab"
--   "abbababaa"
--
-- -- xx >>> example empty -- -- expensive-prop> all (match r) $ take 10 $ generate 42 (r :: M Bool) generate :: Int -> M c -> [[c]] -- | Convert to Kleene -- -- 
--   >>> let re = charRange 'a' 'z'
--   
--   >>> putPretty re
--   ^[abcdefghijklmnopqrstuvwxyz]$
--
-- -- 
--   >>> putPretty (toKleene re :: RE Char)
--   ^[a-z]$
--
toKleene :: Kleene c k => M c -> k -- | Whether M is (structurally) equal to empty. isEmpty :: M c -> Bool -- | Whether M is (structurally) equal to eps. isEps :: M c -> Bool instance Data.Traversable.Traversable Kleene.Monad.M instance Data.Foldable.Foldable Kleene.Monad.M instance GHC.Base.Functor Kleene.Monad.M instance GHC.Show.Show c => GHC.Show.Show (Kleene.Monad.M c) instance GHC.Classes.Ord c => GHC.Classes.Ord (Kleene.Monad.M c) instance GHC.Classes.Eq c => GHC.Classes.Eq (Kleene.Monad.M c) instance GHC.Base.Applicative Kleene.Monad.M instance GHC.Base.Monad Kleene.Monad.M instance Kleene.Classes.Kleene c (Kleene.Monad.M c) instance (GHC.Classes.Eq c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Derivate c (Kleene.Monad.M c) instance (GHC.Classes.Eq c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Match c (Kleene.Monad.M c) instance Data.Semigroup.Semigroup (Kleene.Monad.M c) instance GHC.Base.Monoid (Kleene.Monad.M c) instance Algebra.Lattice.JoinSemiLattice (Kleene.Monad.M c) instance Algebra.Lattice.BoundedJoinSemiLattice (Kleene.Monad.M c) instance c ~ GHC.Types.Char => Data.String.IsString (Kleene.Monad.M c) instance (GHC.Classes.Eq c, GHC.Enum.Enum c, GHC.Enum.Bounded c, Test.QuickCheck.Arbitrary.Arbitrary c) => Test.QuickCheck.Arbitrary.Arbitrary (Kleene.Monad.M c) instance Test.QuickCheck.Arbitrary.CoArbitrary c => Test.QuickCheck.Arbitrary.CoArbitrary (Kleene.Monad.M c) instance (Kleene.Internal.Pretty.Pretty c, GHC.Classes.Eq c) => Kleene.Internal.Pretty.Pretty (Kleene.Monad.M c) module Kleene.RE -- | 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"). data RE c -- | Single character REChars :: (RSet c) -> RE c -- | Concatenation REAppend :: [RE c] -> RE c -- | Union REUnion :: (RSet c) -> (Set (RE c)) -> RE c -- | Kleene star REStar :: (RE c) -> RE c -- | Empty regex. Doesn't accept anything. -- -- 
--   >>> putPretty (empty :: RE Char)
--   ^[]$
--
-- -- 
--   >>> putPretty (bottom :: RE Char)
--   ^[]$
--
-- -- 
--   match (empty :: RE Char) (s :: String) === False
--
empty :: RE c -- | Empty string. Note: different than empty. -- -- 
--   >>> putPretty eps
--   ^$
--
-- -- 
--   >>> putPretty (mempty :: RE Char)
--   ^$
--
-- -- 
--   match (eps :: RE Char) s === null (s :: String)
--
eps :: RE c -- | 
--   >>> putPretty (char 'x')
--   ^x$
--
char :: c -> RE c -- | 
--   >>> putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--
charRange :: Ord c => c -> c -> RE c -- | Any character. Note: different than dot! -- -- 
--   >>> putPretty anyChar
--   ^[^]$
--
anyChar :: Bounded c => RE c -- | Concatenate regular expressions. -- -- 
--   (asREChar r <> s) <> t === r <> (s <> t)
--
-- -- 
--   asREChar r <> empty === empty
--
-- -- 
--   empty <> asREChar r === empty
--
-- -- 
--   asREChar r <> eps === r
--
-- -- 
--   eps <> asREChar r === r
--
appends :: Eq c => [RE c] -> RE c -- | Union of regular expressions. -- -- 
--   asREChar r \/ r === r
--
-- -- 
--   asREChar r \/ s === s \/ r
--
-- -- 
--   (asREChar r \/ s) \/ t === r \/ (s \/ t)
--
-- -- 
--   empty \/ asREChar r === r
--
-- -- 
--   asREChar r \/ empty === r
--
-- -- 
--   everything \/ asREChar r === everything
--
-- -- 
--   asREChar r \/ everything === everything
--
unions :: (Ord c, Enum c, Bounded c) => [RE c] -> RE c -- | Kleene star. -- -- 
--   star (star r) === star (asREChar r)
--
-- -- 
--   star eps     === asREChar eps
--
-- -- 
--   star empty   === asREChar eps
--
-- -- 
--   star anyChar === asREChar everything
--
-- -- 
--   star (r      \/ eps) === star (asREChar r)
--
-- -- 
--   star (char c \/ eps) === star (asREChar (char c))
--
-- -- 
--   star (empty  \/ eps) === asREChar eps
--
star :: Ord c => RE c -> RE c -- | Literal string. -- -- 
--   >>> putPretty ("foobar" :: RE Char)
--   ^foobar$
--
-- -- 
--   >>> putPretty ("(.)" :: RE Char)
--   ^\(\.\)$
--
string :: [c] -> RE c -- | We say that a regular expression r is nullable if the language it -- defines contains the empty string. -- -- 
--   >>> nullable eps
--   True
--
-- -- 
--   >>> nullable (star "x")
--   True
--
-- -- 
--   >>> nullable "foo"
--   False
--
nullable :: RE c -> Bool -- | Intuitively, the derivative of a language <math> with respect to -- a symbol <math> is the language that includes only those -- suffixes of strings with a leading symbol <math> in -- <math>. -- -- 
--   >>> putPretty $ derivate 'f' "foobar"
--   ^oobar$
--
-- -- 
--   >>> putPretty $ derivate 'x' $ "xyz" \/ "abc"
--   ^yz$
--
-- -- 
--   >>> putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--
derivate :: (Ord c, Enum c, Bounded c) => c -> RE c -> RE c -- | Transition map. Used to construct DFA. -- -- 
--   >>> void $ Map.traverseWithKey (\k v -> putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: RE Char)
--   ^[]$ : \_ -> "^[]$"
--   ^b$ : \x -> if
--       | x <= 'a'  -> "^[]$"
--       | x <= 'b'  -> "^$"
--       | otherwise -> "^[]$"
--   ^$ : \_ -> "^[]$"
--   ^ab$ : \x -> if
--       | x <= '`'  -> "^[]$"
--       | x <= 'a'  -> "^b$"
--       | otherwise -> "^[]$"
--
transitionMap :: forall c. (Ord c, Enum c, Bounded c) => RE c -> Map (RE c) (SF c (RE c)) -- | Leading character sets of regular expression. -- -- 
--   >>> leadingChars "foo"
--   fromSeparators "ef"
--
-- -- 
--   >>> leadingChars (star "b" <> star "e")
--   fromSeparators "abde"
--
-- -- 
--   >>> leadingChars (charRange 'b' 'z')
--   fromSeparators "az"
--
leadingChars :: (Ord c, Enum c, Bounded c) => RE c -> Partition c -- | Whether two regexps are equivalent. -- -- 
--   equivalent re1 re2 = forall s. match re1 s === match re1 s
--
-- -- 
--   >>> let re1 = star "a" <> "a"
--   
--   >>> let re2 = "a" <> star "a"
--
-- -- These are different regular expressions, even we perform some -- normalisation-on-construction: -- -- 
--   >>> re1 == re2
--   False
--
-- -- They are however equivalent: -- -- 
--   >>> equivalent re1 re2
--   True
--
-- -- The algorithm works by executing states on "product" regexp, -- and checking whether all resulting states are both accepting or -- rejecting. -- -- 
--   re1 == re2 ==> equivalent re1 re2
--
-- --

More examples

-- -- 
--   >>> let example re1 re2 = putPretty re1 >> putPretty re2 >> return (equivalent re1 re2)
--   
--   >>> example re1 re2
--   ^a*a$
--   ^aa*$
--   True
--
-- -- 
--   >>> example (star "aa") (star "aaa")
--   ^(aa)*$
--   ^(aaa)*$
--   False
--
-- -- 
--   >>> example (star "aa" <> star "aaa") (star "aaa" <> star "aa")
--   ^(aa)*(aaa)*$
--   ^(aaa)*(aa)*$
--   True
--
-- -- 
--   >>> example (star ("a" \/ "b")) (star $ star "a" <> star "b")
--   ^[a-b]*$
--   ^(a*b*)*$
--   True
--
equivalent :: forall c. (Ord c, Enum c, Bounded c) => RE c -> RE c -> Bool -- | Generate random strings of the language RE c describes. -- -- 
--   >>> let example = traverse_ print . take 3 . generate (curry QC.choose) 42
--   
--   >>> example "abc"
--   "abc"
--   "abc"
--   "abc"
--
-- -- 
--   >>> example $ star $ "a" \/ "b"
--   "aaaaba"
--   "bbba"
--   "abbbbaaaa"
--
-- -- 
--   >>> example empty
--
-- -- 
--   all (match r) $ take 10 $ generate (curry QC.choose) 42 (r :: RE Char)
--
generate :: (c -> c -> Gen c) -> Int -> RE c -> [[c]] -- | Whether RE is (structurally) equal to empty. -- -- 
--   isEmpty r === all (not . nullable) (Map.keys $ transitionMap $ asREChar r)
--
isEmpty :: RE c -> Bool instance GHC.Show.Show c => GHC.Show.Show (Kleene.RE.RE c) instance GHC.Classes.Ord c => GHC.Classes.Ord (Kleene.RE.RE c) instance GHC.Classes.Eq c => GHC.Classes.Eq (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Kleene c (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.FiniteKleene c (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Derivate c (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Match c (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.TransitionMap c (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Equivalent c (Kleene.RE.RE c) instance GHC.Classes.Eq c => Data.Semigroup.Semigroup (Kleene.RE.RE c) instance GHC.Classes.Eq c => GHC.Base.Monoid (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Algebra.Lattice.JoinSemiLattice (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Algebra.Lattice.BoundedJoinSemiLattice (Kleene.RE.RE c) instance c ~ GHC.Types.Char => Data.String.IsString (Kleene.RE.RE c) instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c, Test.QuickCheck.Arbitrary.Arbitrary c) => Test.QuickCheck.Arbitrary.Arbitrary (Kleene.RE.RE c) instance Test.QuickCheck.Arbitrary.CoArbitrary c => Test.QuickCheck.Arbitrary.CoArbitrary (Kleene.RE.RE c) instance c ~ GHC.Types.Char => Kleene.Internal.Pretty.Pretty (Kleene.RE.RE c) module Kleene.Functor -- | Applicative Functor regular expression. data K c a -- | Star behaviour data Greediness -- | many Greedy :: Greediness -- | few NonGreedy :: Greediness -- | few, not many. -- -- Let's define two similar regexps -- -- 
--   >>> let re1 = liftA2 (,) (few  $ char 'a') (many $ char 'a')
--   
--   >>> let re2 = liftA2 (,) (many $ char 'a') (few  $ char 'a')
--
-- -- Their RE behaviour is the same: -- -- 
--   >>> C.equivalent (toRE re1) (toRE re2)
--   True
--
-- -- 
--   >>> map (C.match $ toRE re1) ["aaa","bbb"]
--   [True,False]
--
-- -- However, the RA behaviour is different! -- -- 
--   >>> R.match (toRA re1) "aaaa"
--   Just ("","aaaa")
--
-- -- 
--   >>> R.match (toRA re2) "aaaa"
--   Just ("aaaa","")
--
few :: K c a -> K c [a] -- | 
--   >>> putPretty anyChar
--   ^[^]$
--
anyChar :: (Ord c, Enum c, Bounded c) => K c c -- | 
--   >>> putPretty $ oneof ("foobar" :: [Char])
--   ^[a-bfor]$
--
oneof :: (Ord c, Enum c, Foldable f) => f c -> K c c -- | 
--   >>> putPretty $ char 'x'
--   ^x$
--
char :: (Ord c, Enum c) => c -> K c c -- | 
--   >>> putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--
charRange :: (Enum c, Ord c) => c -> c -> K c c -- | 
--   >>> putPretty dot
--   ^.$
--
dot :: K Char Char -- | 
--   >>> putPretty everything
--   ^[^]*$
--
everything :: (Ord c, Enum c, Bounded c) => K c [c] -- | 
--   >>> putPretty everything1
--   ^[^][^]*$
--
everything1 :: (Ord c, Enum c, Bounded c) => K c [c] -- | Matches nothing? isEmpty :: (Ord c, Enum c, Bounded c) => K c a -> Bool -- | Matches whole input? isEverything :: (Ord c, Enum c, Bounded c) => K c a -> Bool -- | Match using regex-applicative match :: K c a -> [c] -> Maybe a -- | Convert to RE. -- -- 
--   >>> putPretty (toRE $ many "foo" :: RE.RE Char)
--   ^(foo)*$
--
toRE :: (Ord c, Enum c, Bounded c) => K c a -> RE c -- | Convert to any Kleene toKleene :: FiniteKleene c k => K c a -> k -- | Convert from RE. -- -- Note: all REStars are converted to Greedy ones, -- it doesn't matter, as we don't capture anything. -- -- 
--   >>> match (fromRE "foobar") "foobar"
--   Just "foobar"
--
-- -- 
--   >>> match (fromRE $ C.star "a" <> C.star "a") "aaaa"
--   Just "aaaa"
--
fromRE :: (Ord c, Enum c) => RE c -> K c [c] -- | Convert K to RE from regex-applicative. -- -- 
--   >>> R.match (toRA ("xx" *> everything <* "zz" :: K Char String)) "xxyyyzz"
--   Just "yyy"
--
-- -- See also match. toRA :: K c a -> RE c a instance GHC.Enum.Bounded Kleene.Functor.Greediness instance GHC.Enum.Enum Kleene.Functor.Greediness instance GHC.Show.Show Kleene.Functor.Greediness instance GHC.Classes.Ord Kleene.Functor.Greediness instance GHC.Classes.Eq Kleene.Functor.Greediness instance (c ~ GHC.Types.Char, Data.String.IsString a) => Data.String.IsString (Kleene.Functor.K c a) instance GHC.Base.Functor (Kleene.Functor.K c) instance GHC.Base.Applicative (Kleene.Functor.K c) instance GHC.Base.Alternative (Kleene.Functor.K c) instance c ~ GHC.Types.Char => Kleene.Internal.Pretty.Pretty (Kleene.Functor.K c a) module Kleene.DFA -- | Deterministic finite automaton. -- -- A deterministic finite automaton (DFA) over an alphabet <math> -- (type variable c) is 4-tuple <math>, <math> , -- <math>, <math>, where -- -- data DFA c DFA :: !(IntMap (SF c Int)) -> !IntSet -> !IntSet -> DFA c -- | transition function [dfaTransition] :: DFA c -> !(IntMap (SF c Int)) -- | accept states [dfaAcceptable] :: DFA c -> !IntSet -- | states we cannot escape [dfaBlackholes] :: DFA c -> !IntSet -- | Convert RE to DFA. -- -- 
--   >>> putPretty $ fromRE $ RE.star "abc"
--   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
--
-- -- Everything and nothing result in blackholes: -- -- 
--   >>> traverse_ (putPretty . fromRE) [RE.empty, RE.star RE.anyChar]
--   0 -> \_ -> 0 -- black hole
--   0+ -> \_ -> 0 -- black hole
--
-- -- Character ranges are effecient: -- -- 
--   >>> putPretty $ fromRE $ RE.charRange 'a' 'z'
--   0 -> \x -> if
--       | x <= '`'  -> 2
--       | x <= 'z'  -> 1
--       | otherwise -> 2
--   1+ -> \_ -> 2
--   2 -> \_ -> 2 -- black hole
--
-- -- An example with two blackholes: -- -- 
--   >>> putPretty $ fromRE $ "c" <> RE.star RE.anyChar
--   0 -> \x -> if
--       | x <= 'b'  -> 2
--       | x <= 'c'  -> 1
--       | otherwise -> 2
--   1+ -> \_ -> 1 -- black hole
--   2 -> \_ -> 2 -- black hole
--
fromRE :: forall c. (Ord c, Enum c, Bounded c) => RE c -> DFA c -- | Convert DFA to RE. -- -- 
--   >>> putPretty $ toRE $ fromRE "foobar"
--   ^foobar$
--
-- -- For string regular expressions, toRE . fromRE -- = id: -- -- 
--   let s = take 5 s' in RE.string (s :: String) === toRE (fromRE (RE.string s))
--
-- -- But in general it isn't: -- -- 
--   >>> let aToZ = RE.star $ RE.charRange 'a' 'z'
--   
--   >>> traverse_ putPretty [aToZ, toRE $ fromRE aToZ]
--   ^[a-z]*$
--   ^([a-z]|[a-z]?[a-z]*[a-z]?)?$
--
-- -- 
--   not-prop> (re :: RE.RE Char) === toRE (fromRE re)
--
-- -- However, they are equivalent: -- -- 
--   >>> RE.equivalent aToZ (toRE (fromRE aToZ))
--   True
--
-- -- And so are others -- -- 
--   >>> all (\re -> RE.equivalent re (toRE (fromRE re))) [RE.star "a", RE.star "ab"]
--   True
--
-- -- 
--   expensive-prop> RE.equivalent re (toRE (fromRE (re :: RE.RE Char)))
--
-- -- Note, that toRE . fromRE can, and usually makes -- regexp unrecognisable: -- -- 
--   >>> putPretty $ toRE $ fromRE $ RE.star "ab"
--   ^(a(ba)*b)?$
--
-- -- We can complement DFA, therefore we can complement RE. -- For example. regular expression matching string containing an -- a: -- -- 
--   >>> let withA = RE.star RE.anyChar <> "a" <> RE.star RE.anyChar
--   
--   >>> let withoutA = toRE $ complement $ fromRE withA
--   
--   >>> putPretty withoutA
--   ^([^a]|[^a]?[^a]*[^a]?)?$
--
-- -- 
--   >>> let withoutA' = RE.star $ RE.REChars $ RSet.complement $ RSet.singleton 'a'
--   
--   >>> putPretty withoutA'
--   ^[^a]*$
--
-- -- 
--   >>> RE.equivalent withoutA withoutA'
--   True
--
-- -- Quite small, for example 2 state DFAs can result in big regular -- expressions: -- -- 
--   >>> putPretty $ toRE $ complement $ fromRE $ star "ab"
--   ^([^]|a(ba)*(ba)?|a(ba)*([^b]|b[^a])|([^a]|a(ba)*([^b]|b[^a]))[^]*[^]?)$
--
-- -- We can use toRE . fromERE to convert ERE -- to RE: -- -- 
--   >>> putPretty $ toRE $ fromERE $ complement $ star "ab"
--   ^([^]|a(ba)*(ba)?|a(ba)*([^b]|b[^a])|([^a]|a(ba)*([^b]|b[^a]))[^]*[^]?)$
--
-- -- 
--   >>> putPretty $ toRE $ fromERE $ "a" /\ "b"
--   ^[]$
--
-- -- See -- https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous -- for the description of the algorithm used. toRE :: forall c. (Ord c, Enum c, Bounded c) => DFA c -> RE c -- | Convert ERE to DFA. -- -- We don't always generate minimal automata: -- -- 
--   >>> putPretty $ fromERE $ "a" /\ "b"
--   0 -> \_ -> 1
--   1 -> \_ -> 1 -- black hole
--
-- -- Compare this to an complement example -- -- Using fromTMEquiv, we can get minimal automaton, for the cost -- of higher complexity (slow!). -- -- 
--   >>> putPretty $ fromTMEquiv $ ("a" /\ "b" :: ERE.ERE Char)
--   0 -> \_ -> 0 -- black hole
--
-- -- 
--   >>> putPretty $ fromERE $ complement $ star "abc"
--   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
--
fromERE :: forall c. (Ord c, Enum c, Bounded c) => ERE c -> DFA c -- | Convert DFA to ERE. toERE :: forall c. (Ord c, Enum c, Bounded c) => DFA c -> ERE c -- | Create from TransitionMap. -- -- See fromRE for a specific example. fromTM :: forall k c. (Ord k, Ord c, TransitionMap c k) => k -> DFA c -- | Create from TransitonMap minimising states with -- Equivalent. -- -- See fromERE for an example. fromTMEquiv :: forall k c. (Ord k, Ord c, TransitionMap c k, Equivalent c k) => k -> DFA c -- | Convert to any Kleene. -- -- See toRE for a specific example. toKleene :: forall k c. (Ord c, Enum c, Bounded c, FiniteKleene c k) => DFA c -> k instance GHC.Show.Show c => GHC.Show.Show (Kleene.DFA.DFA c) instance GHC.Classes.Ord c => Kleene.Classes.Match c (Kleene.DFA.DFA c) instance Kleene.Classes.Complement c (Kleene.DFA.DFA c) instance GHC.Show.Show c => Kleene.Internal.Pretty.Pretty (Kleene.DFA.DFA c) -- | 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) -- -- 
--   >>> putPretty $ fromTM re
--   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 -> ...
--   ...
--
-- -- And we can convert back from DFA to RE: -- -- 
--   >>> let re' = toKleene (fromTM re) :: 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
--   "abcabcabcabcabcabcdefyz"
--   "abcabcabcabcdefyz"
--   "abcabcabcabcabcabcabcabcabcdefx"
--   "abcabcdefx"
--   "abcabcabcabcabcabcdefyz"
--
-- -- 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. module Kleene -- | 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"). data RE c -- | 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 <math>. -- -- 
--   >>> putPretty $ asEREChar $ "a" /\ "b"
--   ^~(~a|~b)$
--
-- -- There is no generator, as intersections makes it hard. data ERE c -- | 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)
--
newtype Equiv r c Equiv :: (r c) -> Equiv r c -- | Deterministic finite automaton. -- -- A deterministic finite automaton (DFA) over an alphabet <math> -- (type variable c) is 4-tuple <math>, <math> , -- <math>, <math>, where -- -- data DFA c DFA :: !(IntMap (SF c Int)) -> !IntSet -> !IntSet -> DFA c -- | transition function [dfaTransition] :: DFA c -> !(IntMap (SF c Int)) -- | accept states [dfaAcceptable] :: DFA c -> !IntSet -- | states we cannot escape [dfaBlackholes] :: DFA c -> !IntSet -- | Create from TransitionMap. -- -- See fromRE for a specific example. fromTM :: forall k c. (Ord k, Ord c, TransitionMap c k) => k -> DFA c -- | Create from TransitonMap minimising states with -- Equivalent. -- -- See fromERE for an example. fromTMEquiv :: forall k c. (Ord k, Ord c, TransitionMap c k, Equivalent c k) => k -> DFA c -- | Convert to any Kleene. -- -- See toRE for a specific example. toKleene :: forall k c. (Ord c, Enum c, Bounded c, FiniteKleene c k) => DFA c -> k class (BoundedJoinSemiLattice k, Semigroup k, Monoid k) => Kleene c k | k -> c -- | Empty regex. Doesn't accept anything. empty :: Kleene c k => k -- | Empty string. Note: different than empty eps :: Kleene c k => k -- | Single character char :: Kleene c k => c -> k -- | Concatenation. appends :: Kleene c k => [k] -> k -- | Union. unions :: Kleene c k => [k] -> k -- | Kleene star star :: Kleene c k => k -> k class Derivate c k | k -> c -- | Does language contain an empty string? nullable :: Derivate c k => k -> Bool -- | Derivative of a language. derivate :: Derivate c k => c -> k -> k -- | An f can be used to match on the input. class Match c k | k -> c match :: Match c k => k -> [c] -> Bool -- | Transition map. class Derivate c k => TransitionMap c k | k -> c transitionMap :: TransitionMap c k => k -> Map k (SF c k) -- | Complement of the language. -- -- Law: -- -- 
--   matches (complement f) xs = not (matches f) xs
--
class Complement c k | k -> c complement :: Complement c k => k -> k -- | Applicative Functor regular expression. data K c a