Kleene.Monad

Documentation

data M c

Regular expression which has no restrictions on the elements. Therefore we can have Monad instance, i.e. have a regexp where characters are regexps themselves.

Because there are no optimisations, it's better to work over small alphabets. On the other hand, we can work over infinite alphabets, if we only use small amount of symbols!

>>> putPretty $ string [True, False]
^10$

>>> let re  = string [True, False, True]
>>> let re' = re >>= \b -> if b then char () else star (char ())
>>> putPretty re'
^..*.$

Constructors

MChars [c]

One of the characters

MAppend [M c]

Concatenation

MUnion [c] [M c]

Union

MStar (M c)

Kleene star

Instances

Monad M

Defined in Kleene.Monad

Methods

(>>=) :: M a -> (a -> M b) -> M b

(>>) :: M a -> M b -> M b

return :: a -> M a

fail :: String -> M a

Functor M

Defined in Kleene.Monad

Methods

fmap :: (a -> b) -> M a -> M b

(<$) :: a -> M b -> M a

Applicative M

Defined in Kleene.Monad

Methods

pure :: a -> M a

(<*>) :: M (a -> b) -> M a -> M b

liftA2 :: (a -> b -> c) -> M a -> M b -> M c

(*>) :: M a -> M b -> M b

(<*) :: M a -> M b -> M a

Foldable M

Defined in Kleene.Monad

Methods

fold :: Monoid m => M m -> m

foldMap :: Monoid m => (a -> m) -> M a -> m

foldr :: (a -> b -> b) -> b -> M a -> b

foldr' :: (a -> b -> b) -> b -> M a -> b

foldl :: (b -> a -> b) -> b -> M a -> b

foldl' :: (b -> a -> b) -> b -> M a -> b

foldr1 :: (a -> a -> a) -> M a -> a

foldl1 :: (a -> a -> a) -> M a -> a

toList :: M a -> [a]

null :: M a -> Bool

length :: M a -> Int

elem :: Eq a => a -> M a -> Bool

maximum :: Ord a => M a -> a

minimum :: Ord a => M a -> a

sum :: Num a => M a -> a

product :: Num a => M a -> a

Traversable M

Defined in Kleene.Monad

Methods

traverse :: Applicative f => (a -> f b) -> M a -> f (M b)

sequenceA :: Applicative f => M (f a) -> f (M a)

mapM :: Monad m => (a -> m b) -> M a -> m (M b)

sequence :: Monad m => M (m a) -> m (M a)

(Eq c, Enum c, Bounded c) => Match c (M c)

Defined in Kleene.Monad

Methods

match :: M c -> [c] -> Bool

match8 :: M c -> ByteString -> Bool

(Eq c, Enum c, Bounded c) => Derivate c (M c)

Defined in Kleene.Monad

Methods

nullable :: M c -> Bool

derivate :: c -> M c -> M c

CharKleene c (M c)

Defined in Kleene.Monad

Methods

char :: c -> M c

string :: [c] -> M c

Eq c => Eq (M c)

Defined in Kleene.Monad

Methods

(==) :: M c -> M c -> Bool

(/=) :: M c -> M c -> Bool

Ord c => Ord (M c)

Defined in Kleene.Monad

Methods

compare :: M c -> M c -> Ordering

(<) :: M c -> M c -> Bool

(<=) :: M c -> M c -> Bool

(>) :: M c -> M c -> Bool

(>=) :: M c -> M c -> Bool

max :: M c -> M c -> M c

min :: M c -> M c -> M c

Show c => Show (M c)

Defined in Kleene.Monad

Methods

showsPrec :: Int -> M c -> ShowS

show :: M c -> String

showList :: [M c] -> ShowS

c ~ Char => IsString (M c)

Defined in Kleene.Monad

Methods

fromString :: String -> M c

Semigroup (M c)

Defined in Kleene.Monad

Methods

(<>) :: M c -> M c -> M c

sconcat :: NonEmpty (M c) -> M c

stimes :: Integral b => b -> M c -> M c

Monoid (M c)

Defined in Kleene.Monad

Methods

mempty :: M c

mappend :: M c -> M c -> M c

mconcat :: [M c] -> M c

(Eq c, Enum c, Bounded c, Arbitrary c) => Arbitrary (M c)

Defined in Kleene.Monad

Methods

arbitrary :: Gen (M c)

shrink :: M c -> [M c]

CoArbitrary c => CoArbitrary (M c)

Defined in Kleene.Monad

Methods

coarbitrary :: M c -> Gen b -> Gen b

(Pretty c, Eq c) => Pretty (M c)

Defined in Kleene.Monad

Methods

pretty :: M c -> String

prettyS :: M c -> ShowS

Kleene (M c)

Defined in Kleene.Monad

Methods

empty :: M c

eps :: M c

appends :: [M c] -> M c

unions :: [M c] -> M c

star :: M c -> M c

Construction

Binary operators are

• <> for append

There are no binary operator for union. Use unions.

empty :: M c

Empty regex. Doesn't accept anything.

>>> putPretty (empty :: M Bool)
^[]$

match (empty :: M Char) (s :: String) === False

eps :: M c

Empty string. Note: different than empty.

>>> putPretty (eps :: M Bool)
^$

>>> putPretty (mempty :: M Bool)
^$

match (eps :: M Char) s === null (s :: String)

char :: c -> M c

>>> putPretty (char 'x')
^x$

charRange :: Enum c => c -> c -> M c

Note: we know little about c.

>>> putPretty $ charRange 'a' 'z'
^[abcdefghijklmnopqrstuvwxyz]$

anyChar :: (Bounded c, Enum c) => M c

Any character. Note: different than dot!

>>> putPretty (anyChar :: M Bool)
^[01]$

appends :: [M c] -> M c

Concatenate regular expressions.

unions :: [M c] -> M c

Union of regular expressions.

Lattice laws don't hold structurally:

star :: M c -> M c

Kleene star.

string :: [c] -> M c

Literal string.

>>> putPretty ("foobar" :: M Char)
^foobar$

>>> putPretty ("(.)" :: M Char)
^\(\.\)$

>>> putPretty $ string [False, True]
^01$

Derivative

nullable :: M c -> Bool

We say that a regular expression r is nullable if the language it defines contains the empty string.

>>> nullable eps
True

>>> nullable (star "x")
True

>>> nullable "foo"
False

derivate :: (Eq c, Enum c, Bounded c) => c -> M c -> M c

Intuitively, the derivative of a language \(\mathcal{L} \subset \Sigma^\star\) with respect to a symbol \(a \in \Sigma\) 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' $ unions ["xyz", "abc"]
^yz$

>>> putPretty $ derivate 'x' $ star "xyz"
^yz(xyz)*$

Generation

generate

Arguments

:: Int

seed

-> M c

-> [[c]]

infinite list of results

Generate random strings of the language M c describes.

>>> let example = traverse_ print . take 3 . generate 42
>>> example "abc"
"abc"
"abc"
"abc"

>>> example $ star $ unions ["a", "b"]
"ababbb"
"baab"
"abbababaa"

xx >>> example empty

expensive-prop> all (match r) $ take 10 $ generate 42 (r :: M Bool)

Conversion

toKleene :: CharKleene c k => M c -> k

Convert to Kleene

>>> let re = charRange 'a' 'z'
>>> putPretty re
^[abcdefghijklmnopqrstuvwxyz]$

>>> putPretty (toKleene re :: RE Char)
^[a-z]$

Other

isEmpty :: M c -> Bool

Whether M is (structurally) equal to empty.

isEps :: M c -> Bool

Whether M is (structurally) equal to eps.