Implementing a language in Haskell: homogenous lists

Question

I'm trying to create an interpreter for a functional language in haskell (I'm new to the language). I'm creating what's probably a weird mix of minimalism and convenience - no abstract data types, but I want to provide the ability to make homogeneous lists.

So my basic variables are data Datum = DatInt Int | DatDbl Double | DatBool Bool and I've realized I'm not at all sure how to represent homogeneous lists. Adding a constructor List Datum or something of the sort would make a heterogeneous list, and making a separate list for each type, i.e. ListInt [Int] | ListDbl [Double] would preclude lists of lists.

What would be the best way to go about representing a homogeneous list?

Answer 1

One useful notion (whether you're going for sexy types or not) is that of a type tag. The non-sexy version is a lot easier to deal with.

data Tag = IntTag
         | DoubleTag
         | BoolTag
         | ListTag Tag
   deriving (Eq, Show)

Now your types are represented by these various tags. An Int is represented by IntTag. A list of Int is represented by ListTag IntTag.

Now you can represent type-annotated expressions something like this:

data Expr = IntLit Int
          | DoubleLit Double
          | BoolLit Bool
          | ListLit Tag [Expr]

-- Check that an expression is validly annotated
typeCheck :: Expr -> Maybe Tag
typeCheck IntLit{} = Just IntTag
...
typeCheck (ListLit tag els)
  | all good els = Just (ListTag tag)
  | otherwise = Nothing
  where
    good el = case typeCheck el of
                Nothing -> False
                Just res = res == tag