module Rip where

----------------------------------------------------------
-- Algebraic types for Regular Expressions, DFAs and GNFAs
----------------------------------------------------------

data RE a = Null | Epsi | Lit a | Or (RE a) (RE a) | Cat (RE a) (RE a) | Star (RE a)

data DFA  s a = DFA  [s] [a] (s -> a -> s) s [s]

data GNFA s a = GNFA [s] [a] (Maybe s -> Maybe s -> RE a)


-- a function to rip a GNFA into an RE, based on 1-step helper function
-- (note that rip1 is not quite a fold, but it is a "paramorphism")

rip (GNFA ss _ d) = rip1 d (map Just ss)

rip1 d [] = d Nothing Nothing
rip1 d (s:ss) = rip1 d' ss
                where d' u v = elim (d u v) (d u s) (d s s) (d s v)
                      elim r s t v = r `Or` (s `Cat` (Star t `Cat` v))


-- a function to "inject" a DFA into an initial GNFA
-- (Nothings represents new begin and end states)

d2g (DFA ss as d q0 f) = GNFA ss as d'
                         where d' Nothing  Nothing  = Null
                               d' Nothing  (Just s) = if s == q0    then Epsi else Null
                               d' (Just s) Nothing  = if s `elem` f then Epsi else Null
                               d' (Just s) (Just t) = foldl Or Null (map Lit [a | a <- as, d s a == t])


-- just for fun, how big are those REs computed as conversions?

size Null = 1
size Epsi = 1
size (Lit _) = 1
size (Or r s)  = 1 + size r + size s
size (Cat r s) = 1 + size r + size s
size (Star r)  = 1 + size r


-- a Show instance for REs, using Unicode (probably won't work in lecture ...)

instance Show a => Show (RE a) where
  show Null = "ø"							-- ("\195\184")
  show Epsi = "ε" 							-- ("\206\181")
  show (Lit a)   = chr a
  show (Or r s)  = inf "|" (show r) (show s)
  show (Cat r s) = inf "·" (show r) (show s)
  show (Star r)  = par (show r ++ "*")

chr c = [head (tail (show c))]
par str = "(" ++ str ++ ")"
inf x a b = par (a ++ x ++ b)


---------------------------------------
-- Some sample DFAs (from the homework)
---------------------------------------

sample1 = DFA [1..4] "ab" d 1 [1,4]
          where d 1 'a' = 2 ;  d 1 'b' = 3
                d 2 'a' = 2 ;  d 2 'b' = 4
                d 3 'a' = 3 ;  d 3 'b' = 3
                d 4 'a' = 2 ;  d 4 'b' = 4

sample2 = DFA [1..8] "ab" d 1 [2,4,5,7]
          where d 1 'a' = 5 ;  d 1 'b' = 2
                d 2 'a' = 4 ;  d 2 'b' = 3
                d 3 'a' = 4 ;  d 3 'b' = 3
                d 4 'a' = 8 ;  d 4 'b' = 8
                d 5 'a' = 6 ;  d 5 'b' = 7
                d 6 'a' = 6 ;  d 6 'b' = 7
                d 7 'a' = 8 ;  d 7 'b' = 8
                d 8 'a' = 8 ;  d 8 'b' = 8

sample3 = DFA [1..3] "ab" d 1 [1,3]
          where d 1 'a' = 2 ;  d 1 'b' = 3
                d 2 'a' = 2 ;  d 2 'b' = 3
                d 3 'a' = 3 ;  d 3 'b' = 2


-- ripping result REs from the samples

r1 = rip (d2g sample1)		-- ε | aa*b (b|aa*b)*
r2 = rip (d2g sample2)		-- b | ba | bbb*a | a | ab | aaa*b
							-- bb*a | a | aa*b | b
							-- b*a | a*b
r3 = rip (d2g sample3)		-- ε | (b|aa*b) (a|ba*b)*
                    		-- ε | a*b (a|ba*b)*



------------------------------------------
-- A (really messy) function to reduce REs
------------------------------------------


red r = case red1 r of Nothing -> r; Just s -> red s

red1 (Null `Cat` r) = Just Null
red1 (r `Cat` Null) = Just Null
red1 (Null `Or` r)  = Just (red r)
red1 (r `Or` Null)  = Just (red r)
red1 (Epsi `Cat` r) = Just (red r)
red1 (r `Cat` Epsi) = Just (red r)
red1 ((r `Or` s)  `Or`  t) = Just (red r `Or`  (red s `Or`  red t))
red1 ((r `Cat` s) `Cat` t) = Just (red r `Cat` (red s `Cat` red t))
red1 (Star Null) = Just Epsi
red1 (Star Epsi) = Just Epsi

red1 Null = Nothing
red1 Epsi = Nothing
red1 (Lit a) = Nothing

red1 (Or  r s) = case red1 r of 
                   Nothing -> case red1 s of 
                                Nothing -> Nothing
                                Just s' -> Just (Or r s')
                   Just r' -> Just (Or r' s)

red1 (Cat r s) = case red1 r of 
                   Nothing -> case red1 s of 
                                Nothing -> Nothing
                                Just s' -> Just (Cat r s')
                   Just r' -> Just (Cat r' s)

red1 (Star r)  = case red1 r of 
                   Nothing -> Nothing
                   Just r' -> Just (Star r')
                   
                   
-- red1 (r `Or` s) = if s < r then Just (s `Or` r) else Nothing
-- red1 (Epsi `Or` (r `Cat` Star s)) = if s == r then Just (Star r) else Nothing
-- red1 ((r `Cat` Star s) `Or` Epsi) = if s == r then Just (Star r) else Nothing