Copyright	(C) 2026 - Eitan Chatav
License	BSD-style (see the file LICENSE)
Maintainer	Eitan Chatav <eitan.chatav@gmail.com>
Stability	provisional
Portability	non-portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Control.Lens.Grammar.Kleene

Contents

KleeneStarAlgebra
RegEx

Description

Regular expressions form a Kleene star algebra. See Kleene, Representation of Events in Nerve Nets and Finite Automata

Synopsis

class Monoid k => KleeneStarAlgebra k where
- starK, plusK, optK :: k -> k
- (>|<) :: k -> k -> k
- zeroK :: k
orK :: (Foldable f, KleeneStarAlgebra k) => f k -> k
anyK :: (Foldable f, KleeneStarAlgebra k) => (a -> k) -> f a -> k
data RegEx token
- = Terminal [token]
- | NonTerminal String
- | Sequence (RegEx token) (RegEx token)
- | KleeneStar (RegEx token)
- | KleeneOpt (RegEx token)
- | KleenePlus (RegEx token)
- | RegExam (RegExam token (RegEx token))
data RegExam token alg
- = Fail
- | Pass
- | OneOf (Set token)
- | NotOneOf (Set token) (CategoryTest token)
- | Alternate alg alg
data CategoryTest token
- = AsIn (Categorize token)
- | NotAsIn (Set (Categorize token))

KleeneStarAlgebra

class Monoid k => KleeneStarAlgebra k where Source #

A KleeneStarAlgebra is a ring with a generally non-commutaive multiplication, the Monoid concatenation operator <> with identity mempty; and an idempotent addition, the alternation operator >|< with identity zeroK.

It has three unary operators optK, plusK and the eponymous starK.

starK x = optK (plusK x)

plusK x = x <> starK x

optK x = mempty >|< x

Minimal complete definition

Nothing

Methods

starK :: k -> k Source #

plusK :: k -> k Source #

optK :: k -> k Source #

(>|<) :: k -> k -> k infixl 3 Source #

default (>|<) :: (k ~ f a, Alternative f) => k -> k -> k Source #

zeroK :: k Source #

default zeroK :: (k ~ f a, Alternative f) => k Source #

Instances

Instances details

KleeneStarAlgebra RegBnf Source #
Instance details Defined in Control.Lens.Grammar Methods starK :: RegBnf -> RegBnf Source # plusK :: RegBnf -> RegBnf Source # optK :: RegBnf -> RegBnf Source # (>\|<) :: RegBnf -> RegBnf -> RegBnf Source # zeroK :: RegBnf Source #
KleeneStarAlgebra RegString Source #
Instance details Defined in Control.Lens.Grammar Methods starK :: RegString -> RegString Source # plusK :: RegString -> RegString Source # optK :: RegString -> RegString Source # (>\|<) :: RegString -> RegString -> RegString Source # zeroK :: RegString Source #
(Ord rule, KleeneStarAlgebra rule) => KleeneStarAlgebra (Bnf rule) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods starK :: Bnf rule -> Bnf rule Source # plusK :: Bnf rule -> Bnf rule Source # optK :: Bnf rule -> Bnf rule Source # (>\|<) :: Bnf rule -> Bnf rule -> Bnf rule Source # zeroK :: Bnf rule Source #
Categorized token => KleeneStarAlgebra (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods starK :: RegEx token -> RegEx token Source # plusK :: RegEx token -> RegEx token Source # optK :: RegEx token -> RegEx token Source # (>\|<) :: RegEx token -> RegEx token -> RegEx token Source # zeroK :: RegEx token Source #
(Alternative f, Monoid k) => KleeneStarAlgebra (Ap f k) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods starK :: Ap f k -> Ap f k Source # plusK :: Ap f k -> Ap f k Source # optK :: Ap f k -> Ap f k Source # (>\|<) :: Ap f k -> Ap f k -> Ap f k Source # zeroK :: Ap f k Source #

orK :: (Foldable f, KleeneStarAlgebra k) => f k -> k Source #

cumulative alternation

anyK :: (Foldable f, KleeneStarAlgebra k) => (a -> k) -> f a -> k Source #

universal

RegEx

data RegEx token Source #

The RegExpression type is the prototypical KleeneStarAlgebra.

Constructors

Terminal [token]
NonTerminal String
Sequence (RegEx token) (RegEx token)
KleeneStar (RegEx token)
KleeneOpt (RegEx token)
KleenePlus (RegEx token)
RegExam (RegExam token (RegEx token))

Instances

Instances details

Categorized token => TokenAlgebra token (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Boole Methods tokenClass :: TokenTest token -> RegEx token Source #
TerminalSymbol token (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods terminal :: [token] -> RegEx token Source #
Categorized token => Tokenized token (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods anyToken :: RegEx token Source # token :: token -> RegEx token Source # oneOf :: Foldable f => f token -> RegEx token Source # notOneOf :: Foldable f => f token -> RegEx token Source # asIn :: Categorize token -> RegEx token Source # notAsIn :: Categorize token -> RegEx token Source #
(Categorized token, HasTrie token) => HasTrie (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Associated Types data (:->:) (RegEx token) :: Type -> Type # Methods trie :: (RegEx token -> b) -> RegEx token :->: b # untrie :: (RegEx token :->: b) -> RegEx token -> b # enumerate :: (RegEx token :->: b) -> [(RegEx token, b)] #
Categorized token => Monoid (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods mempty :: RegEx token # mappend :: RegEx token -> RegEx token -> RegEx token # mconcat :: [RegEx token] -> RegEx token #
Categorized token => Semigroup (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods (<>) :: RegEx token -> RegEx token -> RegEx token # sconcat :: NonEmpty (RegEx token) -> RegEx token # stimes :: Integral b => b -> RegEx token -> RegEx token #
Generic (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Associated Types type Rep (RegEx token) :: Type -> Type # Methods from :: RegEx token -> Rep (RegEx token) x # to :: Rep (RegEx token) x -> RegEx token #
(Categorized token, Read token, Read (Categorize token)) => Read (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods readsPrec :: Int -> ReadS (RegEx token) # readList :: ReadS [RegEx token] # readPrec :: ReadPrec (RegEx token) # readListPrec :: ReadPrec [RegEx token] #
(Categorized token, Show token, Show (Categorize token)) => Show (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods showsPrec :: Int -> RegEx token -> ShowS # show :: RegEx token -> String # showList :: [RegEx token] -> ShowS #
Categorized token => KleeneStarAlgebra (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods starK :: RegEx token -> RegEx token Source # plusK :: RegEx token -> RegEx token Source # optK :: RegEx token -> RegEx token Source # (>\|<) :: RegEx token -> RegEx token -> RegEx token Source # zeroK :: RegEx token Source #
NonTerminalSymbol (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods nonTerminal :: String -> RegEx token Source #
Categorized token => Eq (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods (==) :: RegEx token -> RegEx token -> Bool # (/=) :: RegEx token -> RegEx token -> Bool #
Categorized token => Ord (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods compare :: RegEx token -> RegEx token -> Ordering # (<) :: RegEx token -> RegEx token -> Bool # (<=) :: RegEx token -> RegEx token -> Bool # (>) :: RegEx token -> RegEx token -> Bool # (>=) :: RegEx token -> RegEx token -> Bool # max :: RegEx token -> RegEx token -> RegEx token # min :: RegEx token -> RegEx token -> RegEx token #
(Categorized token, HasTrie token) => Matching [token] (Bnf (RegEx token)) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods (=~) :: [token] -> Bnf (RegEx token) -> Bool Source #
(Categorized token, HasTrie token) => Matching [token] (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.BackusNaur Methods (=~) :: [token] -> RegEx token -> Bool Source #
data (RegEx token) :->: b Source #
Instance details Defined in Control.Lens.Grammar.Kleene data (RegEx token) :->: b = RegExTrie { terminalTrie :: [token] :->: b nonTerminalTrie :: String :->: b sequenceTrie :: (RegEx token, RegEx token) :->: b alternateTrie :: (RegEx token, RegEx token) :->: b kleeneStarTrie :: RegEx token :->: b kleeneOptTrie :: RegEx token :->: b kleenePlusTrie :: RegEx token :->: b failTrie :: b passTrie :: b oneOfTrie :: [token] :->: b notOneOfTrie :: ([token], Either Int [Int]) :->: b }
type Rep (RegEx token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene type Rep (RegEx token) = D1 ('MetaData "RegEx" "Control.Lens.Grammar.Kleene" "distributors-0.3.0.0-inplace" 'False) ((C1 ('MetaCons "Terminal" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [token])) :+: (C1 ('MetaCons "NonTerminal" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 String)) :+: C1 ('MetaCons "Sequence" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (RegEx token)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (RegEx token))))) :+: ((C1 ('MetaCons "KleeneStar" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (RegEx token))) :+: C1 ('MetaCons "KleeneOpt" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (RegEx token)))) :+: (C1 ('MetaCons "KleenePlus" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (RegEx token))) :+: C1 ('MetaCons "RegExam" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (RegExam token (RegEx token)))))))

data RegExam token alg Source #

A component of both RegExpressions and TokenTests, so that the latter can be embedded in the former with tokenClass.

Constructors

Fail
Pass
OneOf (Set token)
NotOneOf (Set token) (CategoryTest token)
Alternate alg alg

Instances

Instances details

Generic1 (RegExam token :: Type -> Type) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Associated Types type Rep1 (RegExam token) :: k -> Type # Methods from1 :: forall (a :: k). RegExam token a -> Rep1 (RegExam token) a # to1 :: forall (a :: k). Rep1 (RegExam token) a -> RegExam token a #
Categorized token => Tokenized token (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods anyToken :: RegExam token alg Source # token :: token -> RegExam token alg Source # oneOf :: Foldable f => f token -> RegExam token alg Source # notOneOf :: Foldable f => f token -> RegExam token alg Source # asIn :: Categorize token -> RegExam token alg Source # notAsIn :: Categorize token -> RegExam token alg Source #
Foldable (RegExam token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods fold :: Monoid m => RegExam token m -> m # foldMap :: Monoid m => (a -> m) -> RegExam token a -> m # foldMap' :: Monoid m => (a -> m) -> RegExam token a -> m # foldr :: (a -> b -> b) -> b -> RegExam token a -> b # foldr' :: (a -> b -> b) -> b -> RegExam token a -> b # foldl :: (b -> a -> b) -> b -> RegExam token a -> b # foldl' :: (b -> a -> b) -> b -> RegExam token a -> b # foldr1 :: (a -> a -> a) -> RegExam token a -> a # foldl1 :: (a -> a -> a) -> RegExam token a -> a # toList :: RegExam token a -> [a] # null :: RegExam token a -> Bool # length :: RegExam token a -> Int # elem :: Eq a => a -> RegExam token a -> Bool # maximum :: Ord a => RegExam token a -> a # minimum :: Ord a => RegExam token a -> a # sum :: Num a => RegExam token a -> a # product :: Num a => RegExam token a -> a #
Traversable (RegExam token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods traverse :: Applicative f => (a -> f b) -> RegExam token a -> f (RegExam token b) # sequenceA :: Applicative f => RegExam token (f a) -> f (RegExam token a) # mapM :: Monad m => (a -> m b) -> RegExam token a -> m (RegExam token b) # sequence :: Monad m => RegExam token (m a) -> m (RegExam token a) #
Functor (RegExam token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods fmap :: (a -> b) -> RegExam token a -> RegExam token b # (<$) :: a -> RegExam token b -> RegExam token a #
Generic (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Associated Types type Rep (RegExam token alg) :: Type -> Type # Methods from :: RegExam token alg -> Rep (RegExam token alg) x # to :: Rep (RegExam token alg) x -> RegExam token alg #
(Categorized token, Read token, Read alg, Read (Categorize token)) => Read (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods readsPrec :: Int -> ReadS (RegExam token alg) # readList :: ReadS [RegExam token alg] # readPrec :: ReadPrec (RegExam token alg) # readListPrec :: ReadPrec [RegExam token alg] #
(Categorized token, Show token, Show alg, Show (Categorize token)) => Show (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods showsPrec :: Int -> RegExam token alg -> ShowS # show :: RegExam token alg -> String # showList :: [RegExam token alg] -> ShowS #
Categorized token => BooleanAlgebra (RegExam token (TokenTest token)) Source #
Instance details Defined in Control.Lens.Grammar.Boole Methods (>&&<) :: RegExam token (TokenTest token) -> RegExam token (TokenTest token) -> RegExam token (TokenTest token) Source # (>\|\|<) :: RegExam token (TokenTest token) -> RegExam token (TokenTest token) -> RegExam token (TokenTest token) Source # notB :: RegExam token (TokenTest token) -> RegExam token (TokenTest token) Source # fromBool :: Bool -> RegExam token (TokenTest token) Source #
(Categorized token, Eq alg) => Eq (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods (==) :: RegExam token alg -> RegExam token alg -> Bool # (/=) :: RegExam token alg -> RegExam token alg -> Bool #
(Categorized token, Ord alg) => Ord (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods compare :: RegExam token alg -> RegExam token alg -> Ordering # (<) :: RegExam token alg -> RegExam token alg -> Bool # (<=) :: RegExam token alg -> RegExam token alg -> Bool # (>) :: RegExam token alg -> RegExam token alg -> Bool # (>=) :: RegExam token alg -> RegExam token alg -> Bool # max :: RegExam token alg -> RegExam token alg -> RegExam token alg # min :: RegExam token alg -> RegExam token alg -> RegExam token alg #
type Rep1 (RegExam token :: Type -> Type) Source #
Instance details Defined in Control.Lens.Grammar.Kleene type Rep1 (RegExam token :: Type -> Type) = D1 ('MetaData "RegExam" "Control.Lens.Grammar.Kleene" "distributors-0.3.0.0-inplace" 'False) ((C1 ('MetaCons "Fail" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Pass" 'PrefixI 'False) (U1 :: Type -> Type)) :+: (C1 ('MetaCons "OneOf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set token))) :+: (C1 ('MetaCons "NotOneOf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set token)) :: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (CategoryTest token))) :+: C1 ('MetaCons "Alternate" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1))))
type Rep (RegExam token alg) Source #
Instance details Defined in Control.Lens.Grammar.Kleene type Rep (RegExam token alg) = D1 ('MetaData "RegExam" "Control.Lens.Grammar.Kleene" "distributors-0.3.0.0-inplace" 'False) ((C1 ('MetaCons "Fail" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Pass" 'PrefixI 'False) (U1 :: Type -> Type)) :+: (C1 ('MetaCons "OneOf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set token))) :+: (C1 ('MetaCons "NotOneOf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set token)) :: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (CategoryTest token))) :+: C1 ('MetaCons "Alternate" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 alg) :: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 alg)))))

data CategoryTest token Source #

CategoryTests for Categorized tokens.

Constructors

AsIn (Categorize token)
NotAsIn (Set (Categorize token))

Instances

Instances details

Generic (CategoryTest token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Associated Types type Rep (CategoryTest token) :: Type -> Type # Methods from :: CategoryTest token -> Rep (CategoryTest token) x # to :: Rep (CategoryTest token) x -> CategoryTest token #
(Categorized token, Read token, Read (Categorize token)) => Read (CategoryTest token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods readsPrec :: Int -> ReadS (CategoryTest token) # readList :: ReadS [CategoryTest token] # readPrec :: ReadPrec (CategoryTest token) # readListPrec :: ReadPrec [CategoryTest token] #
(Categorized token, Show token, Show (Categorize token)) => Show (CategoryTest token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods showsPrec :: Int -> CategoryTest token -> ShowS # show :: CategoryTest token -> String # showList :: [CategoryTest token] -> ShowS #
Categorized token => Eq (CategoryTest token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods (==) :: CategoryTest token -> CategoryTest token -> Bool # (/=) :: CategoryTest token -> CategoryTest token -> Bool #
Categorized token => Ord (CategoryTest token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene Methods compare :: CategoryTest token -> CategoryTest token -> Ordering # (<) :: CategoryTest token -> CategoryTest token -> Bool # (<=) :: CategoryTest token -> CategoryTest token -> Bool # (>) :: CategoryTest token -> CategoryTest token -> Bool # (>=) :: CategoryTest token -> CategoryTest token -> Bool # max :: CategoryTest token -> CategoryTest token -> CategoryTest token # min :: CategoryTest token -> CategoryTest token -> CategoryTest token #
type Rep (CategoryTest token) Source #
Instance details Defined in Control.Lens.Grammar.Kleene type Rep (CategoryTest token) = D1 ('MetaData "CategoryTest" "Control.Lens.Grammar.Kleene" "distributors-0.3.0.0-inplace" 'False) (C1 ('MetaCons "AsIn" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Categorize token))) :+: C1 ('MetaCons "NotAsIn" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Set (Categorize token)))))