-- $Id: RE.hs,v 1.1 1999/06/25 22:20:12 joe Exp $ --

module RE (
    RE(..), re_unit, re_zero, re_sym, re_rep, re_plus, re_opt, re_seq, re_alt,
    nullable, delta, matches
) where

re_unit, re_zero        :: RE a
re_sym                  :: a -> RE a
re_rep, re_plus, re_opt :: RE a -> RE a
re_seq, re_alt          :: RE a -> RE a -> RE a

data RE a =
      RE_ZERO                   -- L(0)   = {} (empty set)
    | RE_UNIT                   -- L(1)   = { [] } (empty sequence)
    | RE_SYM a                  -- L(x)   = { [x] }
    | RE_REP (RE a)             -- L(e*)  = { [] } `union` L(e+)
    | RE_PLUS (RE a)            -- L(e+)  = { x ++ y | x <- L(e), y <- L(e*) }
    | RE_OPT (RE a)             -- L(e?)  = L(e) `union` { [] }
    | RE_SEQ (RE a) (RE a)      -- L(e,f) = { x ++ y | x <- L(e), y <- L(f) }
    | RE_ALT (RE a) (RE a)      -- L(e|f) = L(e) `union` L(f)

-- Constructors:
--      These exploit operator identities to simplify regular expressions.
--
re_unit         = RE_UNIT
re_zero         = RE_ZERO
re_sym x        = RE_SYM x
re_rep RE_UNIT  = RE_UNIT
re_rep RE_ZERO  = RE_UNIT
re_rep e        = RE_REP e
re_plus RE_UNIT = RE_UNIT
re_plus RE_ZERO = RE_ZERO
re_plus e       = RE_PLUS e
re_opt RE_UNIT  = RE_UNIT
re_opt RE_ZERO  = RE_UNIT
re_opt e        = RE_OPT e

re_seq RE_ZERO f        = RE_ZERO
re_seq RE_UNIT f        = f
re_seq e RE_ZERO        = RE_ZERO
re_seq e RE_UNIT        = e
re_seq e f              = RE_SEQ e f
re_alt RE_ZERO f        = f
re_alt e RE_ZERO        = e
re_alt e f              = RE_ALT e f

-- nullable e == [] `in` L(e)
nullable                :: RE sym -> Bool
nullable RE_ZERO        = False
nullable RE_UNIT        = True
nullable (RE_SYM s)     = False
nullable (RE_REP e)     = True
nullable (RE_PLUS e)    = nullable e
nullable (RE_OPT e)     = True
nullable (RE_SEQ e f)   = nullable e && nullable f
nullable (RE_ALT e f)   = nullable e || nullable f

-- L(delta e x) = x \ L(e)
delta                   :: (Eq a) => RE a -> a -> RE a
delta re x = case re of
    RE_ZERO             -> re_zero
    RE_UNIT             -> re_zero
    RE_SYM sym
        | x == sym      -> re_unit
        | otherwise     -> re_zero
    RE_REP e            -> re_seq (delta e x) (re_rep e)
    RE_PLUS e           -> re_seq (delta e x) (re_rep e)
    RE_OPT e            -> delta e x
    RE_SEQ e f
        | nullable e    -> re_alt (re_seq (delta e x) f) (delta f x)
        | otherwise     -> re_seq (delta e x) f
    RE_ALT e f          -> re_alt (delta e x) (delta f x)

-- matches e s == s `in` L(e)
matches                 :: (Eq a) => RE a -> [a] -> Bool
matches e = nullable . foldl delta e

--*EOF*--