rere-0.1: Regular-expressions extended with fixpoints for context-free powers

Safe HaskellSafe
LanguageHaskell2010

RERE

Contents

Description

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

Some examples are in RERE.Examples module.

Synopsis

Regular expressions with fixpoints

data RE a Source #

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
Monad RE Source # 
Instance details

Defined in RERE.Type

Methods

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

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

return :: a -> RE a #

fail :: String -> RE a #

Functor RE Source # 
Instance details

Defined in RERE.Type

Methods

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

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

Applicative RE Source # 
Instance details

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 #

Foldable RE Source # 
Instance details

Defined in RERE.Type

Methods

fold :: Monoid m => RE m -> 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 Source # 
Instance details

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

Eq a => Eq (RE a) Source # 
Instance details

Defined in RERE.Type

Methods

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

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

Ord a => Ord (RE a) Source # 
Instance details

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 #

Show a => Show (RE a) Source # 
Instance details

Defined in RERE.Type

Methods

showsPrec :: Int -> RE a -> ShowS #

show :: RE a -> String #

showList :: [RE a] -> ShowS #

Ord a => IsString (RE a) Source # 
Instance details

Defined in RERE.Type

Methods

fromString :: String -> RE a #

Ord a => Semigroup (RE a) Source # 
Instance details

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 #

(Absurd a, Ord a) => Arbitrary (RE a) Source # 
Instance details

Defined in RERE.Type

Methods

arbitrary :: Gen (RE a) #

shrink :: RE a -> [RE a] #

Smart constructors

ch_ :: Char -> RE a Source #

Smart Ch, as it takes Char argument.

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

Smart Alt.

star_ :: RE a -> RE a Source #

Smart Star.

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

Smart Let

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

Smart Fix.

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

Variable substitution.

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

Construct literal String regex.

Operations

nullable :: RE a -> Bool Source #

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

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

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

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

This function is slow.

size :: RE a -> Int Source #

Size of RE. Counts constructors.

Matching

match :: RE Void -> String -> Bool Source #

Match string by iteratively differentiating the regular expression.

This version is slow, consider using matchR.

Generation

generate Source #

Arguments

:: Int

star upper size

-> Int

fix unroll

-> RE Void 
-> Maybe (Gen String) 

Generate strings.

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

Variables

data Var a Source #

Var is essentially Maybe.

Constructors

B

bound

F a

free variable.

Instances
Functor Var Source # 
Instance details

Defined in RERE.Var

Methods

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

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

Foldable Var Source # 
Instance details

Defined in RERE.Var

Methods

fold :: Monoid m => Var m -> 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 Source # 
Instance details

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

Eq a => Eq (Var a) Source # 
Instance details

Defined in RERE.Var

Methods

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

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

Ord a => Ord (Var a) Source # 
Instance details

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 #

Show a => Show (Var a) Source # 
Instance details

Defined in RERE.Var

Methods

showsPrec :: Int -> Var a -> ShowS #

show :: Var a -> String #

showList :: [Var a] -> ShowS #

IsString a => IsString (Var a) Source # 
Instance details

Defined in RERE.Var

Methods

fromString :: String -> Var a #

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

Analogue of maybe for Var.

data Name Source #

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

Instances
Eq Name Source # 
Instance details

Defined in RERE.Var

Methods

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

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

Ord Name Source # 
Instance details

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 #

Show Name Source # 
Instance details

Defined in RERE.Var

Methods

showsPrec :: Int -> Name -> ShowS #

show :: Name -> String #

showList :: [Name] -> ShowS #

IsString Name Source # 
Instance details

Defined in RERE.Var

Methods

fromString :: String -> Name #

Context-free grammars

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

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

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

Single equation in context-free-grammar equation.

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

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

Knot-tied recursive regular expression.

Instances
Show (RR s) Source # 
Instance details

Defined in RERE.Ref

Methods

showsPrec :: Int -> RR s -> ShowS #

show :: RR s -> String #

showList :: [RR s] -> ShowS #

matchR :: RE Void -> String -> Bool Source #

Convert RE to RR and then match.

Significantly faster than match.

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

Match and print final RR + stats.

ST

data RST s Source #

Knot-tied recursive regular expression.

Instances
Show (RST s) Source # 
Instance details

Defined in RERE.ST

Methods

showsPrec :: Int -> RST s -> ShowS #

show :: RST s -> String #

showList :: [RST s] -> ShowS #

matchST :: RE Void -> String -> Bool Source #

Convert RE to RST and then match.

Significantly faster than match.

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

Match and print final RR + stats.

Character classes

type CharClasses = Set Char Source #

Character classes are represented by partition lower bounds.

charClasses :: RE a -> CharClasses Source #

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

Map char to the representer of a class.

Pretty printing (as LaTeX)

putLatex :: RE Void -> IO () Source #

Pretty-print RE as LaTeX code.

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

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

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

Pretty-print CFG given the names.