to overload a data type or to use a similar one?

Question

This is more of a question about a programming style and common practices. But I feel that it does not fit into the code review forum...

My program parses regular expressions and processes them. A regular expression can have the usual elements (Kleene closure, concatenation, etc) and it also can have references to other regular expressions by their names, like macros:

data Regex a = Epsilon
             | Literal a
             | Ranges [(a, a)]
             | Ref String
             | Then (Regex a) (Regex a)
             | Or (Regex a) (Regex a)
             | Star (Regex a)

After I process a regular expression and resolve all macro references, and convert Literal elements to Range elements (this is needed for my purposes), I end up with a type that cannot and must not have Ref and Literal, so in my functions that work with it I do something like:

foo (Literal _) = error "unexpected literal"
foo (Ref _)     = error "unexpected reference"
foo (Epsilon)   = ...
foo (Star x)    = ...
...

This looks ugly to me because it does runtime checks instead of checks during compilation. Not a very haskell kind of approach.

So maybe I can introduce another data type which is very similar to the original one and use that?

data RegexSimple a = Epsilon2
                   | Ranges2 [(a, a)]
                   | Then2 (Regex a) (Regex a)
                   | Or2 (Regex a) (Regex a)
                   | Star2 (Regex a)

That would work, but here I have a lot of duplication and also the nice and descriptive names of constructors are taken now and I need to invent new ones...

What would the experts do here? I want to learn : )

Answer 1

I don't know what the rest of your code looks like, so this solution may require you to rethink certain aspects, but the most "haskell-ish" solution to this problem would probably be to use GADTs and phantom types. Together, they basically allow you to create arbitrary subtypes for more flexible type safety. You would redefine your types like so.

{-# LANGUAGE GADTs #-}

data Literal
data Ref
data Rangeable

data Regex t a where
         Epsilon :: Regex Rangeable a
         Literal :: a -> Regex Literal a
         Ranges  :: [(a, a)] -> Regex Rangeable a
         Ref     :: String -> Regex Ref a
         Then    :: Regex t' a -> Regex t' a -> Regex Rangeable a
         Or      :: Regex t' a -> Regex t' a -> Regex Rangeable a
         Star    :: Regex t' a -> Regex Rangeable

Then you can define

foo :: Regex Rangeable a
foo (Epsilon)  = ...
foo s@(Star a) = ...

Now, statements like foo $ Literal 'c' will fail compile-time type-checks.