regex-deriv-0.0.3: Replaces/Enhances Text.Regex. Implementing regular expression matching using Bzozoski's Deriviative

Safe HaskellSafe-Inferred



This module defines the data type of internal regular expression pattern, | as well as the partial derivative operations for regular expression patterns.



data Pat Source

regular expression patterns


PVar Int [Range] Pat

variable pattern


pattern without binder

PPair Pat Pat

pair pattern

PChoice [Pat] GFlag

choice pattern

PStar Pat GFlag

star pattern

PPlus Pat Pat

plus pattern, it is used internally to indicate that it is unrolled from a PStar

PEmpty Pat

empty pattern, it is used intermally to indicate that mkEmpty function has been applied.


Eq Pat

The Eq instance for Pat data type NOTE: We ignore the 'consumed word' when comparing patterns (ie we only compare the pattern structure). Essential for later comparisons among patterns.

Ord Pat 
Show Pat 
Key Pat 
Pretty Pat 
IsGreedy Pat

Function isGreedy checks whether a pattern is greedy

Simplifiable Pat

mainly interested in simplifying epsilon, p --> p could be made more optimal, e.g. (epsilon, epsilon) --> epsilon

IsPhi Pat 
IsEpsilon Pat 

strip :: Pat -> RESource

function strip strips away the bindings from a pattern

type Binder = IntMap [Range]Source

The Binder type denotes a set of (pattern var * range) pairs type Binder = [(Int, [Range])]

toBinder :: Pat -> BinderSource

Function toBinder turns a pattern into a binder

class Key a whereSource


hash :: a -> [Int]Source


Key Char 
Key Int 
Key RE 
Key Pat 
Key a => Key [a] 
(Key a, Key b) => Key (a, b) 
(Key a, Key b, Key c) => Key (a, b, c)