ZLS      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Safe# 1 devides type into disjoint connected partitions.Note: we could have non-connecter partitions too, but that would be more complicated. This variant is correct by construction, but less precise.1It's enought to store last element of each piece. (fromList [x1, x2, x3]) ::  s describes a partition of Set s, as{ \{ x \mid x \le x_1 \} \cup \{ x \mid x_1 < x \le x_2 \} \cup \{ x \mid x_2 < x \le x_3 \} \cup \{ x \mid x_3 < x \} Note:S it's enough to check upper bound conditions only if checks are performed in order. Invariant:  is not in the set.Check invariant. Construct  from list of s.(RSet intervals are closed on both sides.Count of sets in a . size whole1size $ split (10 :: Word8)2size (asPartitionChar p) >= 1 'Extract examples from each subset in a .examples $ split (10 :: Word8)fromList [10,255]*examples $ split (10 :: Word8) <> split 20fromList [10,20,255]@invariant p ==> size (asPartitionChar p) === length (examples p) 0all (curry (<=)) $ intervals $ asPartitionChar p Wedge partitions.split (10 :: Word8) <> split 20fromSeparators [10,20])whole `wedge` (p :: Partition Char) === p$(p :: Partition Char) <> whole === p!asPartitionChar p <> q === q <> pasPartitionChar p <> p === p"invariant $ asPartitionChar p <> q Simplest partition: given x partition space into [min..x) and [x .. max]split (128 :: Word8)fromSeparators [128] Make a step function.See  .invariant (asPartitionChar p)  Safe$;All but the newline.Safe&'& Pretty class.For  ::   -> 8 gives a representation accepted by many regex engines.  . !Escapes special regexp charactersSafe&'>?A1Complement of the language.Law: matches ( f) xs =  (matches f) xs Transition map.!Equivalence induced by Matches.Law: " re1 re2  = forall s. matches re1 s == matches re1 s #An f# can be used to match on the input.&&Does language contain an empty string?'Derivative of a language.) Everything.  \Sigma^\star.** a z = ^[a-z]$.+Generalisation of *.,$.$. Every character except new line \n@.-Any character. Note: different than dot!/%Empty regex. Doesn't accept anything.0Empty string. Note: different than /1Single character2Concatenation.3Union.4 Kleene star5One of the characters. !"#$%'&(+),-*.42031/5./012345()*+,-%&'#$!"  !"#$%&'()*+,-./01234 Trustworthy &'0;=>?AK9]6Regular-expressions for which  is ".$let re1 = star "a" <> "a" :: RE Char$let re2 = "a" <> star "a" :: RE Char re1 == re2FalseEquiv re1 == Equiv re2True6 is also a  (but not !)+Equiv "a" `leq` Equiv (star "a" :: RE Char)TrueNot all regular expessions are :$let reA = Equiv "a" :: Equiv RE Char$let reB = Equiv "b" :: Equiv RE Char(leq reA reB, leq reB reA) (False,False)8a \preceq b := a \lor b = b 67679867Safe &';=>?AVzEExtended regular expression It's both, Kleene and Boolean9 algebra. (If we add only intersections, it wouldn't be Boolean).Note:P we don't have special constructor for intersections. We use de Morgan formula %a \land b = \neg (\neg a \lor \neg b)."putPretty $ asEREChar $ "a" /\ "b" ^~(~a|~b)$There is no generator, as R makes it hard.FSingle characterG ConcatenationHUnionI Kleene starJ ComplementK%Empty regex. Doesn't accept anything.putPretty (empty :: ERE Char)^[]$putPretty (bottom :: ERE Char)^[]$1match (empty :: ERE Char) (s :: String) === False Everything."putPretty (everything :: ERE Char)^~[]$putPretty (top :: ERE Char)^~[]$5match (everything :: ERE Char) (s :: String) === TrueLEmpty string. Note: different than K. putPretty eps^$putPretty (mempty :: ERE Char)^$0match (eps :: ERE Char) s === null (s :: String)MputPretty (char 'x')^x$NputPretty $ charRange 'a' 'z'^[a-z]$OAny character. Note: different than dot!putPretty anyChar^[^]$P Concatenate regular expressions.asEREChar r <> empty === emptyempty <> asEREChar r === empty)(asEREChar r <> s) <> t === r <> (s <> t)asEREChar r <> eps === reps <> asEREChar r === rQUnion of regular expressions.asEREChar r \/ r === rasEREChar r \/ s === s \/ r)(asEREChar r \/ s) \/ t === r \/ (s \/ t)empty \/ asEREChar r === rasEREChar r \/ empty === r'everything \/ asREChar r === everything'asREChar r \/ everything === everythingR$Intersection of regular expressions.asEREChar r /\ r === rasEREChar r /\ s === s /\ r)(asEREChar r /\ s) /\ t === r /\ (s /\ t)empty /\ asEREChar r === emptyasEREChar r /\ empty === emptyeverything /\ asREChar r === rasREChar r /\ everything === rS Complement.)complement (complement r) === asEREChar rT Kleene star.$star (star r) === star (asEREChar r)star eps === asEREChar epsstar empty === asEREChar eps%star anyChar === asEREChar everything#star (asREChar r \/ eps) === star r0star (char c \/ eps) === star (char (c :: Char))star (empty \/ eps) === epsULiteral string. putPretty ("foobar" :: ERE Char)^foobar$putPretty ("(.)" :: ERE Char)^\(\.\)$VeWe say that a regular expression r is nullable if the language it defines contains the empty string. nullable epsTruenullable (star "x")Truenullable "foo"Falsenullable (complement eps)FalseW*Intuitively, the derivative of a language  \mathcal{L} \subset \Sigma^\star with respect to a symbol  a \in \SigmaU is the language that includes only those suffixes of strings with a leading symbol a in  \mathcal{L}.!putPretty $ derivate 'f' "foobar"^oobar$)putPretty $ derivate 'x' $ "xyz" \/ "abc"^yz$%putPretty $ derivate 'x' $ star "xyz" ^yz(xyz)*$XWhether E is (structurally) equal to K.YWhether E is (structurally) equal to .Z"Transition map. Used to construct   .void $ Map.traverseWithKey (\k v -> putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: ERE Char) ^[]$ : \_ -> "^[]$"^b$ : \x -> if | x <= 'a' -> "^[]$" | x <= 'b' -> "^$" | otherwise -> "^[]$"^$ : \_ -> "^[]$"^ab$ : \x -> if | x <= '`' -> "^[]$" | x <= 'a' -> "^b$" | otherwise -> "^[]$"[-Leading character sets of regular expression.leadingChars "foo"fromSeparators "ef"#leadingChars (star "b" <> star "e")fromSeparators "abde" leadingChars (charRange 'b' 'z')fromSeparators "az"\#Whether two regexps are equivalent. \ re1 re2  = forall s. match re1 s == match re1 s let re1 = star "a" <> "a"let re2 = "a" <> star "a"]These are different regular expressions, even we perform some normalisation-on-construction: re1 == re2FalseThey are however equivalent:equivalent re1 re2True!The algorithm works by executing statesa on "product" regexp, and checking whether all resulting states are both accepting or rejecting. re1 == re2 ==> \ re1 re2  More examplesSlet example re1 re2 = putPretty re1 >> putPretty re2 >> return (equivalent re1 re2)example re1 re2^a*a$^aa*$True example (star "aa") (star "aaa")^(aa)*$^(aaa)*$False;example (star "aa" <> star "aaa") (star "aaa" <> star "aa") ^(aa)*(aaa)*$ ^(aaa)*(aa)*$True9example (star ("a" \/ "b")) (star $ star "a" <> star "b")^[a-b]*$ ^(a*b*)*$TrueEFGHIJKLMNOPQRSTUVWXYZ[\EFGHIJKLMNOPQRTUSVWZ[\XYEFGHIJSafe &'345;=>?AV:sURegular expression which has no restrictions on the elements. Therefore we can have H instance, i.e. have a regexp where characters are regexps themselves.Because there are no optimisations, it's better to work over small alphabets. On the other hand, we can work over infinite alphabets, if we only use small amount of symbols! putPretty $ string [True, False]^10$$let re = string [True, False, True]<let re' = re >>= \b -> if b then char () else star (char ()) putPretty re'^..*.$tOne of the charactersu ConcatenationvUnionw Kleene starx%Empty regex. Doesn't accept anything.putPretty (empty :: M Bool)^[]$putPretty (bottom :: M Bool)^[]$/match (empty :: M Bool) (s :: String) === FalseyEmpty string. Note: different than x.putPretty (eps :: M Bool)^$putPretty (mempty :: M Bool)^$.match (eps :: M Bool) s === null (s :: String)zputPretty (char 'x')^x${Note: we know little about c.putPretty $ charRange 'a' 'z'^[abcdefghijklmnopqrstuvwxyz]$|Any character. Note: different than dot!putPretty (anyChar :: M Bool)^[01]$} Concatenate regular expressions.~Union of regular expressions.%Lattice laws don't hold structurally: Kleene star.Literal string.putPretty ("foobar" :: M Char)^foobar$putPretty ("(.)" :: M Char)^\(\.\)$ putPretty $ string [False, True]^01$eWe say that a regular expression r is nullable if the language it defines contains the empty string. nullable epsTruenullable (star "x")Truenullable "foo"False*Intuitively, the derivative of a language  \mathcal{L} \subset \Sigma^\star with respect to a symbol  a \in \SigmaU is the language that includes only those suffixes of strings with a leading symbol a in  \mathcal{L}.!putPretty $ derivate 'f' "foobar"^oobar$)putPretty $ derivate 'x' $ "xyz" \/ "abc"^yz$%putPretty $ derivate 'x' $ star "xyz" ^yz(xyz)*$Whether s is (structurally) equal to x.Whether s is (structurally) equal to y.(Generate random strings of the language M c describes.4let example = traverse_ print . take 3 . generate 42 example "abc""abc""abc""abc"example $ star $ "a" \/ "b""ababbb""baab" "abbababaa"xx >>> example emptyCexpensive-prop> all (match r) $ take 10 $ generate 42 (r :: M Bool) Convert to Kleenelet re = charRange 'a' 'z' putPretty re^[abcdefghijklmnopqrstuvwxyz]$"putPretty (toKleene re :: RE Char)^[a-z]$seedinfinite list of resultsstuvwxyz{|}~stuvwxyz{|}~stuvwSafe &';=>?AVRegular expression]Constructors are exposed, but you should use smart constructors in this module to construct .The  and  instances are structural. The Kleene] etc constructors do "weak normalisation", so for values constructed using those operations $ witnesses "weak equivalence". See $ for regular-expression equivalence.Structure is exposed in  Kleene.RE module but consider constructors as half-internal. There are soft-invariants, but violating them shouldn't break anything in the package. (e.g. r will eventually terminate, but may create more redundant states if starting regexp is not "weakly normalised").Single character ConcatenationUnion Kleene star%Empty regex. Doesn't accept anything.putPretty (empty :: RE Char)^[]$putPretty (bottom :: RE Char)^[]$0match (empty :: RE Char) (s :: String) === False Everything.putPretty everything^[^]*$4match (everything :: RE Char) (s :: String) === TrueEmpty string. Note: different than . putPretty eps^$putPretty (mempty :: RE Char)^$/match (eps :: RE Char) s === null (s :: String)putPretty (char 'x')^x$putPretty $ charRange 'a' 'z'^[a-z]$Any character. Note: different than dot!putPretty anyChar^[^]$ Concatenate regular expressions.((asREChar r <> s) <> t === r <> (s <> t)asREChar r <> empty === emptyempty <> asREChar r === emptyasREChar r <> eps === reps <> asREChar r === rUnion of regular expressions.asREChar r \/ r === rasREChar r \/ s === s \/ r((asREChar r \/ s) \/ t === r \/ (s \/ t)empty \/ asREChar r === rasREChar r \/ empty === r'everything \/ asREChar r === everything'asREChar r \/ everything === everything Kleene star.#star (star r) === star (asREChar r)star eps === asREChar epsstar empty === asREChar eps$star anyChar === asREChar everything*star (r \/ eps) === star (asREChar r)1star (char c \/ eps) === star (asREChar (char c))%star (empty \/ eps) === asREChar epsLiteral string.putPretty ("foobar" :: RE Char)^foobar$putPretty ("(.)" :: RE Char)^\(\.\)$eWe say that a regular expression r is nullable if the language it defines contains the empty string. nullable epsTruenullable (star "x")Truenullable "foo"False*Intuitively, the derivative of a language  \mathcal{L} \subset \Sigma^\star with respect to a symbol  a \in \SigmaU is the language that includes only those suffixes of strings with a leading symbol a in  \mathcal{L}.!putPretty $ derivate 'f' "foobar"^oobar$)putPretty $ derivate 'x' $ "xyz" \/ "abc"^yz$%putPretty $ derivate 'x' $ star "xyz" ^yz(xyz)*$Whether  is (structurally) equal to .JisEmpty r === all (not . nullable) (Map.keys $ transitionMap $ asREChar r)"Transition map. Used to construct   .void $ Map.traverseWithKey (\k v -> putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: RE Char) ^[]$ : \_ -> "^[]$"^b$ : \x -> if | x <= 'a' -> "^[]$" | x <= 'b' -> "^$" | otherwise -> "^[]$"^$ : \_ -> "^[]$"^ab$ : \x -> if | x <= '`' -> "^[]$" | x <= 'a' -> "^b$" | otherwise -> "^[]$"-Leading character sets of regular expression.leadingChars "foo"fromSeparators "ef"#leadingChars (star "b" <> star "e")fromSeparators "abde" leadingChars (charRange 'b' 'z')fromSeparators "az"#Whether two regexps are equivalent.  re1 re2  = forall s. match re1 s === match re1 s let re1 = star "a" <> "a"let re2 = "a" <> star "a"]These are different regular expressions, even we perform some normalisation-on-construction: re1 == re2FalseThey are however equivalent:equivalent re1 re2True!The algorithm works by executing statesa on "product" regexp, and checking whether all resulting states are both accepting or rejecting. re1 == re2 ==>  re1 re2  More examplesSlet example re1 re2 = putPretty re1 >> putPretty re2 >> return (equivalent re1 re2)example re1 re2^a*a$^aa*$True example (star "aa") (star "aaa")^(aa)*$^(aaa)*$False;example (star "aa" <> star "aaa") (star "aaa" <> star "aa") ^(aa)*(aaa)*$ ^(aaa)*(aa)*$True9example (star ("a" \/ "b")) (star $ star "a" <> star "b")^[a-b]*$ ^(a*b*)*$True(Generate random strings of the language RE c describes.Flet example = traverse_ print . take 3 . generate (curry QC.choose) 42 example "abc""abc""abc""abc"example $ star $ "a" \/ "b""aaaaba""bbba" "abbbbaaaa" example emptyFall (match r) $ take 10 $ generate (curry QC.choose) 42 (r :: RE Char)character range generatorseedinfinite list of results Safe&'  regular expression.Star behaviour, not . Let's define two similar regexps8let re1 = liftA2 (,) (few $ char 'a') (many $ char 'a')8let re2 = liftA2 (,) (many $ char 'a') (few $ char 'a')Their RE behaviour is the same:"C.equivalent (toRE re1) (toRE re2)True&map (C.match $ toRE re1) ["aaa","bbb"] [True,False] However, the RA behaviour is different!R.match (toRA re1) "aaaa"Just ("","aaaa")R.match (toRA re2) "aaaa"Just ("aaaa","")putPretty anyChar^[^]$&putPretty $ oneof ("foobar" :: [Char]) ^[a-bfor]$putPretty $ char 'x'^x$putPretty $ charRange 'a' 'z'^[a-z]$ putPretty dot^.$putPretty everything^[^]*$putPretty everything1 ^[^][^]*$Matches nothing?Matches whole input? Match using regex-applicative Convert to RE.+putPretty (toRE $ many "foo" :: RE.RE Char)^(foo)*$Convert to any Kleene Convert from RE.Note: all s are converted to 8 ones, it doesn't matter, as we don't capture anything. match (fromRE "foobar") "foobar" Just "foobar"0match (fromRE $ C.star "a" <> C.star "a") "aaaa" Just "aaaa"Convert  to  from regex-applicative.FR.match (toRA ("xx" *> everything <* "zz" :: K Char String)) "xxyyyzz" Just "yyy" See also .OConvert to non-matching JavaScript string which can be used as an argument to  new RegExp%putPretty ("foobar" :: K Char String)^foobar$,putPretty $ many ("foobar" :: K Char String) ^(foobar)*$ Safe &';=>?AVJ Deterministic finite automaton.8A deterministic finite automaton (DFA) over an alphabet \Sigma (type variable c ) is 4-tuple Q, q_0 , F, \delta, whereQ& is a finite set of states (subset of ), q_0 \in Q" is the distinguised start state (0), F \subset Q+ is a set of final (or accepting) states (), and\delta : Q \times \Sigma \to Q6 is a function called the state transition function ().transition function accept statesstates we cannot escapeConvert  to ."putPretty $ fromRE $ RE.star "abc" 0+ -> \x -> if | x <= '`' -> 3 | x <= 'a' -> 2 | otherwise -> 3 1 -> \x -> if | x <= 'b' -> 3 | x <= 'c' -> 0 | otherwise -> 3 2 -> \x -> if | x <= 'a' -> 3 | x <= 'b' -> 1 | otherwise -> 33 -> \_ -> 3 -- black hole,Everything and nothing result in blackholes:=traverse_ (putPretty . fromRE) [RE.empty, RE.star RE.anyChar]0 -> \_ -> 0 -- black hole0+ -> \_ -> 0 -- black holeCharacter ranges are effecient:)putPretty $ fromRE $ RE.charRange 'a' 'z' 0 -> \x -> if | x <= '`' -> 2 | x <= 'z' -> 1 | otherwise -> 2 1+ -> \_ -> 22 -> \_ -> 2 -- black holeAn example with two blackholes:.putPretty $ fromRE $ "c" <> RE.star RE.anyChar 0 -> \x -> if | x <= 'b' -> 2 | x <= 'c' -> 1 | otherwise -> 21+ -> \_ -> 1 -- black hole2 -> \_ -> 2 -- black holeConvert E to .*We don't always generate minimal automata: putPretty $ fromERE $ "a" /\ "b" 0 -> \_ -> 11 -> \_ -> 1 -- black holeCompare this to an  complement exampleUsing K, we can get minimal automaton, for the cost of higher complexity (slow!).6putPretty $ fromTMEquiv $ ("a" /\ "b" :: ERE.ERE Char)0 -> \_ -> 0 -- black hole-putPretty $ fromERE $ complement $ star "abc" 0 -> \x -> if | x <= '`' -> 3 | x <= 'a' -> 2 | otherwise -> 31+ -> \x -> if | x <= 'b' -> 3 | x <= 'c' -> 0 | otherwise -> 32+ -> \x -> if | x <= 'a' -> 3 | x <= 'b' -> 1 | otherwise -> 33+ -> \_ -> 3 -- black hole Create from .See  for a specific example. Create from  TransitonMap minimising states with !.See  for an example.Convert  to ."putPretty $ toRE $ fromRE "foobar"^foobar$For  regular expressions,  .  = :Llet s = take 5 s' in RE.string (s :: String) === toRE (fromRE (RE.string s))But in general it isn't:)let aToZ = RE.star $ RE.charRange 'a' 'z'.traverse_ putPretty [aToZ, toRE $ fromRE aToZ]^[a-z]*$^([a-z]|[a-z]?[a-z]*[a-z]?)?$ 2not-prop> (re :: RE.RE Char) === toRE (fromRE re) However, they are :'RE.equivalent aToZ (toRE (fromRE aToZ))TrueAnd so are othersLall (\re -> RE.equivalent re (toRE (fromRE re))) [RE.star "a", RE.star "ab"]True Dexpensive-prop> RE.equivalent re (toRE (fromRE (re :: RE.RE Char)))  Note, that  . . can, and usually makes regexp unrecognisable:(putPretty $ toRE $ fromRE $ RE.star "ab" ^(a(ba)*b)?$We can " DFA, therefore we can complement A. For example. regular expression matching string containing an a:;let withA = RE.star RE.anyChar <> "a" <> RE.star RE.anyChar/let withoutA = toRE $ complement $ fromRE withAputPretty withoutA^([^a]|[^a]?[^a]*[^a]?)?$Klet withoutA' = RE.star $ RE.REChars $ RSet.complement $ RSet.singleton 'a'putPretty withoutA'^[^a]*$ RE.equivalent withoutA withoutA'TrueLQuite small, for example 2 state DFAs can result in big regular expressions:2putPretty $ toRE $ complement $ fromRE $ star "ab"H^([^]|a(ba)*(ba)?|a(ba)*([^b]|b[^a])|([^a]|a(ba)*([^b]|b[^a]))[^]*[^]?)$ We can use  .  to convert E to :3putPretty $ toRE $ fromERE $ complement $ star "ab"H^([^]|a(ba)*(ba)?|a(ba)*([^b]|b[^a])|([^a]|a(ba)*([^b]|b[^a]))[^]*[^]?)$'putPretty $ toRE $ fromERE $ "a" /\ "b"^[]$See  Thttps://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous, for the description of the algorithm used.Convert  to E.Convert to any ..See  for a specific example.Complement DFA.Complement of  is way easier than of : complement accept states.-let dfa = complement $ fromRE $ RE.star "abc" putPretty dfa 0 -> \x -> if | x <= '`' -> 3 | x <= 'a' -> 2 | otherwise -> 31+ -> \x -> if | x <= 'b' -> 3 | x <= 'c' -> 0 | otherwise -> 32+ -> \x -> if | x <= 'a' -> 3 | x <= 'b' -> 1 | otherwise -> 33+ -> \_ -> 3 -- black holeImap (match dfa) ["", "abc", "abcabc", "aa","abca", 'a' : 'a' : undefined]"[False,False,False,True,True,True]Run  on the input.Because we have analysed a language, in some cases we can determine an input without traversing all of the input. That's not the cases with  $. let dfa = fromRE $ RE.star "abc"Bmap (match dfa) ["", "abc", "abcabc", "aa", 'a' : 'a' : undefined][True,True,True,False,False]Holds: $ ( re) xs == $ re xs Uall (match (fromRE r)) $ take 10 $ RE.generate (curry QC.choose) 42 (r :: RE.RE Char)  SafeKe #$%&'./1302467EE67./01234%&'#$  !"#$%&'()*+,-./0123456789 :;<=>?@AABCDEFGHIJKLMNOPQRST:;<79=>U+?V34WX-Y/Z[\]^_`abcdefghijklmnopqrst:;<79=>?V34Wuvwxyz{|}~ :;<79=>?V34W-Y/v     9 @ < 7 8 6 W X 1 w   w 66        kleene-0-5hRBmmcnM8J13794EiikvgKleene.Internal.PartitionKleene.Internal.SetsKleene.Internal.PrettyKleene.Classes Kleene.Equiv Kleene.ERE Kleene.Monad Kleene.REKleene.Functor Kleene.DFAREDFAKleene Partition unPartition invariantfromSeparators fromRSetsfromRSetwholesizeexamples intervalswedgesplittoSF$fMonoidPartition$fSemigroupPartition$fArbitraryPartition$fShowPartition $fEqPartition$fOrdPartitiondotRSetPrettyprettyprettyS putPretty $fPretty() $fPrettyBool $fPrettyChar $fPrettyRSet Complement complement TransitionMap transitionMap Equivalent equivalentMatchmatchDerivatenullablederivate FiniteKleene everything charRangedotanyCharemptyepscharappendsunionsstaroneofEquiv$fPartialOrdEquiv $fEqEquiv $fShowEquiv$fSemigroupEquiv $fMonoidEquiv$fBoundedJoinSemiLatticeEquiv$fJoinSemiLatticeEquiv $fPrettyEquiv$fComplementEquiv$fEquivalentEquiv $fMatchEquiv$fDerivateEquiv $fKleeneEquivEREEREChars EREAppendEREUnionEREStarERENot intersectionsstringisEmpty isEverything leadingChars $fPrettyERE$fCoArbitraryERE$fArbitraryERE $fIsStringERE$fBoundedLatticeERE $fLatticeERE$fBoundedMeetSemiLatticeERE$fMeetSemiLatticeERE$fBoundedJoinSemiLatticeERE$fJoinSemiLatticeERE $fMonoidERE$fSemigroupERE$fEquivalentcERE$fTransitionMapcERE $fMatchcERE$fDerivatecERE$fComplementcERE$fFiniteKleenecERE $fKleenecERE$fEqERE$fOrdERE $fShowEREMMCharsMAppendMUnionMStarisEpsgeneratetoKleene $fPrettyM$fCoArbitraryM $fArbitraryM $fIsStringM$fBoundedJoinSemiLatticeM$fJoinSemiLatticeM $fMonoidM $fSemigroupM $fMatchcM $fDerivatecM $fKleenecM$fMonadM$fApplicativeM$fEqM$fOrdM$fShowM $fFunctorM $fFoldableM$fTraversableMRECharsREAppendREUnionREStar $fPrettyRE$fCoArbitraryRE $fArbitraryRE $fIsStringRE$fBoundedJoinSemiLatticeRE$fJoinSemiLatticeRE $fMonoidRE $fSemigroupRE$fEquivalentcRE$fTransitionMapcRE $fMatchcRE $fDerivatecRE$fFiniteKleenecRE $fKleenecRE$fEqRE$fOrdRE$fShowREK GreedinessGreedy NonGreedyfew everything1toREfromREtoRA $fPrettyK$fAlternativeK$fApplicativeK $fFunctorK $fIsStringK$fEqGreediness$fOrdGreediness$fShowGreediness$fEnumGreediness$fBoundedGreediness dfaTransition dfaAcceptable dfaBlackholesfromEREfromTM fromTMEquivtoERE $fPrettyDFA$fComplementcDFA $fMatchcDFA $fShowDFAbaseGHC.EnummaxBound+range-set-list-0.1.3-HrO42WndNOLGlCajTiS11PData.RangeSet.MapRSetGHC.BaseString System.IOputStrLnghc-prim GHC.Classesnot==%lattices-1.7.1-JNc189eGBPKDwoaMePSTKmAlgebra.PartialOrd PartialOrdOrd comparableMonadEq ApplicativeFunctormany.regex-applicative-0.3.3-FT1HMlwLQTj62mC0WMSukOText.Regex.Applicative.TypesKEmptyKPureKCharKAppendKUnionKStarKMapKString GHC.TypesIntid