{-# LANGUAGE FlexibleInstances, FlexibleContexts #-}
module RegExp where

import Auxfuns(plistf,comp)
import qualified Data.Set as DS
import Data.List(sortBy)

----------------------------------------------------


data RegExp a
  = Lambda                         -- the empty string ""
  | Empty                          -- the empty set
  | One a                          -- a singleton set {a}
  | Union (RegExp a) (RegExp a)    -- union of two RegExp
  | Cat (RegExp a) (RegExp a)      -- Concatenation
  | Star (RegExp a)                -- Kleene closure

-- extract an "nth" aproximation of the set denoted 

meaning:: Ord a => Int -> (RegExp a) -> Set [a]
meaning n (One x) = one x
meaning n Lambda = lam
meaning n Empty = empty
meaning n (Union x y) = union (meaning n x) (meaning n y)
meaning n (Cat x y) = cat (meaning n x) (meaning n y)
meaning n (Star x) = starN n (meaning n x)

printSetSize = 100::Int
starLimit = 4::Int

------------------------------------------------------
-- Operations creating Regular languages

one x = Set(DS.insert [x] DS.empty)

lam:: Ord a => Set [a]
lam = Set(DS.insert [] DS.empty)

empty = Set DS.empty

union (Set x) (Set y) = Set(DS.union x y)

cat (Set xs) (Set ys) = 
   Set (DS.fromList [ x++y | x <- DS.toList xs, y <- DS.toList ys])

starN 0 x = lam
starN 1 x = union lam x
starN n x = union lam (union x (cat x (starN (n-1) x)))
star x = starN starLimit x

setElem x (Set s) = elem x (DS.toList s)
-------------------------------------------------------------------------
-- Sets 
newtype Set s = Set (DS.Set s)

instance Show (Set String) where
  show x = showN printSetSize x

showN n (Set xs) = plistf show "{" (take n (sortBy comp (DS.toList xs))) "," "}"

instance Eq s => Eq (Set s) where
  (Set x) == (Set y) = x==y