plus
:: RE a > RE a
We can extend the language of regular expressions by standard abstractions. 
sem
:: RE a > [a]
The semantics of regular expressions can be defined as a nondeterministic operation associating any word of the language defined by the regular expression: 
match
:: Data a => RE a > [a] > Bool
An operation to match a string against a regular expression can be defined by the following constraint: 
grep
:: Data a => RE a > [a] > Bool

grepShow
:: Data a => RE a > [a] > [a]
The following operation extends the operation grep to return the substring which starts with the regular expression. 
grepPos
:: Data a => RE a > [a] > Int
The following operation extends the operation grep to return the position where the matched regular expression starts. 
A data type to represent regular expression over some alphabet. A regular expression is either a literal, i.e., a member of the alphabet, an choice between two regular expressions, the concatenation of two regular expressions, or the repetition of a regular expression.
Constructors:
Lit
:: a > RE a
Alt
:: (RE a) > (RE a) > RE a
Conc
:: (RE a) > (RE a) > RE a
Star
:: (RE a) > RE a
We can extend the language of regular expressions by standard abstractions. Here we introduce an operator denoting at least one or more repetitions of a regular expression:

The semantics of regular expressions can be defined as a nondeterministic operation associating any word of the language defined by the regular expression:

An operation to match a string against a regular expression can be defined by the following constraint: 