RERE

Regular-expressions extended with fixpoints for context-free powers.

Some examples are in RERE.Examples module.

Regular expressions with fixpoints

data RE a

Regular expression with fixed point.

Constructors

Null

Full

Eps

Ch CharSet

App (RE a) (RE a)

Alt (RE a) (RE a)

Star (RE a)

Var a

Let Name (RE a) (RE (Var a))

Fix Name (RE (Var a))

Instances

Foldable RE

Defined in RERE.Type

Methods

fold :: Monoid m => RE m -> m

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

foldMap' :: Monoid m => (a -> m) -> RE a -> m

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

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

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

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

foldr1 :: (a -> a -> a) -> RE a -> a

foldl1 :: (a -> a -> a) -> RE a -> a

toList :: RE a -> [a]

null :: RE a -> Bool

length :: RE a -> Int

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

maximum :: Ord a => RE a -> a

minimum :: Ord a => RE a -> a

sum :: Num a => RE a -> a

product :: Num a => RE a -> a

Traversable RE

Defined in RERE.Type

Methods

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

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

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

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

Applicative RE

Defined in RERE.Type

Methods

pure :: a -> RE a

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

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

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

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

Functor RE

Defined in RERE.Type

Methods

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

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

Monad RE

Defined in RERE.Type

Methods

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

(>>) :: RE a -> RE b -> RE b

return :: a -> RE a

(Absurd a, Ord a) => Arbitrary (RE a)

Defined in RERE.Type

Methods

arbitrary :: Gen (RE a)

shrink :: RE a -> [RE a]

Ord a => IsString (RE a)

Defined in RERE.Type

Methods

fromString :: String -> RE a

Ord a => Semigroup (RE a)

Defined in RERE.Type

Methods

(<>) :: RE a -> RE a -> RE a

sconcat :: NonEmpty (RE a) -> RE a

stimes :: Integral b => b -> RE a -> RE a

Show a => Show (RE a)

Defined in RERE.Type

Methods

showsPrec :: Int -> RE a -> ShowS

show :: RE a -> String

showList :: [RE a] -> ShowS

Eq a => Eq (RE a)

Defined in RERE.Type

Methods

(==) :: RE a -> RE a -> Bool

(/=) :: RE a -> RE a -> Bool

Ord a => Ord (RE a)

Defined in RERE.Type

Methods

compare :: RE a -> RE a -> Ordering

(<) :: RE a -> RE a -> Bool

(<=) :: RE a -> RE a -> Bool

(>) :: RE a -> RE a -> Bool

(>=) :: RE a -> RE a -> Bool

max :: RE a -> RE a -> RE a

min :: RE a -> RE a -> RE a

Smart constructors

ch_ :: Char -> RE a

Smart Ch, as it takes Char argument.

(\/) :: Ord a => RE a -> RE a -> RE a infixl 5

Smart Alt.

star_ :: RE a -> RE a

Smart Star.

let_ :: Ord a => Name -> RE a -> RE (Var a) -> RE a

Smart Let

fix_ :: Ord a => Name -> RE (Var a) -> RE a

Smart Fix.

(>>>=) :: Ord b => RE a -> (a -> RE b) -> RE b infixl 4

Variable substitution.

string_ :: Ord a => String -> RE a

Construct literal String regex.

Operations

nullable :: RE a -> Bool

Whether the regular expression accepts empty string, or whether the formal language contains empty string.

>>> nullable Eps
True

>>> nullable (ch_ 'c')
False

derivative :: Char -> RE Void -> RE Void

Derivative of regular exression to respect of character. derivative c r is \(D_c(r)\).

compact :: Ord a => RE a -> RE a

Re-apply smart constructors on RE structure, thus potentially making it smaller.

This function is slow.

size :: RE a -> Int

Size of RE. Counts constructors.

Matching

match :: RE Void -> String -> Bool

Match string by iteratively differentiating the regular expression.

This version is slow, consider using matchR.

Generation

generate

Arguments

:: Int

star upper size

-> Int

fix unroll

-> RE Void

-> Maybe (Gen String)

Generate strings.

>>> runGen 43 $ generate 10 10 $ star_ (ch_ 'a')
"aaaaaaaaaa"

>>> runGen 44 $ generate 10 10 $ star_ (ch_ 'a')
"aaa"

Variables

data Var a

Var is essentially Maybe.

Constructors

B

bound

F a

free variable.

Instances

Foldable Var

Defined in RERE.Var

Methods

fold :: Monoid m => Var m -> m

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

foldMap' :: Monoid m => (a -> m) -> Var a -> m

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

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

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

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

foldr1 :: (a -> a -> a) -> Var a -> a

foldl1 :: (a -> a -> a) -> Var a -> a

toList :: Var a -> [a]

null :: Var a -> Bool

length :: Var a -> Int

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

maximum :: Ord a => Var a -> a

minimum :: Ord a => Var a -> a

sum :: Num a => Var a -> a

product :: Num a => Var a -> a

Traversable Var

Defined in RERE.Var

Methods

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

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

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

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

Functor Var

Defined in RERE.Var

Methods

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

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

IsString a => IsString (Var a)

Defined in RERE.Var

Methods

fromString :: String -> Var a

Show a => Show (Var a)

Defined in RERE.Var

Methods

showsPrec :: Int -> Var a -> ShowS

show :: Var a -> String

showList :: [Var a] -> ShowS

Eq a => Eq (Var a)

Defined in RERE.Var

Methods

(==) :: Var a -> Var a -> Bool

(/=) :: Var a -> Var a -> Bool

Ord a => Ord (Var a)

Defined in RERE.Var

Methods

compare :: Var a -> Var a -> Ordering

(<) :: Var a -> Var a -> Bool

(<=) :: Var a -> Var a -> Bool

(>) :: Var a -> Var a -> Bool

(>=) :: Var a -> Var a -> Bool

max :: Var a -> Var a -> Var a

min :: Var a -> Var a -> Var a

unvar :: r -> (a -> r) -> Var a -> r

Analogue of maybe for Var.

data Name

Names carry information used in pretty-printing, but otherwise they all compare EQual.

Instances

IsString Name

Defined in RERE.Var

Methods

fromString :: String -> Name

Show Name

Defined in RERE.Var

Methods

showsPrec :: Int -> Name -> ShowS

show :: Name -> String

showList :: [Name] -> ShowS

Eq Name

Defined in RERE.Var

Methods

(==) :: Name -> Name -> Bool

(/=) :: Name -> Name -> Bool

Ord Name

Defined in RERE.Var

Methods

compare :: Name -> Name -> Ordering

(<) :: Name -> Name -> Bool

(<=) :: Name -> Name -> Bool

(>) :: Name -> Name -> Bool

(>=) :: Name -> Name -> Bool

max :: Name -> Name -> Name

min :: Name -> Name -> Name

Context-free grammars

type CFG n a = Vec n (CFGBase n a)

Context-free grammar represented as n equations of RE (CFGBase) with n variables.

type CFGBase n a = RE (Either (Fin n) a)

Single equation in context-free-grammar equation.

cfgToRE :: (SNatI n, Ord a) => Vec ('S n) Name -> CFG ('S n) a -> RE a

Convert CFG (with names for productions) into RE. Note: the start symbol have to be last equation.

>>> let a = Eps \/ ch_ 'a' <> Var (Left FZ)
>>> let b = Eps \/ ch_ 'b' <> Var (Left (FS FZ))
>>> let cfg = b ::: a ::: VNil

[ begin{aligned} {mathit{b}} &= {varepsilon}cupmathtt{b}{mathit{a}} -- {mathit{a}} &= {varepsilon}cupmathtt{a}{mathit{b}} -- end{aligned}

Faster matching

Ref

data RR s

Knot-tied recursive regular expression.

Instances

Show (RR s)

Defined in RERE.Ref

Methods

showsPrec :: Int -> RR s -> ShowS

show :: RR s -> String

showList :: [RR s] -> ShowS

matchR :: RE Void -> String -> Bool

Convert RE to RR and then match.

Significantly faster than match.

matchDebugR :: RE Void -> String -> IO ()

Match and print final RR + stats.

ST

data RST s

Knot-tied recursive regular expression.

Instances

Show (RST s)

Defined in RERE.ST

Methods

showsPrec :: Int -> RST s -> ShowS

show :: RST s -> String

showList :: [RST s] -> ShowS

matchST :: RE Void -> String -> Bool

Convert RE to RST and then match.

Significantly faster than match.

matchDebugST :: RE Void -> String -> IO ()

Match and print final RR + stats.

Character classes

type CharClasses = Set Char

Character classes are represented by partition lower bounds.

charClasses :: RE a -> CharClasses

Character classes.

We can partition Char so characters in each part, affect the given regular expression in the same way.

If we do some kind of memoising, we can map all characters to classOfChar, making everything smaller.

classOfChar :: CharClasses -> Char -> Char

Map char to the representer of a class.

Pretty printing (as LaTeX)

putLatex :: RE Void -> IO ()

Pretty-print RE as LaTeX code.

putLatexTrace :: RE Void -> String -> IO ()

Run match variant, collect intermediate steps, and pretty-print that trace.

putLatexCFG :: Vec n Name -> CFG n Void -> IO ()

Pretty-print CFG given the names.