regex-size.hs

-- THIS CODE IS COMPLETELY WRONG

import qualified Data.List as List

data Regex = Class [Char]   -- character class
           | Seq [Regex]    -- sequence, ABC
           | Choice [Regex] -- choice, A|B|C
           | Star Regex     -- zero or more, A*
             deriving (Show)

data Size = Finite Int | Infinite deriving (Show, Eq)

instance Num Size where
  abs = undefined; signum = undefined; negate = undefined -- unnecessary
  fromInteger = Finite . fromInteger
  Finite x + Finite y = Finite (x + y)
  _ + _ = Infinite
  Finite x * Finite y = Finite (x * y)
  x * y = if x == 0 || y == 0 then 0 else Infinite

-- computes size & language (list of matching strings, if regex is finite)
eval :: Regex -> (Size, [String])
eval (Class chars) = (Finite (length cset), [[c] | c <- cset])
  where cset = List.nub chars
eval (Seq regexes) = (product sizes, concat <$> sequence langs)
  where (sizes, langs) = unzip $ map eval regexes
eval (Choice regexes) = (size, lang)
  where (sizes, langs) = unzip $ map eval regexes
        lang = concat langs
        size = if elem Infinite sizes then Infinite
               -- finite, so just count 'em. inefficient but works.
               else Finite (length (List.nub lang))
eval (Star r) = (size, lang)
  where (rsize, rlang) = eval r
        size | rsize == 0 = 1
             | rsize == 1 && List.nub rlang == [""] = 1
             | otherwise = Infinite
        lang = [""] ++ ((++) <$> [x | x <- rlang, x /= ""] <*> lang)

size :: Regex -> Size
size = fst . eval