!6      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Safe$ kleene1 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.kleeneCheck invariant.kleene Construct  from list of s.(RSet intervals are closed on both sides.kleeneCount of sets in a . size whole1size $ split (10 :: Word8)2size (asPartitionChar p) >= 1 kleene'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) kleene2all (uncurry (<=)) $ intervals $ asPartitionChar p kleeneWedge 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 kleeneSimplest partition: given x partition space into [min..x) and [x .. max]split (128 :: Word8)fromSeparators [128] kleeneMake a step function.kleeneSee  .kleeneinvariant (asPartitionChar p)  Safe&kleeneAll but the newline.Safe&'(kleene Pretty class.For  ::   -> 8 gives a representation accepted by many regex engines.kleene  . kleene!Escapes special regexp charactersSafe&'8@AC7L#kleeneComplement of the language.Law: * ($ f) xs =  (* f) xs %kleeneTransition map.'kleeneEquivalence induced by ).Law: ( re1 re2  = forall s. * re1 s == * re1 s )kleeneAn f# can be used to match on the input.-kleene&Does language contain an empty string?.kleeneDerivative of a language.0kleene Everything.  \Sigma^\star.1kleene1 a z = ^[a-z]$.2kleeneGeneralisation of 1.3kleene.! Every character except new line \n.4kleeneAny character. Note: different than 3!7kleeneSingle character9kleeneKleene algebra.If k is  it's expected that < = ; if k is   it's expected that = =  . ,https://en.wikipedia.org/wiki/Kleene_algebraWikipedia: Kleene Algebra.:kleene%Empty regex. Doesn't accept anything.;kleeneEmpty string. Note: different than :.<kleeneConcatenation.=kleeneUnion.>kleene Kleene star.?kleeneOne of the characters.!"#$%&'()+*,.-/2031546789><;=:?9><;=:678?/203154,.-)+*'(%&#$!"Safe &'=?@ACXAkleeneRegular expression]Constructors are exposed, but you should use smart constructors in this module to construct A.The  and  instances are structural. The Kleene] etc constructors do "weak normalisation", so for values constructed using those operations $ witnesses "weak equivalence". See U$ 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. Sr will eventually terminate, but may create more redundant states if starting regexp is not "weakly normalised").BkleeneSingle characterCkleene ConcatenationDkleeneUnionEkleene Kleene starFkleene%Empty regex. Doesn't accept anything.putPretty (empty :: RE Char)^[]$putPretty (bottom :: RE Char)^[]$0match (empty :: RE Char) (s :: String) === Falsekleene Everything.putPretty everything^[^]*$4match (everything :: RE Char) (s :: String) === TrueGkleeneEmpty string. Note: different than F. putPretty eps^$putPretty (mempty :: RE Char)^$/match (eps :: RE Char) s === null (s :: String)HkleeneputPretty (char 'x')^x$IkleeneputPretty $ charRange 'a' 'z'^[a-z]$JkleeneAny character. Note: different than dot!putPretty anyChar^[^]$Kkleene Concatenate regular expressions.((asREChar r <> s) <> t === r <> (s <> t)asREChar r <> empty === emptyempty <> asREChar r === emptyasREChar r <> eps === reps <> asREChar r === rLkleeneUnion 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 === everythingMkleene 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 epsNkleeneLiteral string.putPretty ("foobar" :: RE Char)^foobar$putPretty ("(.)" :: RE Char)^\(\.\)$OkleeneeWe say that a regular expression r is nullable if the language it defines contains the empty string. nullable epsTruenullable (star "x")Truenullable "foo"FalsePkleene*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)*$QkleeneNot only we can decide whether A3 is nullable, we can also remove the empty string:putPretty $ nullableProof eps^[]$$putPretty $ nullableProof $ star "x"^xx*$putPretty $ nullableProof "foo"NothingQ is consistent with O:2isJust (nullableProof r) === nullable (asREChar r)0The returned regular expression is not nullable:8maybe True (not . nullable) $ nullableProof $ asREChar rVIf we union with empty regex, we get a equivalent regular expression we started with:<maybe r (eps \/) (nullableProof r) `equivalent` (asREChar r)RkleeneWhether A is (structurally) equal to F.JisEmpty r === all (not . nullable) (Map.keys $ transitionMap $ asREChar r)Skleene"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 -> "^[]$"Tkleene-Leading character sets of regular expression.leadingChars "foo"fromSeparators "ef"#leadingChars (star "b" <> star "e")fromSeparators "abde" leadingChars (charRange 'b' 'z')fromSeparators "az"Ukleene#Whether two regexps are equivalent. U 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 ==> U 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*)*$TrueVkleene(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)Vkleenecharacter range generatorkleeneseedkleeneinfinite list of resultsABCDEFGHIJKLMNOPQRSTUV Trustworthy &'1=?@ACMWkleeneRegular-expressions for which  is (.$let re1 = star "a" <> "a" :: RE Char$let re2 = "a" <> star "a" :: RE Char re1 == re2FalseEquiv re1 == Equiv re2TrueW 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)Ykleenea \preceq b := a \lor b = b WXWXSafe &'=?@ACX՝hkleeneExtended 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 v makes it hard.ikleeneSingle characterjkleene ConcatenationkkleeneUnionlkleene Kleene starmkleene Complementnkleene*Convert from ordinary regular expression, A.okleene%Empty regex. Doesn't accept anything.putPretty (empty :: ERE Char)^[]$putPretty (bottom :: ERE Char)^[]$1match (empty :: ERE Char) (s :: String) === Falsekleene Everything."putPretty (everything :: ERE Char)^~[]$putPretty (top :: ERE Char)^~[]$5match (everything :: ERE Char) (s :: String) === TruepkleeneEmpty string. Note: different than o. putPretty eps^$putPretty (mempty :: ERE Char)^$0match (eps :: ERE Char) s === null (s :: String)qkleeneputPretty (char 'x')^x$rkleeneputPretty $ charRange 'a' 'z'^[a-z]$skleeneAny character. Note: different than dot!putPretty anyChar^[^]$tkleene Concatenate regular expressions.asEREChar r <> empty === emptyempty <> asEREChar r === empty)(asEREChar r <> s) <> t === r <> (s <> t)asEREChar r <> eps === reps <> asEREChar r === rukleeneUnion 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 \/ asEREChar r === everything(asEREChar r \/ everything === everythingvkleene$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 /\ asEREChar r === rasEREChar r /\ everything === rwkleene Complement.)complement (complement r) === asEREChar rxkleene Kleene star.$star (star r) === star (asEREChar r)star eps === asEREChar epsstar empty === asEREChar eps%star anyChar === asEREChar everything$star (asEREChar r \/ eps) === star r0star (char c \/ eps) === star (char (c :: Char))star (empty \/ eps) === epsykleeneLiteral string. putPretty ("foobar" :: ERE Char)^foobar$putPretty ("(.)" :: ERE Char)^\(\.\)$zkleeneeWe 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)False{kleene*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)*$|kleeneWhether h is (structurally) equal to o.}kleeneWhether h is (structurally) equal to .~kleene"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 -> "^[]$"kleene-Leading character sets of regular expression.leadingChars "foo"fromSeparators "ef"#leadingChars (star "b" <> star "e")fromSeparators "abde" leadingChars (charRange 'b' 'z')fromSeparators "az"kleene#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*)*$Truehijklmnopqrstuvwxyz{|}~hijklmopqrstuvxywz{n~|}Safe &'=?@ACX,/kleeneDeterministic 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 s), q_0 \in Q" is the distinguised start state (), 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 ().kleenetransition functionkleene initial statekleene accept stateskleenestates we cannot escapekleeneConvert A 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 holekleeneConvert h to .,We don't always generate a minimal automata: putPretty $ fromERE $ "a" /\ "b" 0 -> \_ -> 11 -> \_ -> 1 -- black holeCompare this to a $ exampleUsing M, we can get a 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 holekleene Create from %.See  for a specific example.kleene Create from  TransitonMap minimising states with '.See  for an example.kleeneConvert  to A."putPretty $ toRE $ fromRE "foobar"^foobar$For N 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 U:'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 AA. 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 h to A: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.kleeneConvert  to h.kleeneConvert to any 9.See  for a specific example.kleeneGet Graphviz dot-code of DFA. let dfa = fromRE $ RE.star "abc"putStr $ toDot dfa digraph dfa { rankdir=LR; // states"0" [shape=doublecircle];"1" [shape=circle];"2" [shape=circle];// initial state"" [shape=none]; "" -> "0";// transitions"0" -> "2"[label="a"]"1" -> "0"[label="c"]"2" -> "1"[label="b"]}kleeneMore flexible version of .kleeneWARNING: The  6 is inefficient, it actually computes the conjunction:!putPretty $ asREChar $ "a" /\ "b"^[]$&putPretty $ asREChar $ "a" /\ star "a"^a$.putPretty $ asREChar $ star "aa" /\ star "aaa"^(a(aaaaaa)*aaaaa)?$kleeneComplement DFA.Complement of  is way easier than of A: 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]kleeneRun  on the input.Because we have analysed a language, in some cases we can determine a result without traversing all of the input. That's not the cases with A *. 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) Safe &'456=?@ACXTkleeneURegular 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'^..*.$kleeneOne of the characterskleene ConcatenationkleeneUnionkleene Kleene starkleene%Empty regex. Doesn't accept anything.putPretty (empty :: M Bool)^[]$/match (empty :: M Char) (s :: String) === FalsekleeneEmpty string. Note: different than .putPretty (eps :: M Bool)^$putPretty (mempty :: M Bool)^$.match (eps :: M Char) s === null (s :: String)kleeneputPretty (char 'x')^x$kleeneNote: we know little about c.putPretty $ charRange 'a' 'z'^[abcdefghijklmnopqrstuvwxyz]$kleeneAny character. Note: different than dot!putPretty (anyChar :: M Bool)^[01]$kleene Concatenate regular expressions.kleeneUnion of regular expressions.%Lattice laws don't hold structurally:kleene Kleene star.kleeneLiteral string.putPretty ("foobar" :: M Char)^foobar$putPretty ("(.)" :: M Char)^\(\.\)$ putPretty $ string [False, True]^01$kleeneeWe say that a regular expression r is nullable if the language it defines contains the empty string. nullable epsTruenullable (star "x")Truenullable "foo"Falsekleene*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$0putPretty $ derivate 'x' $ unions ["xyz", "abc"]^yz$%putPretty $ derivate 'x' $ star "xyz" ^yz(xyz)*$kleeneWhether  is (structurally) equal to .kleeneWhether  is (structurally) equal to .kleene(Generate random strings of the language M c describes.4let example = traverse_ print . take 3 . generate 42 example "abc""abc""abc""abc""example $ star $ unions ["a", "b"]"ababbb""baab" "abbababaa"xx >>> example emptyCexpensive-prop> all (match r) $ take 10 $ generate 42 (r :: M Bool)kleene Convert to Kleenelet re = charRange 'a' 'z' putPretty re^[abcdefghijklmnopqrstuvwxyz]$"putPretty (toKleene re :: RE Char)^[a-z]$kleeneseedkleeneinfinite list of resultsSafeTABCDEFGHIJKLMNOPQRSTUVABCDEFGHIJKLMNOPSTUVRQSafe&'mkleene    regular expression.kleeneStar behaviourkleenekleenekleene, 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","")kleeneputPretty anyChar^[^]$kleene&putPretty $ oneof ("foobar" :: [Char]) ^[a-bfor]$kleeneputPretty $ char 'x'^x$kleeneputPretty $ charRange 'a' 'z'^[a-z]$kleene putPretty dot^.$kleeneputPretty everything^[^]*$kleeneputPretty everything1 ^[^][^]*$kleeneMatches nothing?kleeneMatches whole input?kleene Match using regex-applicativekleene Convert to RE.+putPretty (toRE $ many "foo" :: RE.RE Char)^(foo)*$kleeneConvert to any Kleenekleene Convert from RE.Note: all Es 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"kleeneConvert  to  from regex-applicative.FR.match (toRA ("xx" *> everything <* "zz" :: K Char String)) "xxyyyzz" Just "yyy" See also .kleeneOConvert 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)*$ Safent Safe&' kleene    regular expression.kleene, not . Let's define two similar regexps:let re1 = liftF2 (,) (few1 $ char 'a') (some1 $ char 'a'):let re2 = liftF2 (,) (some1 $ char 'a') (few1 $ 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) "aaaaa"Just ('a' :| "",'a' :| "aaa")R.match (toRA re2) "aaaaa"Just ('a' :| "aaa",'a' :| "")kleeneputPretty anyChar^[^]$kleene&putPretty $ oneof ("foobar" :: [Char]) ^[a-bfor]$kleeneputPretty $ char 'x'^x$kleeneputPretty $ charRange 'a' 'z'^[a-z]$kleene putPretty dot^.$kleeneputPretty everything1 ^[^][^]*$kleeneMatches nothing?kleeneMatches whole input?kleene Match using regex-applicativekleene Convert to RE.5putPretty (toRE $ some1 (string "foo") :: RE.RE Char) ^foo(foo)*$kleeneConvert to any KleenekleeneConvert  to  from regex-applicative.aR.match (toRA (string "xx" .> everything1 <. string "zz" :: K1 Char (NonEmpty Char))) "xxyyzyyzz"Just ('y' :| "yzyy") See also .kleene%putPretty $ nullableProof (pure True)Right 1 , ^[]$9putPretty $ nullableProof (many "xyz" :: K Char [String])Right [] , ^xyz(xyz)*$]putPretty $ nullableProof (many $ toList <$> optional "x" <|> many "yz" :: K Char [[String]])$Right [] , ^(x|yz(yz)*)(x|yz(yz)*)*$kleeneOConvert 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+!"#$%&)*+,-./4513026879:=;<>AWXh+AhWX9:=;<>687/451302,-.)*+%&#$!" !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQ RSTUKLIDFMNOJ@AVW9X;YZZ[\]^_`abcdefghijklmnopKLIDFMNq7OJ@AWr9X;stuvwxyz{|}~p      K L I D F M N O J @ A W Y FPIDECWr=p  F P I D E W r J = V CC   !kleene-0.1-AW5UH4xkZdlETdHpypR0ugKleene.Internal.PartitionKleene.Internal.SetsKleene.Internal.PrettyKleene.Classes Kleene.RE Kleene.Equiv Kleene.ERE Kleene.DFA Kleene.MonadKleene.FunctorKleene.Functor.NonEmptyREAlgebra.LatticeLatticejoinsKleene.Internal.REDFAKleene.Internal.FunctorKleene Partition unPartition invariantfromSeparators fromRSetsfromRSetwholesizeexamples intervalswedgesplittoSF$fMonoidPartition$fSemigroupPartition$fArbitraryPartition$fShowPartition $fEqPartition$fOrdPartitiondotRSetPrettyprettyprettyS putPretty $fPretty[] $fPretty(,)$fPrettyEither $fPrettyMaybe $fPretty() $fPrettyBool $fPrettyChar $fPrettyRSetToLatin1toLatin1 Complement complement TransitionMap transitionMap Equivalent equivalentMatchmatchmatch8Derivatenullablederivate FiniteKleene everything charRangedotanyCharnotChar CharKleenecharstringemptyepsappendsunionsstaroneof$fToLatin1RSetRECharsREAppendREUnionREStar nullableProofisEmpty leadingCharsgenerateEquiv$fPartialOrdEquiv $fEqEquiv $fShowEquiv$fSemigroupEquiv $fMonoidEquiv$fBoundedJoinSemiLatticeEquiv$fBoundedMeetSemiLatticeEquiv$fLatticeEquiv $fPrettyEquiv$fComplementEquiv$fEquivalentEquiv $fMatchEquiv$fDerivateEquiv$fCharKleeneEquiv $fKleeneEquivEREEREChars EREAppendEREUnionEREStarERENotfromRE intersections isEverything $fToLatin1ERE $fPrettyERE$fCoArbitraryERE$fArbitraryERE $fIsStringERE$fBoundedMeetSemiLatticeERE$fBoundedJoinSemiLatticeERE $fLatticeERE $fMonoidERE$fSemigroupERE$fEquivalentcERE$fTransitionMapcERE $fMatchcERE$fDerivatecERE$fComplementcERE$fFiniteKleenecERE$fCharKleenecERE $fKleeneERE$fEqERE$fOrdERE $fShowERE dfaTransition dfaInitial dfaAcceptable dfaBlackholesfromEREfromTM fromTMEquivtoREtoEREtoKleenetoDottoDot'$fComplementcRE$fBoundedMeetSemiLatticeRE$fBoundedJoinSemiLatticeRE $fLatticeRE $fPrettyDFA$fDerivatecDFA$fComplementcDFA $fMatchcDFA $fShowDFAMMCharsMAppendMUnionMStarisEps $fPrettyM$fCoArbitraryM $fArbitraryM $fIsStringM $fMonoidM $fSemigroupM $fMatchcM $fDerivatecM$fCharKleenecM $fKleeneM$fMonadM$fApplicativeM$fEqM$fOrdM$fShowM $fFunctorM $fFoldableM$fTraversableMK GreedinessGreedy NonGreedyfew everything1toRAK1some1 $fPrettyK1$fAltK1 $fApplyK1 $fFunctorK1baseGHC.EnummaxBound*range-set-list-0.1.3-VTHWbvGvnS5Gw5W7RZzIqData.RangeSet.MapRSetGHC.BaseString System.IOputStrLnghc-prim GHC.ClassesnotMonoidmappendEqOrd==!lattices-2-KTzUXBiBQFmGHdhLxwXQFmAlgebra.PartialOrd PartialOrd comparableid/\Monad ApplicativeFunctormany.regex-applicative-0.3.3-I3rRNj55s533YYKiqKRdUuText.Regex.Applicative.Types $fPrettyKKEmptyKPureKCharKAppendKUnionKStarKMapKStringfew1