-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Kleene algebra
--   
--   Kleene algebra
--   
--   Think: Regular expressions
--   
--   Implements ideas from <i>Regular-expression derivatives
--   re-examined</i> by Scott Owens, John Reppy and Aaron Turon
--   <a>https://doi.org/10.1017/S0956796808007090</a>
@package kleene
@version 0.2

module Kleene.Internal.Partition

-- | <a>Partition</a> devides type into disjoint connected partitions.
--   
--   <i>Note:</i> 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.
--   
--   <tt><a>Partition</a> (fromList [x1, x2, x3]) :: <a>Partition</a>
--   s</tt> describes a partition of <i>Set</i> <tt>s</tt>, as
--   
--   &lt;math&gt;
--   
--   <i>Note:</i> it's enough to check upper bound conditions only if
--   checks are performed in order.
--   
--   <i>Invariant:</i> <a>maxBound</a> 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
fromSeparators :: (Enum a, Bounded a, Ord a) => [a] -> Partition a

-- | Construct <a>Partition</a> from list of <a>RSet</a>s.
--   
--   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 <a>Partition</a>.
--   
--   <pre>
--   &gt;&gt;&gt; size whole
--   1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; size $ split (10 :: Word8)
--   2
--   </pre>
--   
--   <pre>
--   size (asPartitionChar p) &gt;= 1
--   </pre>
size :: Partition a -> Int

-- | Extract examples from each subset in a <a>Partition</a>.
--   
--   <pre>
--   &gt;&gt;&gt; examples $ split (10 :: Word8)
--   fromList [10,255]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; examples $ split (10 :: Word8) &lt;&gt; split 20
--   fromList [10,20,255]
--   </pre>
--   
--   <pre>
--   invariant p ==&gt; size (asPartitionChar p) === length (examples p)
--   </pre>
examples :: (Bounded a, Enum a, Ord a) => Partition a -> Set a

-- | <pre>
--   all (uncurry (&lt;=)) $ intervals $ asPartitionChar p
--   </pre>
intervals :: (Enum a, Bounded a, Ord a) => Partition a -> NonEmpty (a, a)

-- | Wedge partitions.
--   
--   <pre>
--   &gt;&gt;&gt; split (10 :: Word8) &lt;&gt; split 20
--   fromSeparators [10,20]
--   </pre>
--   
--   <pre>
--   whole `wedge` (p :: Partition Char) === p
--   </pre>
--   
--   <pre>
--   (p :: Partition Char) &lt;&gt; whole === p
--   </pre>
--   
--   <pre>
--   asPartitionChar p &lt;&gt; q === q &lt;&gt; p
--   </pre>
--   
--   <pre>
--   asPartitionChar p &lt;&gt; p === p
--   </pre>
--   
--   <pre>
--   invariant $ asPartitionChar p &lt;&gt; q
--   </pre>
wedge :: Ord a => Partition a -> Partition a -> Partition a

-- | Simplest partition: given <tt>x</tt> partition space into <tt>[min..x)
--   and [x .. max]</tt>
--   
--   <pre>
--   &gt;&gt;&gt; split (128 :: Word8)
--   fromSeparators [128]
--   </pre>
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.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.Classes.Eq a => GHC.Classes.Eq (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)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Kleene.Internal.Partition.Partition a)
instance (GHC.Enum.Enum a, GHC.Enum.Bounded a, GHC.Classes.Ord a) => GHC.Base.Semigroup (Kleene.Internal.Partition.Partition a)
instance GHC.Show.Show a => GHC.Show.Show (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 <tt><a>pretty</a> :: <a>RE</a> -&gt; <a>String</a></tt> gives a
--   representation accepted by many regex engines.
class Pretty a
pretty :: Pretty a => a -> String
prettyS :: Pretty a => a -> ShowS

-- | <pre>
--   <a>putStrLn</a> . <a>pretty</a>
--   </pre>
putPretty :: Pretty a => a -> IO ()
instance Kleene.Internal.Pretty.Pretty GHC.Types.Bool
instance Kleene.Internal.Pretty.Pretty GHC.Types.Char
instance (Kleene.Internal.Pretty.Pretty a, Kleene.Internal.Pretty.Pretty b) => Kleene.Internal.Pretty.Pretty (Data.Either.Either a b)
instance GHC.Show.Show a => Kleene.Internal.Pretty.Pretty [a]
instance Kleene.Internal.Pretty.Pretty a => Kleene.Internal.Pretty.Pretty (GHC.Maybe.Maybe a)
instance (c GHC.Types.~ GHC.Types.Char) => Kleene.Internal.Pretty.Pretty (Data.RangeSet.Map.RSet c)
instance (Kleene.Internal.Pretty.Pretty a, Kleene.Internal.Pretty.Pretty b) => Kleene.Internal.Pretty.Pretty (a, b)
instance Kleene.Internal.Pretty.Pretty ()

module Kleene.Classes

-- | Kleene algebra.
--   
--   If <tt>k</tt> is <a>Monoid</a> it's expected that <tt><a>appends</a> =
--   <a>mappend</a></tt>; if <tt>k</tt> is <a>Lattice</a> it's expected
--   that <tt><a>unions</a> = <a>joins</a></tt>.
--   
--   <a>Wikipedia: Kleene Algebra</a>.
class Kleene k

-- | Empty regex. Doesn't accept anything.
empty :: Kleene k => k

-- | Empty string. <i>Note:</i> different than <a>empty</a>.
eps :: Kleene k => k

-- | Concatenation.
appends :: Kleene k => [k] -> k

-- | Union.
unions :: Kleene k => [k] -> k

-- | Kleene star.
star :: Kleene k => k -> k
class Kleene k => CharKleene c k | k -> c

-- | Single character
char :: CharKleene c k => c -> k
string :: CharKleene c k => [c] -> k

-- | One of the characters.
oneof :: (CharKleene c k, Foldable f) => f c -> k
class CharKleene c k => FiniteKleene c k | k -> c

-- | Everything. &lt;math&gt;.
everything :: FiniteKleene c k => k

-- | <tt><a>charRange</a> <tt>a</tt> <tt>z</tt> = ^[a-z]$</tt>.
charRange :: FiniteKleene c k => c -> c -> k

-- | Generalisation of <a>charRange</a>.
fromRSet :: FiniteKleene c k => RSet c -> k

-- | <tt>.</tt> Every character except new line <tt>\n</tt>.
dot :: FiniteKleene c k => k

-- | Any character. <i>Note:</i> different than <a>dot</a>!
anyChar :: FiniteKleene c k => k
notChar :: FiniteKleene c k => c -> k
($dmnotChar) :: (FiniteKleene c k, Ord c, Enum c, Bounded c) => c -> 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 <tt>f</tt> can be used to match on the input.
class Match c k | k -> c
match :: Match c k => k -> [c] -> Bool
match8 :: Match c k => k -> ByteString -> Bool

-- | Equivalence induced by <a>Match</a>.
--   
--   <i>Law:</i>
--   
--   <pre>
--   <a>equivalent</a> re1 re2 <a>=</a> forall s. <a>match</a> re1 s == <a>match</a> re1 s
--   </pre>
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.
--   
--   <i>Law:</i>
--   
--   <pre>
--   <a>match</a> (<a>complement</a> f) xs = <a>not</a> (<a>match</a> f) xs
--   </pre>
class Complement c k | k -> c
complement :: Complement c k => k -> k
class ToLatin1 (k :: Type -> Type)
toLatin1 :: ToLatin1 k => k Char -> k Word8
instance Kleene.Classes.ToLatin1 Data.RangeSet.Map.RSet

module Kleene.Internal.RE

-- | Regular expression
--   
--   Constructors are exposed, but you should use smart constructors in
--   this module to construct <a>RE</a>.
--   
--   The <a>Eq</a> and <a>Ord</a> instances are structural. The
--   <tt>Kleene</tt> etc constructors do "weak normalisation", so for
--   values constructed using those operations <a>Eq</a> witnesses "weak
--   equivalence". See <a>equivalent</a> for regular-expression
--   equivalence.
--   
--   Structure is exposed in <a>Kleene.RE</a> module but consider
--   constructors as half-internal. There are soft-invariants, but
--   violating them shouldn't break anything in the package. (e.g.
--   <a>transitionMap</a> 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.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (empty :: RE Char)
--   ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (bottom :: RE Char)
--   ^[]$
--   </pre>
--   
--   <pre>
--   match (empty :: RE Char) (s :: String) === False
--   </pre>
empty :: RE c

-- | Empty string. <i>Note:</i> different than <a>empty</a>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty eps
--   ^$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (mempty :: RE Char)
--   ^$
--   </pre>
--   
--   <pre>
--   match (eps :: RE Char) s === null (s :: String)
--   </pre>
eps :: RE c

-- | Everything.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty everything
--   ^[^]*$
--   </pre>
--   
--   <pre>
--   match (everything :: RE Char) (s :: String) === True
--   </pre>
everything :: Bounded c => RE c

-- | <pre>
--   &gt;&gt;&gt; putPretty (char 'x')
--   ^x$
--   </pre>
char :: c -> RE c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--   </pre>
charRange :: Ord c => c -> c -> RE c

-- | Any character. <i>Note:</i> different than dot!
--   
--   <pre>
--   &gt;&gt;&gt; putPretty anyChar
--   ^[^]$
--   </pre>
anyChar :: Bounded c => RE c

-- | Concatenate regular expressions.
--   
--   <pre>
--   (asREChar r &lt;&gt; s) &lt;&gt; t === r &lt;&gt; (s &lt;&gt; t)
--   </pre>
--   
--   <pre>
--   asREChar r &lt;&gt; empty === empty
--   </pre>
--   
--   <pre>
--   empty &lt;&gt; asREChar r === empty
--   </pre>
--   
--   <pre>
--   asREChar r &lt;&gt; eps === r
--   </pre>
--   
--   <pre>
--   eps &lt;&gt; asREChar r === r
--   </pre>
appends :: Eq c => [RE c] -> RE c

-- | Union of regular expressions.
--   
--   <pre>
--   asREChar r \/ r === r
--   </pre>
--   
--   <pre>
--   asREChar r \/ s === s \/ r
--   </pre>
--   
--   <pre>
--   (asREChar r \/ s) \/ t === r \/ (s \/ t)
--   </pre>
--   
--   <pre>
--   empty \/ asREChar r === r
--   </pre>
--   
--   <pre>
--   asREChar r \/ empty === r
--   </pre>
--   
--   <pre>
--   everything \/ asREChar r === everything
--   </pre>
--   
--   <pre>
--   asREChar r \/ everything === everything
--   </pre>
unions :: (Ord c, Enum c, Bounded c) => [RE c] -> RE c

-- | Kleene star.
--   
--   <pre>
--   star (star r) === star (asREChar r)
--   </pre>
--   
--   <pre>
--   star eps     === asREChar eps
--   </pre>
--   
--   <pre>
--   star empty   === asREChar eps
--   </pre>
--   
--   <pre>
--   star anyChar === asREChar everything
--   </pre>
--   
--   <pre>
--   star (r      \/ eps) === star (asREChar r)
--   </pre>
--   
--   <pre>
--   star (char c \/ eps) === star (asREChar (char c))
--   </pre>
--   
--   <pre>
--   star (empty  \/ eps) === asREChar eps
--   </pre>
star :: Ord c => RE c -> RE c

-- | Literal string.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("foobar" :: RE Char)
--   ^foobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("(.)" :: RE Char)
--   ^\(\.\)$
--   </pre>
string :: [c] -> RE c

-- | We say that a regular expression r is nullable if the language it
--   defines contains the empty string.
--   
--   <pre>
--   &gt;&gt;&gt; nullable eps
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable (star "x")
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable "foo"
--   False
--   </pre>
nullable :: RE c -> Bool

-- | Intuitively, the derivative of a language &lt;math&gt; with respect to
--   a symbol &lt;math&gt; is the language that includes only those
--   suffixes of strings with a leading symbol &lt;math&gt; in
--   &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'f' "foobar"
--   ^oobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ "xyz" \/ "abc"
--   ^yz$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--   </pre>
derivate :: (Ord c, Enum c, Bounded c) => c -> RE c -> RE c

-- | Transition map. Used to construct <a>DFA</a>.
--   
--   <pre>
--   &gt;&gt;&gt; void $ Map.traverseWithKey (\k v -&gt; putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: RE Char)
--   ^[]$ : \_ -&gt; "^[]$"
--   ^b$ : \x -&gt; if
--       | x &lt;= 'a'  -&gt; "^[]$"
--       | x &lt;= 'b'  -&gt; "^$"
--       | otherwise -&gt; "^[]$"
--   ^$ : \_ -&gt; "^[]$"
--   ^ab$ : \x -&gt; if
--       | x &lt;= '`'  -&gt; "^[]$"
--       | x &lt;= 'a'  -&gt; "^b$"
--       | otherwise -&gt; "^[]$"
--   </pre>
transitionMap :: (Ord c, Enum c, Bounded c) => RE c -> Map (RE c) (SF c (RE c))

-- | Leading character sets of regular expression.
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars "foo"
--   fromSeparators "ef"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars (star "b" &lt;&gt; star "e")
--   fromSeparators "abde"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars (charRange 'b' 'z')
--   fromSeparators "az"
--   </pre>
leadingChars :: (Ord c, Enum c, Bounded c) => RE c -> Partition c

-- | Whether two regexps are equivalent.
--   
--   <pre>
--   <a>equivalent</a> re1 re2 <a>=</a> forall s. <tt>match</tt> re1 s === <tt>match</tt> re1 s
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = star "a" &lt;&gt; "a"
--   
--   &gt;&gt;&gt; let re2 = "a" &lt;&gt; star "a"
--   </pre>
--   
--   These are different regular expressions, even we perform some
--   normalisation-on-construction:
--   
--   <pre>
--   &gt;&gt;&gt; re1 == re2
--   False
--   </pre>
--   
--   They are however equivalent:
--   
--   <pre>
--   &gt;&gt;&gt; equivalent re1 re2
--   True
--   </pre>
--   
--   The algorithm works by executing <tt>states</tt> on "product" regexp,
--   and checking whether all resulting states are both accepting or
--   rejecting.
--   
--   <pre>
--   re1 == re2 ==&gt; <a>equivalent</a> re1 re2
--   </pre>
--   
--   <h3>More examples</h3>
--   
--   <pre>
--   &gt;&gt;&gt; let example re1 re2 = putPretty re1 &gt;&gt; putPretty re2 &gt;&gt; return (equivalent re1 re2)
--   
--   &gt;&gt;&gt; example re1 re2
--   ^a*a$
--   ^aa*$
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star "aa") (star "aaa")
--   ^(aa)*$
--   ^(aaa)*$
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star "aa" &lt;&gt; star "aaa") (star "aaa" &lt;&gt; star "aa")
--   ^(aa)*(aaa)*$
--   ^(aaa)*(aa)*$
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star ("a" \/ "b")) (star $ star "a" &lt;&gt; star "b")
--   ^[a-b]*$
--   ^(a*b*)*$
--   True
--   </pre>
equivalent :: (Ord c, Enum c, Bounded c) => RE c -> RE c -> Bool

-- | Generate random strings of the language <tt>RE c</tt> describes.
--   
--   <pre>
--   &gt;&gt;&gt; let example = traverse_ print . take 3 . generate (curry QC.choose) 42
--   
--   &gt;&gt;&gt; example "abc"
--   "abc"
--   "abc"
--   "abc"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example $ star $ "a" \/ "b"
--   ""
--   "bbaabbaaba"
--   "b"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example empty
--   </pre>
--   
--   <pre>
--   all (match r) $ take 10 $ generate (curry QC.choose) 42 (r :: RE Char)
--   </pre>
generate :: (c -> c -> Gen c) -> Int -> RE c -> [[c]]

-- | Whether <a>RE</a> is (structurally) equal to <a>empty</a>.
--   
--   <pre>
--   isEmpty r === all (not . nullable) (Map.keys $ transitionMap $ asREChar r)
--   </pre>
isEmpty :: RE c -> Bool

-- | Not only we can decide whether <a>RE</a> is nullable, we can also
--   remove the empty string:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof eps
--   ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof $ star "x"
--   ^xx*$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof "foo"
--   Nothing
--   </pre>
--   
--   <a>nullableProof</a> is consistent with <a>nullable</a>:
--   
--   <pre>
--   isJust (nullableProof r) === nullable (asREChar r)
--   </pre>
--   
--   The returned regular expression is not nullable:
--   
--   <pre>
--   maybe True (not . nullable) $ nullableProof $ asREChar r
--   </pre>
--   
--   If we union with empty regex, we get a equivalent regular expression
--   we started with:
--   
--   <pre>
--   maybe r (eps \/) (nullableProof r) `equivalent` (asREChar r)
--   </pre>
nullableProof :: (Ord c, Enum c, Bounded c) => RE c -> Maybe (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.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.CharKleene c (Kleene.Internal.RE.RE c)
instance Test.QuickCheck.Arbitrary.CoArbitrary c => Test.QuickCheck.Arbitrary.CoArbitrary (Kleene.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Derivate c (Kleene.Internal.RE.RE c)
instance GHC.Classes.Eq c => GHC.Classes.Eq (Kleene.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Equivalent c (Kleene.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.FiniteKleene c (Kleene.Internal.RE.RE c)
instance (c GHC.Types.~ GHC.Types.Char) => Data.String.IsString (Kleene.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Kleene (Kleene.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Match c (Kleene.Internal.RE.RE c)
instance GHC.Classes.Eq c => GHC.Base.Monoid (Kleene.Internal.RE.RE c)
instance GHC.Classes.Ord c => GHC.Classes.Ord (Kleene.Internal.RE.RE c)
instance (c GHC.Types.~ GHC.Types.Char) => Kleene.Internal.Pretty.Pretty (Kleene.Internal.RE.RE c)
instance GHC.Classes.Eq c => GHC.Base.Semigroup (Kleene.Internal.RE.RE c)
instance GHC.Show.Show c => GHC.Show.Show (Kleene.Internal.RE.RE c)
instance Kleene.Classes.ToLatin1 Kleene.Internal.RE.RE
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.TransitionMap c (Kleene.Internal.RE.RE c)

module Kleene.Equiv

-- | Regular-expressions for which <a>==</a> is <a>equivalent</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = star "a" &lt;&gt; "a" :: RE Char
--   
--   &gt;&gt;&gt; let re2 = "a" &lt;&gt; star "a" :: RE Char
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; re1 == re2
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Equiv re1 == Equiv re2
--   True
--   </pre>
--   
--   <a>Equiv</a> is also a <a>PartialOrd</a> (but not <a>Ord</a>!)
--   
--   <pre>
--   &gt;&gt;&gt; Equiv "a" `leq` Equiv (star "a" :: RE Char)
--   True
--   </pre>
--   
--   Not all regular expessions are <a>comparable</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let reA = Equiv "a" :: Equiv RE Char
--   
--   &gt;&gt;&gt; let reB = Equiv "b" :: Equiv RE Char
--   
--   &gt;&gt;&gt; (leq reA reB, leq reB reA)
--   (False,False)
--   </pre>
newtype Equiv (r :: Type -> Type) c
Equiv :: r c -> Equiv (r :: Type -> Type) c
instance Algebra.Lattice.BoundedJoinSemiLattice (r c) => Algebra.Lattice.BoundedJoinSemiLattice (Kleene.Equiv.Equiv r c)
instance Algebra.Lattice.BoundedMeetSemiLattice (r c) => Algebra.Lattice.BoundedMeetSemiLattice (Kleene.Equiv.Equiv r c)
instance Kleene.Classes.CharKleene c (r c) => Kleene.Classes.CharKleene 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.Derivate c (r c) => Kleene.Classes.Derivate c (Kleene.Equiv.Equiv r c)
instance Kleene.Classes.Equivalent c (r c) => GHC.Classes.Eq (Kleene.Equiv.Equiv r c)
instance Kleene.Classes.Equivalent c (r c) => Kleene.Classes.Equivalent c (Kleene.Equiv.Equiv r c)
instance Kleene.Classes.Kleene (r c) => Kleene.Classes.Kleene (Kleene.Equiv.Equiv r c)
instance Algebra.Lattice.Lattice (r c) => Algebra.Lattice.Lattice (Kleene.Equiv.Equiv r c)
instance Kleene.Classes.Match c (r c) => Kleene.Classes.Match c (Kleene.Equiv.Equiv r c)
instance GHC.Base.Monoid (r c) => GHC.Base.Monoid (Kleene.Equiv.Equiv r c)
instance (Algebra.Lattice.Lattice (r c), Kleene.Classes.Equivalent c (r c)) => Algebra.PartialOrd.PartialOrd (Kleene.Equiv.Equiv r c)
instance Kleene.Internal.Pretty.Pretty (r c) => Kleene.Internal.Pretty.Pretty (Kleene.Equiv.Equiv r c)
instance GHC.Base.Semigroup (r c) => GHC.Base.Semigroup (Kleene.Equiv.Equiv r c)
instance GHC.Show.Show (r c) => GHC.Show.Show (Kleene.Equiv.Equiv r c)

module Kleene.ERE

-- | Extended regular expression
--   
--   It's both, <i>Kleene</i> and <i>Boolean</i> algebra. (If we add only
--   intersections, it wouldn't be <i>Boolean</i>).
--   
--   <i>Note:</i> we don't have special constructor for intersections. We
--   use de Morgan formula &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ asEREChar $ "a" /\ "b"
--   ^~(~a|~b)$
--   </pre>
--   
--   There is no generator, as <a>intersections</a> 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.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (empty :: ERE Char)
--   ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (bottom :: ERE Char)
--   ^[]$
--   </pre>
--   
--   <pre>
--   match (empty :: ERE Char) (s :: String) === False
--   </pre>
empty :: ERE c

-- | Empty string. <i>Note:</i> different than <a>empty</a>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty eps
--   ^$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (mempty :: ERE Char)
--   ^$
--   </pre>
--   
--   <pre>
--   match (eps :: ERE Char) s === null (s :: String)
--   </pre>
eps :: ERE c

-- | Everything.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (everything :: ERE Char)
--   ^~[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (top :: ERE Char)
--   ^~[]$
--   </pre>
--   
--   <pre>
--   match (everything :: ERE Char) (s :: String) === True
--   </pre>
everything :: ERE c

-- | <pre>
--   &gt;&gt;&gt; putPretty (char 'x')
--   ^x$
--   </pre>
char :: c -> ERE c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--   </pre>
charRange :: Ord c => c -> c -> ERE c

-- | Any character. <i>Note:</i> different than dot!
--   
--   <pre>
--   &gt;&gt;&gt; putPretty anyChar
--   ^[^]$
--   </pre>
anyChar :: Bounded c => ERE c

-- | Concatenate regular expressions.
--   
--   <pre>
--   asEREChar r &lt;&gt; empty === empty
--   </pre>
--   
--   <pre>
--   empty &lt;&gt; asEREChar r === empty
--   </pre>
--   
--   <pre>
--   (asEREChar r &lt;&gt; s) &lt;&gt; t === r &lt;&gt; (s &lt;&gt; t)
--   </pre>
--   
--   <pre>
--   asEREChar r &lt;&gt; eps === r
--   </pre>
--   
--   <pre>
--   eps &lt;&gt; asEREChar r === r
--   </pre>
appends :: Eq c => [ERE c] -> ERE c

-- | Union of regular expressions.
--   
--   <pre>
--   asEREChar r \/ r === r
--   </pre>
--   
--   <pre>
--   asEREChar r \/ s === s \/ r
--   </pre>
--   
--   <pre>
--   (asEREChar r \/ s) \/ t === r \/ (s \/ t)
--   </pre>
--   
--   <pre>
--   empty \/ asEREChar r === r
--   </pre>
--   
--   <pre>
--   asEREChar r \/ empty === r
--   </pre>
--   
--   <pre>
--   everything \/ asEREChar r === everything
--   </pre>
--   
--   <pre>
--   asEREChar r \/ everything === everything
--   </pre>
unions :: (Ord c, Enum c) => [ERE c] -> ERE c

-- | Intersection of regular expressions.
--   
--   <pre>
--   asEREChar r /\ r === r
--   </pre>
--   
--   <pre>
--   asEREChar r /\ s === s /\ r
--   </pre>
--   
--   <pre>
--   (asEREChar r /\ s) /\ t === r /\ (s /\ t)
--   </pre>
--   
--   <pre>
--   empty /\ asEREChar r === empty
--   </pre>
--   
--   <pre>
--   asEREChar r /\ empty === empty
--   </pre>
--   
--   <pre>
--   everything /\ asEREChar r === r
--   </pre>
--   
--   <pre>
--   asEREChar r /\ everything === r
--   </pre>
intersections :: (Ord c, Enum c) => [ERE c] -> ERE c

-- | Kleene star.
--   
--   <pre>
--   star (star r) === star (asEREChar r)
--   </pre>
--   
--   <pre>
--   star eps     === asEREChar eps
--   </pre>
--   
--   <pre>
--   star empty   === asEREChar eps
--   </pre>
--   
--   <pre>
--   star anyChar === asEREChar everything
--   </pre>
--   
--   <pre>
--   star (asEREChar r \/ eps) === star r
--   </pre>
--   
--   <pre>
--   star (char c \/ eps) === star (char (c :: Char))
--   </pre>
--   
--   <pre>
--   star (empty \/ eps) === eps
--   </pre>
star :: (Ord c, Bounded c) => ERE c -> ERE c

-- | Literal string.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("foobar" :: ERE Char)
--   ^foobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("(.)" :: ERE Char)
--   ^\(\.\)$
--   </pre>
string :: [c] -> ERE c

-- | Complement.
--   
--   <pre>
--   complement (complement r) === asEREChar r
--   </pre>
complement :: ERE c -> ERE c

-- | We say that a regular expression r is nullable if the language it
--   defines contains the empty string.
--   
--   <pre>
--   &gt;&gt;&gt; nullable eps
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable (star "x")
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable "foo"
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable (complement eps)
--   False
--   </pre>
nullable :: ERE c -> Bool

-- | Intuitively, the derivative of a language &lt;math&gt; with respect to
--   a symbol &lt;math&gt; is the language that includes only those
--   suffixes of strings with a leading symbol &lt;math&gt; in
--   &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'f' "foobar"
--   ^oobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ "xyz" \/ "abc"
--   ^yz$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--   </pre>
derivate :: (Ord c, Enum c) => c -> ERE c -> ERE c

-- | Convert from ordinary regular expression, <a>RE</a>.
fromRE :: Ord c => RE c -> ERE c

-- | Transition map. Used to construct <a>DFA</a>.
--   
--   <pre>
--   &gt;&gt;&gt; void $ Map.traverseWithKey (\k v -&gt; putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: ERE Char)
--   ^[]$ : \_ -&gt; "^[]$"
--   ^b$ : \x -&gt; if
--       | x &lt;= 'a'  -&gt; "^[]$"
--       | x &lt;= 'b'  -&gt; "^$"
--       | otherwise -&gt; "^[]$"
--   ^$ : \_ -&gt; "^[]$"
--   ^ab$ : \x -&gt; if
--       | x &lt;= '`'  -&gt; "^[]$"
--       | x &lt;= 'a'  -&gt; "^b$"
--       | otherwise -&gt; "^[]$"
--   </pre>
transitionMap :: (Ord c, Enum c, Bounded c) => ERE c -> Map (ERE c) (SF c (ERE c))

-- | Leading character sets of regular expression.
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars "foo"
--   fromSeparators "ef"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars (star "b" &lt;&gt; star "e")
--   fromSeparators "abde"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars (charRange 'b' 'z')
--   fromSeparators "az"
--   </pre>
leadingChars :: (Ord c, Enum c, Bounded c) => ERE c -> Partition c

-- | Whether two regexps are equivalent.
--   
--   <pre>
--   <a>equivalent</a> re1 re2 <a>=</a> forall s. <tt>match</tt> re1 s == <tt>match</tt> re1 s
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = star "a" &lt;&gt; "a"
--   
--   &gt;&gt;&gt; let re2 = "a" &lt;&gt; star "a"
--   </pre>
--   
--   These are different regular expressions, even we perform some
--   normalisation-on-construction:
--   
--   <pre>
--   &gt;&gt;&gt; re1 == re2
--   False
--   </pre>
--   
--   They are however equivalent:
--   
--   <pre>
--   &gt;&gt;&gt; equivalent re1 re2
--   True
--   </pre>
--   
--   The algorithm works by executing <tt>states</tt> on "product" regexp,
--   and checking whether all resulting states are both accepting or
--   rejecting.
--   
--   <pre>
--   re1 == re2 ==&gt; <a>equivalent</a> re1 re2
--   </pre>
--   
--   <h3>More examples</h3>
--   
--   <pre>
--   &gt;&gt;&gt; let example re1 re2 = putPretty re1 &gt;&gt; putPretty re2 &gt;&gt; return (equivalent re1 re2)
--   
--   &gt;&gt;&gt; example re1 re2
--   ^a*a$
--   ^aa*$
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star "aa") (star "aaa")
--   ^(aa)*$
--   ^(aaa)*$
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star "aa" &lt;&gt; star "aaa") (star "aaa" &lt;&gt; star "aa")
--   ^(aa)*(aaa)*$
--   ^(aaa)*(aa)*$
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star ("a" \/ "b")) (star $ star "a" &lt;&gt; star "b")
--   ^[a-b]*$
--   ^(a*b*)*$
--   True
--   </pre>
equivalent :: (Ord c, Enum c, Bounded c) => ERE c -> ERE c -> Bool

-- | Whether <a>ERE</a> is (structurally) equal to <a>empty</a>.
isEmpty :: ERE c -> Bool

-- | Whether <a>ERE</a> is (structurally) equal to <a>everything</a>.
isEverything :: ERE c -> Bool
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 (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.BoundedMeetSemiLattice (Kleene.ERE.ERE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.CharKleene c (Kleene.ERE.ERE c)
instance Test.QuickCheck.Arbitrary.CoArbitrary c => Test.QuickCheck.Arbitrary.CoArbitrary (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.Eq c => GHC.Classes.Eq (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.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.FiniteKleene c (Kleene.ERE.ERE c)
instance (c GHC.Types.~ GHC.Types.Char) => Data.String.IsString (Kleene.ERE.ERE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Kleene (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) => Kleene.Classes.Match c (Kleene.ERE.ERE c)
instance GHC.Classes.Eq c => GHC.Base.Monoid (Kleene.ERE.ERE c)
instance GHC.Classes.Ord c => GHC.Classes.Ord (Kleene.ERE.ERE c)
instance (c GHC.Types.~ GHC.Types.Char) => Kleene.Internal.Pretty.Pretty (Kleene.ERE.ERE c)
instance GHC.Classes.Eq c => GHC.Base.Semigroup (Kleene.ERE.ERE c)
instance GHC.Show.Show c => GHC.Show.Show (Kleene.ERE.ERE c)
instance Kleene.Classes.ToLatin1 Kleene.ERE.ERE
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.TransitionMap c (Kleene.ERE.ERE c)

module Kleene.DFA

-- | Deterministic finite automaton.
--   
--   A deterministic finite automaton (DFA) over an alphabet &lt;math&gt;
--   (type variable <tt>c</tt>) is 4-tuple &lt;math&gt;, &lt;math&gt; ,
--   &lt;math&gt;, &lt;math&gt;, where
--   
--   <ul>
--   <li>&lt;math&gt; is a finite set of states (subset of
--   <tt>s</tt>),</li>
--   <li>&lt;math&gt; is the distinguised start state
--   (<a>dfaInitial</a>),</li>
--   <li>&lt;math&gt; is a set of final (or accepting) states
--   (<a>dfaAcceptable</a>), and</li>
--   <li>&lt;math&gt; is a function called the state transition function
--   (<a>dfaTransition</a>).</li>
--   </ul>
data DFA c
DFA :: !IntMap (SF c Int) -> !Int -> !IntSet -> !IntSet -> DFA c

-- | transition function
[dfaTransition] :: DFA c -> !IntMap (SF c Int)

-- | initial state
[dfaInitial] :: DFA c -> !Int

-- | accept states
[dfaAcceptable] :: DFA c -> !IntSet

-- | states we cannot escape
[dfaBlackholes] :: DFA c -> !IntSet

-- | Convert <a>RE</a> to <a>DFA</a>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromRE $ RE.star "abc"
--   0+ -&gt; \x -&gt; if
--       | x &lt;= '`'  -&gt; 3
--       | x &lt;= 'a'  -&gt; 2
--       | otherwise -&gt; 3
--   1 -&gt; \x -&gt; if
--       | x &lt;= 'b'  -&gt; 3
--       | x &lt;= 'c'  -&gt; 0
--       | otherwise -&gt; 3
--   2 -&gt; \x -&gt; if
--       | x &lt;= 'a'  -&gt; 3
--       | x &lt;= 'b'  -&gt; 1
--       | otherwise -&gt; 3
--   3 -&gt; \_ -&gt; 3 -- black hole
--   </pre>
--   
--   Everything and nothing result in blackholes:
--   
--   <pre>
--   &gt;&gt;&gt; traverse_ (putPretty . fromRE) [RE.empty, RE.star RE.anyChar]
--   0 -&gt; \_ -&gt; 0 -- black hole
--   0+ -&gt; \_ -&gt; 0 -- black hole
--   </pre>
--   
--   Character ranges are effecient:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromRE $ RE.charRange 'a' 'z'
--   0 -&gt; \x -&gt; if
--       | x &lt;= '`'  -&gt; 2
--       | x &lt;= 'z'  -&gt; 1
--       | otherwise -&gt; 2
--   1+ -&gt; \_ -&gt; 2
--   2 -&gt; \_ -&gt; 2 -- black hole
--   </pre>
--   
--   An example with two blackholes:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromRE $ "c" &lt;&gt; RE.star RE.anyChar
--   0 -&gt; \x -&gt; if
--       | x &lt;= 'b'  -&gt; 2
--       | x &lt;= 'c'  -&gt; 1
--       | otherwise -&gt; 2
--   1+ -&gt; \_ -&gt; 1 -- black hole
--   2 -&gt; \_ -&gt; 2 -- black hole
--   </pre>
fromRE :: (Ord c, Enum c, Bounded c) => RE c -> DFA c

-- | Convert <a>DFA</a> to <a>RE</a>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ toRE $ fromRE "foobar"
--   ^foobar$
--   </pre>
--   
--   For <a>string</a> regular expressions, <tt><a>toRE</a> . <a>fromRE</a>
--   = <a>id</a></tt>:
--   
--   <pre>
--   let s' = take 5 s in RE.string (s' :: String) === toRE (fromRE (RE.string s'))
--   </pre>
--   
--   But in general it isn't:
--   
--   <pre>
--   &gt;&gt;&gt; let aToZ = RE.star $ RE.charRange 'a' 'z'
--   
--   &gt;&gt;&gt; traverse_ putPretty [aToZ, toRE $ fromRE aToZ]
--   ^[a-z]*$
--   ^([a-z]|[a-z]?[a-z]*[a-z]?)?$
--   </pre>
--   
--   <pre>
--   not-prop&gt; (re :: RE.RE Char) === toRE (fromRE re)
--   </pre>
--   
--   However, they are <a>equivalent</a>:
--   
--   <pre>
--   &gt;&gt;&gt; RE.equivalent aToZ (toRE (fromRE aToZ))
--   True
--   </pre>
--   
--   And so are others
--   
--   <pre>
--   &gt;&gt;&gt; all (\re -&gt; RE.equivalent re (toRE (fromRE re))) [RE.star "a", RE.star "ab"]
--   True
--   </pre>
--   
--   <pre>
--   expensive-prop&gt; RE.equivalent re (toRE (fromRE (re :: RE.RE Char)))
--   </pre>
--   
--   Note, that <tt><a>toRE</a> . <a>fromRE</a></tt> can, and usually makes
--   regexp unrecognisable:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ toRE $ fromRE $ RE.star "ab"
--   ^(a(ba)*b)?$
--   </pre>
--   
--   We can <a>complement</a> DFA, therefore we can complement <a>RE</a>.
--   For example. regular expression matching string containing an
--   <tt>a</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; let withA = RE.star RE.anyChar &lt;&gt; "a" &lt;&gt; RE.star RE.anyChar
--   
--   &gt;&gt;&gt; let withoutA = toRE $ complement $ fromRE withA
--   
--   &gt;&gt;&gt; putPretty withoutA
--   ^([^a]|[^a]?[^a]*[^a]?)?$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let withoutA' = RE.star $ RE.REChars $ RSet.complement $ RSet.singleton 'a'
--   
--   &gt;&gt;&gt; putPretty withoutA'
--   ^[^a]*$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; RE.equivalent withoutA withoutA'
--   True
--   </pre>
--   
--   Quite small, for example 2 state DFAs can result in big regular
--   expressions:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ toRE $ complement $ fromRE $ star "ab"
--   ^([^]|a(ba)*(ba)?|a(ba)*([^b]|b[^a])|([^a]|a(ba)*([^b]|b[^a]))[^]*[^]?)$
--   </pre>
--   
--   We can use <tt><a>toRE</a> . <a>fromERE</a></tt> to convert <a>ERE</a>
--   to <a>RE</a>:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ toRE $ fromERE $ complement $ star "ab"
--   ^([^]|a(ba)*(ba)?|a(ba)*([^b]|b[^a])|([^a]|a(ba)*([^b]|b[^a]))[^]*[^]?)$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ toRE $ fromERE $ "a" /\ "b"
--   ^[]$
--   </pre>
--   
--   See
--   <a>https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous</a>
--   for the description of the algorithm used.
toRE :: (Ord c, Enum c, Bounded c) => DFA c -> RE c

-- | Convert <a>ERE</a> to <a>DFA</a>.
--   
--   We don't always generate a minimal automata:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromERE $ "a" /\ "b"
--   0 -&gt; \_ -&gt; 1
--   1 -&gt; \_ -&gt; 1 -- black hole
--   </pre>
--   
--   Compare this to a <a>complement</a> example
--   
--   Using <a>fromTMEquiv</a>, we can get a minimal automaton, for the cost
--   of higher complexity (slow!).
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromTMEquiv $ ("a" /\ "b" :: ERE.ERE Char)
--   0 -&gt; \_ -&gt; 0 -- black hole
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromERE $ complement $ star "abc"
--   0 -&gt; \x -&gt; if
--       | x &lt;= '`'  -&gt; 3
--       | x &lt;= 'a'  -&gt; 2
--       | otherwise -&gt; 3
--   1+ -&gt; \x -&gt; if
--       | x &lt;= 'b'  -&gt; 3
--       | x &lt;= 'c'  -&gt; 0
--       | otherwise -&gt; 3
--   2+ -&gt; \x -&gt; if
--       | x &lt;= 'a'  -&gt; 3
--       | x &lt;= 'b'  -&gt; 1
--       | otherwise -&gt; 3
--   3+ -&gt; \_ -&gt; 3 -- black hole
--   </pre>
fromERE :: (Ord c, Enum c, Bounded c) => ERE c -> DFA c

-- | Convert <a>DFA</a> to <a>ERE</a>.
toERE :: (Ord c, Enum c, Bounded c) => DFA c -> ERE c

-- | Create from <a>TransitionMap</a>.
--   
--   See <a>fromRE</a> for a specific example.
fromTM :: (Ord k, Ord c, TransitionMap c k) => k -> DFA c

-- | Create from <tt>TransitonMap</tt> minimising states with
--   <a>Equivalent</a>.
--   
--   See <a>fromERE</a> for an example.
fromTMEquiv :: (Ord k, Ord c, TransitionMap c k, Equivalent c k) => k -> DFA c

-- | Convert to any <a>Kleene</a>.
--   
--   See <a>toRE</a> for a specific example.
toKleene :: forall k c. (Ord c, Enum c, Bounded c, FiniteKleene c k) => DFA c -> k

-- | Get Graphviz dot-code of DFA.
--   
--   <pre>
--   &gt;&gt;&gt; let dfa = fromRE $ RE.star "abc"
--   
--   &gt;&gt;&gt; putStr $ toDot dfa
--   digraph dfa {
--   rankdir=LR;
--   // states
--   "0" [shape=doublecircle];
--   "1" [shape=circle];
--   "2" [shape=circle];
--   // initial state
--   "" [shape=none];
--   "" -&gt; "0";
--   // transitions
--   "0" -&gt; "2"[label="a"]
--   "1" -&gt; "0"[label="c"]
--   "2" -&gt; "1"[label="b"]
--   }
--   </pre>
toDot :: DFA Char -> String

-- | More flexible version of <a>toDot</a>.
toDot' :: (Ord c, Enum c, Bounded c) => (Int -> String) -> (c -> String) -> DFA c -> String
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Algebra.Lattice.BoundedJoinSemiLattice (Kleene.Internal.RE.RE c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Algebra.Lattice.BoundedMeetSemiLattice (Kleene.Internal.RE.RE c)
instance Kleene.Classes.Complement c (Kleene.DFA.DFA c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Kleene.Classes.Complement c (Kleene.Internal.RE.RE c)
instance GHC.Classes.Ord c => Kleene.Classes.Derivate c (Kleene.DFA.DFA c)
instance (GHC.Classes.Ord c, GHC.Enum.Enum c, GHC.Enum.Bounded c) => Algebra.Lattice.Lattice (Kleene.Internal.RE.RE c)
instance GHC.Classes.Ord c => Kleene.Classes.Match c (Kleene.DFA.DFA c)
instance GHC.Show.Show c => Kleene.Internal.Pretty.Pretty (Kleene.DFA.DFA c)
instance GHC.Show.Show c => GHC.Show.Show (Kleene.DFA.DFA c)

module Kleene.Monad

-- | Regular expression which has no restrictions on the elements.
--   Therefore we can have <a>Monad</a> 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!
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ string [True, False]
--   ^10$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let re  = string [True, False, True]
--   
--   &gt;&gt;&gt; let re' = re &gt;&gt;= \b -&gt; if b then char () else star (char ())
--   
--   &gt;&gt;&gt; putPretty re'
--   ^..*.$
--   </pre>
data 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.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (empty :: M Bool)
--   ^[]$
--   </pre>
--   
--   <pre>
--   match (empty :: M Char) (s :: String) === False
--   </pre>
empty :: M c

-- | Empty string. <i>Note:</i> different than <a>empty</a>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (eps :: M Bool)
--   ^$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (mempty :: M Bool)
--   ^$
--   </pre>
--   
--   <pre>
--   match (eps :: M Char) s === null (s :: String)
--   </pre>
eps :: M c

-- | <pre>
--   &gt;&gt;&gt; putPretty (char 'x')
--   ^x$
--   </pre>
char :: c -> M c

-- | <i>Note:</i> we know little about <tt>c</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[abcdefghijklmnopqrstuvwxyz]$
--   </pre>
charRange :: Enum c => c -> c -> M c

-- | Any character. <i>Note:</i> different than dot!
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (anyChar :: M Bool)
--   ^[01]$
--   </pre>
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.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("foobar" :: M Char)
--   ^foobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("(.)" :: M Char)
--   ^\(\.\)$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ string [False, True]
--   ^01$
--   </pre>
string :: [c] -> M c

-- | We say that a regular expression r is nullable if the language it
--   defines contains the empty string.
--   
--   <pre>
--   &gt;&gt;&gt; nullable eps
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable (star "x")
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable "foo"
--   False
--   </pre>
nullable :: M c -> Bool

-- | Intuitively, the derivative of a language &lt;math&gt; with respect to
--   a symbol &lt;math&gt; is the language that includes only those
--   suffixes of strings with a leading symbol &lt;math&gt; in
--   &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'f' "foobar"
--   ^oobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ unions ["xyz", "abc"]
--   ^yz$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--   </pre>
derivate :: (Eq c, Enum c, Bounded c) => c -> M c -> M c

-- | Generate random strings of the language <tt>M c</tt> describes.
--   
--   <pre>
--   &gt;&gt;&gt; let example = traverse_ print . take 3 . generate 42
--   
--   &gt;&gt;&gt; example "abc"
--   "abc"
--   "abc"
--   "abc"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example $ star $ unions ["a", "b"]
--   ""
--   "aaababaaab"
--   "a"
--   </pre>
--   
--   xx &gt;&gt;&gt; example empty
--   
--   expensive-prop&gt; all (match r) $ take 10 $ generate 42 (r :: M Bool)
generate :: Int -> M c -> [[c]]

-- | Convert to <tt>Kleene</tt>
--   
--   <pre>
--   &gt;&gt;&gt; let re = charRange 'a' 'z'
--   
--   &gt;&gt;&gt; putPretty re
--   ^[abcdefghijklmnopqrstuvwxyz]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (toKleene re :: RE Char)
--   ^[a-z]$
--   </pre>
toKleene :: CharKleene c k => M c -> k

-- | Whether <a>M</a> is (structurally) equal to <a>empty</a>.
isEmpty :: M c -> Bool

-- | Whether <a>M</a> is (structurally) equal to <a>eps</a>.
isEps :: M c -> Bool
instance GHC.Base.Applicative Kleene.Monad.M
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 Kleene.Classes.CharKleene c (Kleene.Monad.M c)
instance Test.QuickCheck.Arbitrary.CoArbitrary c => Test.QuickCheck.Arbitrary.CoArbitrary (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.Classes.Eq (Kleene.Monad.M c)
instance Data.Foldable.Foldable Kleene.Monad.M
instance GHC.Base.Functor Kleene.Monad.M
instance (c GHC.Types.~ GHC.Types.Char) => Data.String.IsString (Kleene.Monad.M c)
instance Kleene.Classes.Kleene (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 GHC.Base.Monad Kleene.Monad.M
instance GHC.Base.Monoid (Kleene.Monad.M c)
instance GHC.Classes.Ord c => GHC.Classes.Ord (Kleene.Monad.M c)
instance (Kleene.Internal.Pretty.Pretty c, GHC.Classes.Eq c) => Kleene.Internal.Pretty.Pretty (Kleene.Monad.M c)
instance GHC.Base.Semigroup (Kleene.Monad.M c)
instance GHC.Show.Show c => GHC.Show.Show (Kleene.Monad.M c)
instance Data.Traversable.Traversable Kleene.Monad.M

module Kleene.RE

-- | Regular expression
--   
--   Constructors are exposed, but you should use smart constructors in
--   this module to construct <a>RE</a>.
--   
--   The <a>Eq</a> and <a>Ord</a> instances are structural. The
--   <tt>Kleene</tt> etc constructors do "weak normalisation", so for
--   values constructed using those operations <a>Eq</a> witnesses "weak
--   equivalence". See <a>equivalent</a> for regular-expression
--   equivalence.
--   
--   Structure is exposed in <a>Kleene.RE</a> module but consider
--   constructors as half-internal. There are soft-invariants, but
--   violating them shouldn't break anything in the package. (e.g.
--   <a>transitionMap</a> 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.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (empty :: RE Char)
--   ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (bottom :: RE Char)
--   ^[]$
--   </pre>
--   
--   <pre>
--   match (empty :: RE Char) (s :: String) === False
--   </pre>
empty :: RE c

-- | Empty string. <i>Note:</i> different than <a>empty</a>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty eps
--   ^$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (mempty :: RE Char)
--   ^$
--   </pre>
--   
--   <pre>
--   match (eps :: RE Char) s === null (s :: String)
--   </pre>
eps :: RE c

-- | Everything.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty everything
--   ^[^]*$
--   </pre>
--   
--   <pre>
--   match (everything :: RE Char) (s :: String) === True
--   </pre>
everything :: Bounded c => RE c

-- | <pre>
--   &gt;&gt;&gt; putPretty (char 'x')
--   ^x$
--   </pre>
char :: c -> RE c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--   </pre>
charRange :: Ord c => c -> c -> RE c

-- | Any character. <i>Note:</i> different than dot!
--   
--   <pre>
--   &gt;&gt;&gt; putPretty anyChar
--   ^[^]$
--   </pre>
anyChar :: Bounded c => RE c

-- | Concatenate regular expressions.
--   
--   <pre>
--   (asREChar r &lt;&gt; s) &lt;&gt; t === r &lt;&gt; (s &lt;&gt; t)
--   </pre>
--   
--   <pre>
--   asREChar r &lt;&gt; empty === empty
--   </pre>
--   
--   <pre>
--   empty &lt;&gt; asREChar r === empty
--   </pre>
--   
--   <pre>
--   asREChar r &lt;&gt; eps === r
--   </pre>
--   
--   <pre>
--   eps &lt;&gt; asREChar r === r
--   </pre>
appends :: Eq c => [RE c] -> RE c

-- | Union of regular expressions.
--   
--   <pre>
--   asREChar r \/ r === r
--   </pre>
--   
--   <pre>
--   asREChar r \/ s === s \/ r
--   </pre>
--   
--   <pre>
--   (asREChar r \/ s) \/ t === r \/ (s \/ t)
--   </pre>
--   
--   <pre>
--   empty \/ asREChar r === r
--   </pre>
--   
--   <pre>
--   asREChar r \/ empty === r
--   </pre>
--   
--   <pre>
--   everything \/ asREChar r === everything
--   </pre>
--   
--   <pre>
--   asREChar r \/ everything === everything
--   </pre>
unions :: (Ord c, Enum c, Bounded c) => [RE c] -> RE c

-- | Kleene star.
--   
--   <pre>
--   star (star r) === star (asREChar r)
--   </pre>
--   
--   <pre>
--   star eps     === asREChar eps
--   </pre>
--   
--   <pre>
--   star empty   === asREChar eps
--   </pre>
--   
--   <pre>
--   star anyChar === asREChar everything
--   </pre>
--   
--   <pre>
--   star (r      \/ eps) === star (asREChar r)
--   </pre>
--   
--   <pre>
--   star (char c \/ eps) === star (asREChar (char c))
--   </pre>
--   
--   <pre>
--   star (empty  \/ eps) === asREChar eps
--   </pre>
star :: Ord c => RE c -> RE c

-- | Literal string.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("foobar" :: RE Char)
--   ^foobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty ("(.)" :: RE Char)
--   ^\(\.\)$
--   </pre>
string :: [c] -> RE c

-- | We say that a regular expression r is nullable if the language it
--   defines contains the empty string.
--   
--   <pre>
--   &gt;&gt;&gt; nullable eps
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable (star "x")
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; nullable "foo"
--   False
--   </pre>
nullable :: RE c -> Bool

-- | Intuitively, the derivative of a language &lt;math&gt; with respect to
--   a symbol &lt;math&gt; is the language that includes only those
--   suffixes of strings with a leading symbol &lt;math&gt; in
--   &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'f' "foobar"
--   ^oobar$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ "xyz" \/ "abc"
--   ^yz$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ derivate 'x' $ star "xyz"
--   ^yz(xyz)*$
--   </pre>
derivate :: (Ord c, Enum c, Bounded c) => c -> RE c -> RE c

-- | Transition map. Used to construct <a>DFA</a>.
--   
--   <pre>
--   &gt;&gt;&gt; void $ Map.traverseWithKey (\k v -&gt; putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: RE Char)
--   ^[]$ : \_ -&gt; "^[]$"
--   ^b$ : \x -&gt; if
--       | x &lt;= 'a'  -&gt; "^[]$"
--       | x &lt;= 'b'  -&gt; "^$"
--       | otherwise -&gt; "^[]$"
--   ^$ : \_ -&gt; "^[]$"
--   ^ab$ : \x -&gt; if
--       | x &lt;= '`'  -&gt; "^[]$"
--       | x &lt;= 'a'  -&gt; "^b$"
--       | otherwise -&gt; "^[]$"
--   </pre>
transitionMap :: (Ord c, Enum c, Bounded c) => RE c -> Map (RE c) (SF c (RE c))

-- | Leading character sets of regular expression.
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars "foo"
--   fromSeparators "ef"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars (star "b" &lt;&gt; star "e")
--   fromSeparators "abde"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; leadingChars (charRange 'b' 'z')
--   fromSeparators "az"
--   </pre>
leadingChars :: (Ord c, Enum c, Bounded c) => RE c -> Partition c

-- | Whether two regexps are equivalent.
--   
--   <pre>
--   <a>equivalent</a> re1 re2 <a>=</a> forall s. <tt>match</tt> re1 s === <tt>match</tt> re1 s
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = star "a" &lt;&gt; "a"
--   
--   &gt;&gt;&gt; let re2 = "a" &lt;&gt; star "a"
--   </pre>
--   
--   These are different regular expressions, even we perform some
--   normalisation-on-construction:
--   
--   <pre>
--   &gt;&gt;&gt; re1 == re2
--   False
--   </pre>
--   
--   They are however equivalent:
--   
--   <pre>
--   &gt;&gt;&gt; equivalent re1 re2
--   True
--   </pre>
--   
--   The algorithm works by executing <tt>states</tt> on "product" regexp,
--   and checking whether all resulting states are both accepting or
--   rejecting.
--   
--   <pre>
--   re1 == re2 ==&gt; <a>equivalent</a> re1 re2
--   </pre>
--   
--   <h3>More examples</h3>
--   
--   <pre>
--   &gt;&gt;&gt; let example re1 re2 = putPretty re1 &gt;&gt; putPretty re2 &gt;&gt; return (equivalent re1 re2)
--   
--   &gt;&gt;&gt; example re1 re2
--   ^a*a$
--   ^aa*$
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star "aa") (star "aaa")
--   ^(aa)*$
--   ^(aaa)*$
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star "aa" &lt;&gt; star "aaa") (star "aaa" &lt;&gt; star "aa")
--   ^(aa)*(aaa)*$
--   ^(aaa)*(aa)*$
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example (star ("a" \/ "b")) (star $ star "a" &lt;&gt; star "b")
--   ^[a-b]*$
--   ^(a*b*)*$
--   True
--   </pre>
equivalent :: (Ord c, Enum c, Bounded c) => RE c -> RE c -> Bool

-- | Generate random strings of the language <tt>RE c</tt> describes.
--   
--   <pre>
--   &gt;&gt;&gt; let example = traverse_ print . take 3 . generate (curry QC.choose) 42
--   
--   &gt;&gt;&gt; example "abc"
--   "abc"
--   "abc"
--   "abc"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example $ star $ "a" \/ "b"
--   ""
--   "bbaabbaaba"
--   "b"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; example empty
--   </pre>
--   
--   <pre>
--   all (match r) $ take 10 $ generate (curry QC.choose) 42 (r :: RE Char)
--   </pre>
generate :: (c -> c -> Gen c) -> Int -> RE c -> [[c]]

-- | Whether <a>RE</a> is (structurally) equal to <a>empty</a>.
--   
--   <pre>
--   isEmpty r === all (not . nullable) (Map.keys $ transitionMap $ asREChar r)
--   </pre>
isEmpty :: RE c -> Bool

-- | Not only we can decide whether <a>RE</a> is nullable, we can also
--   remove the empty string:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof eps
--   ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof $ star "x"
--   ^xx*$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof "foo"
--   Nothing
--   </pre>
--   
--   <a>nullableProof</a> is consistent with <a>nullable</a>:
--   
--   <pre>
--   isJust (nullableProof r) === nullable (asREChar r)
--   </pre>
--   
--   The returned regular expression is not nullable:
--   
--   <pre>
--   maybe True (not . nullable) $ nullableProof $ asREChar r
--   </pre>
--   
--   If we union with empty regex, we get a equivalent regular expression
--   we started with:
--   
--   <pre>
--   maybe r (eps \/) (nullableProof r) `equivalent` (asREChar r)
--   </pre>
nullableProof :: (Ord c, Enum c, Bounded c) => RE c -> Maybe (RE c)

module Kleene.Internal.Functor

-- | <a>Applicative</a> <a>Functor</a> regular expression.
data K c a
[KEmpty] :: forall c a. K c a
[KPure] :: forall a c. a -> K c a
[KChar] :: forall c. (Ord c, Enum c) => RSet c -> K c c
[KAppend] :: forall a1 b a c. (a1 -> b -> a) -> K c a1 -> K c b -> K c a
[KUnion] :: forall c a. K c a -> K c a -> K c a
[KStar] :: forall c a1. Greediness -> K c a1 -> K c [a1]
[KMap] :: forall a1 a c. (a1 -> a) -> K c a1 -> K c a
[KString] :: forall c. Eq c => [c] -> K c [c]

-- | Star behaviour
data Greediness

-- | <a>many</a>
Greedy :: Greediness

-- | <a>few</a>
NonGreedy :: Greediness

-- | <a>few</a>, not <a>many</a>.
--   
--   Let's define two similar regexps
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = liftA2 (,) (few  $ char 'a') (many $ char 'a')
--   
--   &gt;&gt;&gt; let re2 = liftA2 (,) (many $ char 'a') (few  $ char 'a')
--   </pre>
--   
--   Their <tt>RE</tt> behaviour is the same:
--   
--   <pre>
--   &gt;&gt;&gt; C.equivalent (toRE re1) (toRE re2)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (C.match $ toRE re1) ["aaa","bbb"]
--   [True,False]
--   </pre>
--   
--   However, the <tt>RA</tt> behaviour is different!
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA re1) "aaaa"
--   Just ("","aaaa")
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA re2) "aaaa"
--   Just ("aaaa","")
--   </pre>
few :: K c a -> K c [a]

-- | <pre>
--   &gt;&gt;&gt; putPretty anyChar
--   ^[^]$
--   </pre>
anyChar :: (Ord c, Enum c, Bounded c) => K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ oneof ("foobar" :: [Char])
--   ^[a-bfor]$
--   </pre>
oneof :: (Ord c, Enum c, Foldable f) => f c -> K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ char 'x'
--   ^x$
--   </pre>
char :: (Ord c, Enum c) => c -> K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--   </pre>
charRange :: (Enum c, Ord c) => c -> c -> K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty dot
--   ^.$
--   </pre>
dot :: K Char Char

-- | <pre>
--   &gt;&gt;&gt; putPretty everything
--   ^[^]*$
--   </pre>
everything :: (Ord c, Enum c, Bounded c) => K c [c]

-- | <pre>
--   &gt;&gt;&gt; putPretty everything1
--   ^[^][^]*$
--   </pre>
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 <tt>regex-applicative</tt>
match :: K c a -> [c] -> Maybe a

-- | Convert to <tt>RE</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (toRE $ many "foo" :: RE.RE Char)
--   ^(foo)*$
--   </pre>
toRE :: (Ord c, Enum c, Bounded c) => K c a -> RE c

-- | Convert to any <tt>Kleene</tt>
toKleene :: FiniteKleene c k => K c a -> k

-- | Convert from <tt>RE</tt>.
--   
--   <i>Note:</i> all <a>REStar</a>s are converted to <a>Greedy</a> ones,
--   it doesn't matter, as we don't capture anything.
--   
--   <pre>
--   &gt;&gt;&gt; match (fromRE "foobar") "foobar"
--   Just "foobar"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; match (fromRE $ C.star "a" &lt;&gt; C.star "a") "aaaa"
--   Just "aaaa"
--   </pre>
fromRE :: (Ord c, Enum c) => RE c -> K c [c]

-- | Convert <a>K</a> to <a>RE</a> from <tt>regex-applicative</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA ("xx" *&gt; everything &lt;* "zz" :: K Char String)) "xxyyyzz"
--   Just "yyy"
--   </pre>
--   
--   See also <a>match</a>.
toRA :: K c a -> RE c a
instance Data.Functor.Alt.Alt (Kleene.Internal.Functor.K c)
instance GHC.Base.Alternative (Kleene.Internal.Functor.K c)
instance GHC.Base.Applicative (Kleene.Internal.Functor.K c)
instance Data.Functor.Bind.Class.Apply (Kleene.Internal.Functor.K c)
instance GHC.Enum.Bounded Kleene.Internal.Functor.Greediness
instance GHC.Enum.Enum Kleene.Internal.Functor.Greediness
instance GHC.Classes.Eq Kleene.Internal.Functor.Greediness
instance GHC.Base.Functor (Kleene.Internal.Functor.K c)
instance (c GHC.Types.~ GHC.Types.Char, Data.String.IsString a) => Data.String.IsString (Kleene.Internal.Functor.K c a)
instance GHC.Classes.Ord Kleene.Internal.Functor.Greediness
instance (c GHC.Types.~ GHC.Types.Char) => Kleene.Internal.Pretty.Pretty (Kleene.Internal.Functor.K c a)
instance GHC.Show.Show Kleene.Internal.Functor.Greediness

module Kleene.Functor

-- | <a>Applicative</a> <a>Functor</a> regular expression.
data K c a

-- | Star behaviour
data Greediness

-- | <a>many</a>
Greedy :: Greediness

-- | <a>few</a>
NonGreedy :: Greediness

-- | <a>few</a>, not <a>many</a>.
--   
--   Let's define two similar regexps
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = liftA2 (,) (few  $ char 'a') (many $ char 'a')
--   
--   &gt;&gt;&gt; let re2 = liftA2 (,) (many $ char 'a') (few  $ char 'a')
--   </pre>
--   
--   Their <tt>RE</tt> behaviour is the same:
--   
--   <pre>
--   &gt;&gt;&gt; C.equivalent (toRE re1) (toRE re2)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (C.match $ toRE re1) ["aaa","bbb"]
--   [True,False]
--   </pre>
--   
--   However, the <tt>RA</tt> behaviour is different!
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA re1) "aaaa"
--   Just ("","aaaa")
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA re2) "aaaa"
--   Just ("aaaa","")
--   </pre>
few :: K c a -> K c [a]

-- | <pre>
--   &gt;&gt;&gt; putPretty anyChar
--   ^[^]$
--   </pre>
anyChar :: (Ord c, Enum c, Bounded c) => K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ oneof ("foobar" :: [Char])
--   ^[a-bfor]$
--   </pre>
oneof :: (Ord c, Enum c, Foldable f) => f c -> K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ char 'x'
--   ^x$
--   </pre>
char :: (Ord c, Enum c) => c -> K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--   </pre>
charRange :: (Enum c, Ord c) => c -> c -> K c c

-- | <pre>
--   &gt;&gt;&gt; putPretty dot
--   ^.$
--   </pre>
dot :: K Char Char

-- | <pre>
--   &gt;&gt;&gt; putPretty everything
--   ^[^]*$
--   </pre>
everything :: (Ord c, Enum c, Bounded c) => K c [c]

-- | <pre>
--   &gt;&gt;&gt; putPretty everything1
--   ^[^][^]*$
--   </pre>
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 <tt>regex-applicative</tt>
match :: K c a -> [c] -> Maybe a

-- | Convert to <tt>RE</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (toRE $ many "foo" :: RE.RE Char)
--   ^(foo)*$
--   </pre>
toRE :: (Ord c, Enum c, Bounded c) => K c a -> RE c

-- | Convert to any <tt>Kleene</tt>
toKleene :: FiniteKleene c k => K c a -> k

-- | Convert from <tt>RE</tt>.
--   
--   <i>Note:</i> all <a>REStar</a>s are converted to <a>Greedy</a> ones,
--   it doesn't matter, as we don't capture anything.
--   
--   <pre>
--   &gt;&gt;&gt; match (fromRE "foobar") "foobar"
--   Just "foobar"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; match (fromRE $ C.star "a" &lt;&gt; C.star "a") "aaaa"
--   Just "aaaa"
--   </pre>
fromRE :: (Ord c, Enum c) => RE c -> K c [c]

-- | Convert <a>K</a> to <a>RE</a> from <tt>regex-applicative</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA ("xx" *&gt; everything &lt;* "zz" :: K Char String)) "xxyyyzz"
--   Just "yyy"
--   </pre>
--   
--   See also <a>match</a>.
toRA :: K c a -> RE c a

module Kleene.Functor.NonEmpty

-- | <a>Applicative</a> <a>Functor</a> regular expression.
data K1 c a

-- | Star behaviour
data Greediness

-- | <a>many</a>
Greedy :: Greediness

-- | <a>few</a>
NonGreedy :: Greediness
some1 :: K1 c a -> K1 c (NonEmpty a)

-- | <a>few1</a>, not <a>some1</a>.
--   
--   Let's define two similar regexps
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = liftF2 (,) (few1 $ char 'a')  (some1 $ char 'a')
--   
--   &gt;&gt;&gt; let re2 = liftF2 (,) (some1 $ char 'a') (few1  $ char 'a')
--   </pre>
--   
--   Their <tt>RE</tt> behaviour is the same:
--   
--   <pre>
--   &gt;&gt;&gt; C.equivalent (toRE re1) (toRE re2)
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; map (C.match $ toRE re1) ["aaa","bbb"]
--   [True,False]
--   </pre>
--   
--   However, the <tt>RA</tt> behaviour is different!
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA re1) "aaaaa"
--   Just ('a' :| "",'a' :| "aaa")
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA re2) "aaaaa"
--   Just ('a' :| "aaa",'a' :| "")
--   </pre>
few1 :: K1 c a -> K1 c (NonEmpty a)

-- | <pre>
--   &gt;&gt;&gt; putPretty anyChar
--   ^[^]$
--   </pre>
anyChar :: (Ord c, Enum c, Bounded c) => K1 c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ oneof ("foobar" :: [Char])
--   ^[a-bfor]$
--   </pre>
oneof :: (Ord c, Enum c, Foldable f) => f c -> K1 c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ char 'x'
--   ^x$
--   </pre>
char :: (Ord c, Enum c) => c -> K1 c c

-- | <pre>
--   &gt;&gt;&gt; putPretty $ charRange 'a' 'z'
--   ^[a-z]$
--   </pre>
charRange :: (Enum c, Ord c) => c -> c -> K1 c c

-- | <pre>
--   &gt;&gt;&gt; putPretty dot
--   ^.$
--   </pre>
dot :: K1 Char Char

-- | <pre>
--   &gt;&gt;&gt; putPretty everything1
--   ^[^][^]*$
--   </pre>
everything1 :: (Ord c, Enum c, Bounded c) => K1 c (NonEmpty c)
string :: String -> K1 Char (NonEmpty Char)

-- | Matches nothing?
isEmpty :: (Ord c, Enum c, Bounded c) => K1 c a -> Bool

-- | Matches whole input?
isEverything :: (Ord c, Enum c, Bounded c) => K1 c a -> Bool

-- | Match using <tt>regex-applicative</tt>
match :: K1 c a -> [c] -> Maybe a

-- | Convert to <tt>RE</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (toRE $ some1 (string "foo") :: RE.RE Char)
--   ^foo(foo)*$
--   </pre>
toRE :: (Ord c, Enum c, Bounded c) => K1 c a -> RE c

-- | Convert to any <tt>Kleene</tt>
toKleene :: FiniteKleene c k => K1 c a -> k

-- | Convert <a>K</a> to <a>RE</a> from <tt>regex-applicative</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; R.match (toRA (string "xx" .&gt; everything1 &lt;. string "zz" :: K1 Char (NonEmpty Char))) "xxyyzyyzz"
--   Just ('y' :| "yzyy")
--   </pre>
--   
--   See also <a>match</a>.
toRA :: K1 c a -> RE c a

-- | <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof (pure True)
--   Right 1 , ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof (many "xyz" :: K Char [String])
--   Right [] , ^xyz(xyz)*$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ nullableProof (many $ toList &lt;$&gt; optional "x" &lt;|&gt; many "yz" :: K Char [[String]])
--   Right [] , ^(x|yz(yz)*)(x|yz(yz)*)*$
--   </pre>
nullableProof :: K c a -> Either (K1 c a) (a, K1 c a)
instance Data.Functor.Alt.Alt (Kleene.Functor.NonEmpty.K1 c)
instance Data.Functor.Bind.Class.Apply (Kleene.Functor.NonEmpty.K1 c)
instance GHC.Base.Functor (Kleene.Functor.NonEmpty.K1 c)
instance (c GHC.Types.~ GHC.Types.Char) => Kleene.Internal.Pretty.Pretty (Kleene.Functor.NonEmpty.K1 c a)


-- | Kleene algebra.
--   
--   This package provides means to work with kleene algebra, at the moment
--   specifically concentrating on regular expressions over <a>Char</a>.
--   
--   Implements ideas from <i>Regular-expression derivatives
--   re-examined</i> by Scott Owens, John Reppy and Aaron Turon
--   <a>https://doi.org/10.1017/S0956796808007090</a>.
--   
--   <pre>
--   &gt;&gt;&gt; :set -XOverloadedStrings
--   
--   &gt;&gt;&gt; import Algebra.Lattice
--   
--   &gt;&gt;&gt; import Algebra.PartialOrd
--   
--   &gt;&gt;&gt; import Data.Semigroup
--   
--   &gt;&gt;&gt; import Kleene.Internal.Pretty (putPretty)
--   </pre>
--   
--   <a>Kleene.RE</a> module provides <a>RE</a> type. <a>Kleene.Classes</a>
--   module provides various classes to work with the type. All of that is
--   re-exported from <a>Kleene</a> module.
--   
--   First let's construct a regular expression value:
--   
--   <pre>
--   &gt;&gt;&gt; let re = star "abc" &lt;&gt; "def" &lt;&gt; ("x" \/ "yz") :: RE Char
--   
--   &gt;&gt;&gt; putPretty re
--   ^(abc)*def(x|yz)$
--   </pre>
--   
--   We can convert it to <a>DFA</a> (there are 8 states)
--   
--   <pre>
--   &gt;&gt;&gt; let dfa = fromTM re
--   
--   &gt;&gt;&gt; putPretty dfa
--   0 -&gt; \x -&gt; if
--       | x &lt;= '`'  -&gt; 8
--       | x &lt;= 'a'  -&gt; 5
--       | x &lt;= 'c'  -&gt; 8
--       | x &lt;= 'd'  -&gt; 3
--       | otherwise -&gt; 8
--   1 -&gt; \x -&gt; if
--       | x &lt;= 'w'  -&gt; 8
--       | x &lt;= 'x'  -&gt; 6
--       | x &lt;= 'y'  -&gt; 7
--       | otherwise -&gt; 8
--   2 -&gt; ...
--   ...
--   </pre>
--   
--   It's also possible to graphically visualise DFAs
--   
--   <pre>
--   λ&gt; writeFile "example.dot' (<a>toDot</a> dfa)
--   %  dot -Tpng -oexample.png example.dot
--   </pre>
--   
--   
--   And we can convert back from <a>DFA</a> to <a>RE</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let re' = toKleene dfa :: RE Char
--   
--   &gt;&gt;&gt; putPretty re'
--   ^(a(bca)*bcdefx|defx|(a(bca)*bcdefy|defy)z)$
--   </pre>
--   
--   As you see, we don't get what we started with. Yet, these regular
--   expressions are <a>equivalent</a>;
--   
--   <pre>
--   &gt;&gt;&gt; equivalent re re'
--   True
--   </pre>
--   
--   or using <a>Equiv</a> wrapper
--   
--   <pre>
--   &gt;&gt;&gt; Equiv re == Equiv re'
--   True
--   </pre>
--   
--   (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:
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Foldable
--   
--   &gt;&gt;&gt; import qualified Test.QuickCheck as QC
--   
--   &gt;&gt;&gt; import Kleene.RE (generate)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; traverse_ print $ take 5 $ generate (curry QC.choose) 42 re
--   "abcdefx"
--   "abcabcdefx"
--   "abcdefyz"
--   "abcabcabcabcabcabcabcdefyz"
--   "abcabcabcabcabcabcabcdefyz"
--   </pre>
--   
--   In addition to the "normal" regular expressions, there are <i>extended
--   regular expressions</i>. Regular expressions which we can
--   <a>complement</a>, and therefore intersect:
--   
--   <pre>
--   &gt;&gt;&gt; let ere = star "aa" /\ star "aaa" :: ERE Char
--   
--   &gt;&gt;&gt; putPretty ere
--   ^~(~((aa)*)|~((aaa)*))$
--   </pre>
--   
--   We can convert <a>ERE</a> to <a>RE</a> via <a>DFA</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let re'' = toKleene (fromTM ere) :: RE Char
--   
--   &gt;&gt;&gt; putPretty re''
--   ^(a(aaaaaa)*aaaaa)?$
--   </pre>
--   
--   Machine works own ways, we don't (always) get as pretty results as
--   we'd like:
--   
--   <pre>
--   &gt;&gt;&gt; equivalent re'' (star "aaaaaa")
--   True
--   </pre>
--   
--   Another feature of the library is an <tt>Applciative</tt>
--   <a>Functor</a>,
--   
--   <pre>
--   &gt;&gt;&gt; import Control.Applicative
--   
--   &gt;&gt;&gt; import qualified Kleene.Functor as F
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f = (,) &lt;$&gt; many (F.char 'x') &lt;* F.few F.anyChar &lt;*&gt; many (F.char 'z')
--   
--   &gt;&gt;&gt; putPretty f
--   ^x*[^]*z*$
--   </pre>
--   
--   By relying on
--   <a>http://hackage.haskell.org/package/regex-applicative</a> library,
--   we can match and <i>capture</i> with regular expression.
--   
--   <pre>
--   &gt;&gt;&gt; F.match f "xyyzzz"
--   Just ("x","zzz")
--   </pre>
--   
--   Where with <a>RE</a> we can only get <a>True</a> or <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; match (F.toRE f) "xyyzzz"
--   True
--   </pre>
--   
--   Which in this case is not even interesting because:
--   
--   <pre>
--   &gt;&gt;&gt; equivalent (F.toRE f) everything
--   True
--   </pre>
--   
--   Converting from <a>RE</a> to <a>K</a> is also possible, which may be
--   handy:
--   
--   <pre>
--   &gt;&gt;&gt; let g = (,) &lt;$&gt; F.few F.anyChar &lt;*&gt; F.fromRE re''
--   
--   &gt;&gt;&gt; putPretty g
--   ^[^]*(a(aaaaaa)*aaaaa)?$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; F.match g (replicate 20 'a')
--   Just ("aa","aaaaaaaaaaaaaaaaaa")
--   </pre>
--   
--   We got longest divisible by 6 prefix of as. That's because
--   <a>fromRE</a> uses <tt>many</tt> for <a>star</a>.
module Kleene

-- | Regular expression
--   
--   Constructors are exposed, but you should use smart constructors in
--   this module to construct <a>RE</a>.
--   
--   The <a>Eq</a> and <a>Ord</a> instances are structural. The
--   <tt>Kleene</tt> etc constructors do "weak normalisation", so for
--   values constructed using those operations <a>Eq</a> witnesses "weak
--   equivalence". See <a>equivalent</a> for regular-expression
--   equivalence.
--   
--   Structure is exposed in <a>Kleene.RE</a> module but consider
--   constructors as half-internal. There are soft-invariants, but
--   violating them shouldn't break anything in the package. (e.g.
--   <a>transitionMap</a> 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, <i>Kleene</i> and <i>Boolean</i> algebra. (If we add only
--   intersections, it wouldn't be <i>Boolean</i>).
--   
--   <i>Note:</i> we don't have special constructor for intersections. We
--   use de Morgan formula &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ asEREChar $ "a" /\ "b"
--   ^~(~a|~b)$
--   </pre>
--   
--   There is no generator, as <a>intersections</a> makes it hard.
data ERE c

-- | Regular-expressions for which <a>==</a> is <a>equivalent</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let re1 = star "a" &lt;&gt; "a" :: RE Char
--   
--   &gt;&gt;&gt; let re2 = "a" &lt;&gt; star "a" :: RE Char
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; re1 == re2
--   False
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Equiv re1 == Equiv re2
--   True
--   </pre>
--   
--   <a>Equiv</a> is also a <a>PartialOrd</a> (but not <a>Ord</a>!)
--   
--   <pre>
--   &gt;&gt;&gt; Equiv "a" `leq` Equiv (star "a" :: RE Char)
--   True
--   </pre>
--   
--   Not all regular expessions are <a>comparable</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let reA = Equiv "a" :: Equiv RE Char
--   
--   &gt;&gt;&gt; let reB = Equiv "b" :: Equiv RE Char
--   
--   &gt;&gt;&gt; (leq reA reB, leq reB reA)
--   (False,False)
--   </pre>
newtype Equiv (r :: Type -> Type) c
Equiv :: r c -> Equiv (r :: Type -> Type) c

-- | Deterministic finite automaton.
--   
--   A deterministic finite automaton (DFA) over an alphabet &lt;math&gt;
--   (type variable <tt>c</tt>) is 4-tuple &lt;math&gt;, &lt;math&gt; ,
--   &lt;math&gt;, &lt;math&gt;, where
--   
--   <ul>
--   <li>&lt;math&gt; is a finite set of states (subset of
--   <tt>s</tt>),</li>
--   <li>&lt;math&gt; is the distinguised start state
--   (<a>dfaInitial</a>),</li>
--   <li>&lt;math&gt; is a set of final (or accepting) states
--   (<a>dfaAcceptable</a>), and</li>
--   <li>&lt;math&gt; is a function called the state transition function
--   (<a>dfaTransition</a>).</li>
--   </ul>
data DFA c
DFA :: !IntMap (SF c Int) -> !Int -> !IntSet -> !IntSet -> DFA c

-- | transition function
[dfaTransition] :: DFA c -> !IntMap (SF c Int)

-- | initial state
[dfaInitial] :: DFA c -> !Int

-- | accept states
[dfaAcceptable] :: DFA c -> !IntSet

-- | states we cannot escape
[dfaBlackholes] :: DFA c -> !IntSet

-- | Create from <a>TransitionMap</a>.
--   
--   See <a>fromRE</a> for a specific example.
fromTM :: (Ord k, Ord c, TransitionMap c k) => k -> DFA c

-- | Create from <tt>TransitonMap</tt> minimising states with
--   <a>Equivalent</a>.
--   
--   See <a>fromERE</a> for an example.
fromTMEquiv :: (Ord k, Ord c, TransitionMap c k, Equivalent c k) => k -> DFA c

-- | Convert to any <a>Kleene</a>.
--   
--   See <a>toRE</a> for a specific example.
toKleene :: forall k c. (Ord c, Enum c, Bounded c, FiniteKleene c k) => DFA c -> k

-- | Get Graphviz dot-code of DFA.
--   
--   <pre>
--   &gt;&gt;&gt; let dfa = fromRE $ RE.star "abc"
--   
--   &gt;&gt;&gt; putStr $ toDot dfa
--   digraph dfa {
--   rankdir=LR;
--   // states
--   "0" [shape=doublecircle];
--   "1" [shape=circle];
--   "2" [shape=circle];
--   // initial state
--   "" [shape=none];
--   "" -&gt; "0";
--   // transitions
--   "0" -&gt; "2"[label="a"]
--   "1" -&gt; "0"[label="c"]
--   "2" -&gt; "1"[label="b"]
--   }
--   </pre>
toDot :: DFA Char -> String

-- | Kleene algebra.
--   
--   If <tt>k</tt> is <a>Monoid</a> it's expected that <tt><a>appends</a> =
--   <a>mappend</a></tt>; if <tt>k</tt> is <a>Lattice</a> it's expected
--   that <tt><a>unions</a> = <a>joins</a></tt>.
--   
--   <a>Wikipedia: Kleene Algebra</a>.
class Kleene k

-- | Empty regex. Doesn't accept anything.
empty :: Kleene k => k

-- | Empty string. <i>Note:</i> different than <a>empty</a>.
eps :: Kleene k => k

-- | Concatenation.
appends :: Kleene k => [k] -> k

-- | Union.
unions :: Kleene k => [k] -> k

-- | Kleene star.
star :: Kleene k => k -> k
class Kleene k => CharKleene c k | k -> c

-- | Single character
char :: CharKleene c k => c -> k
string :: CharKleene c k => [c] -> k
class CharKleene c k => FiniteKleene c k | k -> c

-- | Everything. &lt;math&gt;.
everything :: FiniteKleene c k => k

-- | <tt><a>charRange</a> <tt>a</tt> <tt>z</tt> = ^[a-z]$</tt>.
charRange :: FiniteKleene c k => c -> c -> k

-- | Generalisation of <a>charRange</a>.
fromRSet :: FiniteKleene c k => RSet c -> k

-- | <tt>.</tt> Every character except new line <tt>\n</tt>.
dot :: FiniteKleene c k => k

-- | Any character. <i>Note:</i> different than <a>dot</a>!
anyChar :: FiniteKleene c k => k
notChar :: FiniteKleene c k => c -> k
($dmnotChar) :: (FiniteKleene c k, Ord c, Enum c, Bounded c) => c -> 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 <tt>f</tt> can be used to match on the input.
class Match c k | k -> c
match :: Match c k => k -> [c] -> Bool
match8 :: Match c k => k -> ByteString -> Bool

-- | Equivalence induced by <a>Match</a>.
--   
--   <i>Law:</i>
--   
--   <pre>
--   <a>equivalent</a> re1 re2 <a>=</a> forall s. <a>match</a> re1 s == <a>match</a> re1 s
--   </pre>
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.
--   
--   <i>Law:</i>
--   
--   <pre>
--   <a>match</a> (<a>complement</a> f) xs = <a>not</a> (<a>match</a> f) xs
--   </pre>
class Complement c k | k -> c
complement :: Complement c k => k -> k
class ToLatin1 (k :: Type -> Type)
toLatin1 :: ToLatin1 k => k Char -> k Word8

-- | <a>Applicative</a> <a>Functor</a> regular expression.
data K c a
