-
Notifications
You must be signed in to change notification settings - Fork 0
/
Regex.hs
34 lines (28 loc) · 1.31 KB
/
Regex.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
module Regex where
import ToString
-- | 'Regex' is the type for regular expressions.
-- A Regex can be constructed as a literal alphabet symbol, the epsilon
-- symbol, the sum or the concatenation of two expressions, or the
-- Kleene star of a regular expression.
data Regex a = Literal a
| Epsilon
| Altern (Regex a) (Regex a)
| Concat (Regex a) (Regex a)
| Kleene (Regex a)
-- | 'Regex a' is an instance of Show if 'a' is.
instance (ToString a) => Show (Regex a) where
show (Literal x ) = toString x
show (Epsilon ) = "ε"
show (Altern x y) = "(" ++ toString x ++ "|" ++ toString y ++ ")"
show (Concat x y) = toString x ++ toString y
show (Kleene x ) = "(" ++ toString x ++ ")*"
-- | 'match' returns True if the alphabet string input is in the language
-- generated by the regular expression.
match :: (Eq a) => Regex a -> [a] -> Bool
match (Literal x) s = (s == [x])
match (Epsilon) s = (s == [])
match (Altern x y) s = (match x s)||(match y s)
match (Concat x y) s = or [(match x sa)&&(match y sb) | (sa,sb) <- partitions]
where partitions = [splitAt n s | n <- [0..length s]]
match (Kleene x) s = (match Epsilon s) || or [(match x sa)&&(match (Kleene x) sb) | (sa,sb) <- partitions]
where partitions = [splitAt n s | n <- [1..length s]]