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

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 (curry (&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.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) => GHC.Base.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 <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 (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. <i>Note:</i> different than <a>empty</a>
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. &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>.$. Every character except new line </tt>\n@.
dot :: (FiniteKleene c k, c ~ Char) => k

-- | Any character. <i>Note:</i> 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 <tt>f</tt> can be used to match on the input.
class Match c k | k -> c
match :: Match c k => k -> [c] -> Bool

-- | Equivalence induced by <tt>Matches</tt>.
--   
--   <i>Law:</i>
--   
--   <pre>
--   <a>equivalent</a> re1 re2 <a>=</a> forall s. <tt>matches</tt> re1 s == <tt>matches</tt> 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>
--   <tt>matches</tt> (<a>complement</a> f) xs = <a>not</a> (<tt>matches</tt> f) xs
--   </pre>
class Complement c k | k -> c
complement :: Complement c k => k -> k

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 c
Equiv :: (r c) -> Equiv r c
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 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)
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, <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

-- | <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 \/ asREChar r === everything
--   </pre>
--   
--   <pre>
--   asREChar 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 /\ asREChar r === r
--   </pre>
--   
--   <pre>
--   asREChar 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 (asREChar 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

-- | 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 :: forall c. (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 :: forall c. (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.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 => GHC.Base.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 <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

-- | 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.
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (empty :: M Bool)
--   ^[]$
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; putPretty (bottom :: M Bool)
--   ^[]$
--   </pre>
--   
--   <pre>
--   match (empty :: M Bool) (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 Bool) 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' $ "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 $ "a" \/ "b"
--   "ababbb"
--   "baab"
--   "abbababaa"
--   </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 :: Kleene 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 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 GHC.Base.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 <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

-- | <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 :: forall c. (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 :: forall c. (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"
--   "aaaaba"
--   "bbba"
--   "abbbbaaaa"
--   </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
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 => GHC.Base.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

-- | <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
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 &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
--   <a>Int</a>),</li>
--   <li>&lt;math&gt; is the distinguised start state (<tt>0</tt>),</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)) -> !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 <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 :: forall c. (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 :: forall c. (Ord c, Enum c, Bounded c) => DFA c -> RE c

-- | Convert <a>ERE</a> to <a>DFA</a>.
--   
--   We don't always generate minimal automata:
--   
--   <pre>
--   &gt;&gt;&gt; putPretty $ fromERE $ "a" /\ "b"
--   0 -&gt; \_ -&gt; 1
--   1 -&gt; \_ -&gt; 1 -- black hole
--   </pre>
--   
--   Compare this to an <tt>complement</tt> example
--   
--   Using <a>fromTMEquiv</a>, we can get 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 :: forall c. (Ord c, Enum c, Bounded c) => ERE c -> DFA c

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

-- | Create from <a>TransitionMap</a>.
--   
--   See <a>fromRE</a> for a specific example.
fromTM :: forall k c. (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 :: forall k c. (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
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 <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; putPretty $ fromTM re
--   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>
--   
--   And we can convert back from <a>DFA</a> to <a>RE</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let re' = toKleene (fromTM re) :: 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
--   "abcabcabcabcabcabcdefyz"
--   "abcabcabcabcdefyz"
--   "abcabcabcabcabcabcabcabcabcdefx"
--   "abcabcdefx"
--   "abcabcabcabcabcabcdefyz"
--   </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 c
Equiv :: (r c) -> Equiv r 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
--   <a>Int</a>),</li>
--   <li>&lt;math&gt; is the distinguised start state (<tt>0</tt>),</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)) -> !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 <a>TransitionMap</a>.
--   
--   See <a>fromRE</a> for a specific example.
fromTM :: forall k c. (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 :: forall k c. (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
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. <i>Note:</i> different than <a>empty</a>
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 <tt>f</tt> 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.
--   
--   <i>Law:</i>
--   
--   <pre>
--   <tt>matches</tt> (<a>complement</a> f) xs = <a>not</a> (<tt>matches</tt> f) xs
--   </pre>
class Complement c k | k -> c
complement :: Complement c k => k -> k

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