How do I restrict the types in a heterogenous list?

Question

I am currently trying to create a (sort of) typesafe xml like syntax embedded into Haskell. In the end I am hoping to achieve something like this:

tree = group [arg1 "str", arg2 42] 
         [item [foo, bar] []
         ,item [foo, bar] []
         ]

where group and item are of kind Node :: [Arg t] -> [Node c] -> Node t. If this doesn't make any sense it is most probably because I have no idea what I am doing :)

My question now is how to make the type system prevent me from giving 'wrong' arguments to a Node. Eg Nodes of type Group only may have arguments of type Arg1 and Arg2 but Items may have arguments of type Foo and Bar.

I guess the bottom line question is: how do i restrict the types in a heterogenous list?

---

Example of the (user) syntax i am trying to achieve:

group .: arg1 "str" .: arg2 42
    item .: foo .: bar
    item .: foo .: bar

where (.:) is a function that sets the parameter in the node. This would represent a group with some parameters containing two items.

Additionally there would be some (pseudo) definition like:

data Node = Node PossibleArguments PossibleChildNodes

type Group = Node [Arg1, Arg2] [Item]
type Item  = Node [Foo, Bar] []

I am searching for a way to catch usage errors by the typechecker.

Answer 1

Based on the ensuing discussion, it sounds like what you want is to create a DSL (Domain-Specific Language) to represent XML.

One option is to embed your DSL in Haskell so it can appear in Haskell source code. In general, you can do this by defining the types you need, and providing a set of functions to work with those types. It sounds like this is what you're hoping to do. However, as an embedded DSL, it will be subject to some constraints, and this is the problem you're encountering. Perhaps there is a clever trick to do what you want, maybe something involving type functions, but I can't think of anything at present. If you want to keep trying, maybe add the tags dsl and gadt to your question, catch the attention of people who know more about this stuff than I do. Alternatively, you might be able to use something like Template Haskell or Scrap Your Boilerplate to allow your users to omit some information, which would them be "filled in" before Haskell "sees" it.

Another option is to have an external DSL, which you parse using Haskell. You could define a DSL, but maybe it would be easier to just use XML directly with a suitable DTD. There are Haskell libraries for parsing XML, of course.

Answer 2

What you have doesn't sound to me like you need a heterogeneous list. Maybe you're looking for something like this?

data Foo = Foo Int

data Bar = Bar Int

data Arg = StringArg String | IntArg Int | DoubleArg Double

data Tree = Group Arg Arg [Item]

data Item = Item Foo Bar

example :: Tree
example = Group (StringArg "str") (IntArg 42)
            [Item (Foo 1) (Bar 2), Item (Foo 12) (Bar 36)]

Note that we could even create a list of Args of different "sub-types". For example, [StringArg "hello", IntArg 3, DoubleArg 12.0]. It would still be a homogeneous list, though.

===== EDIT =====

There are a few ways you could handle the "default argument" situation. Suppose the Bar argument in an item is optional. My first thought is that while it may be optional for the user to specify it, when I store the data I want to include the default argument. That way, determining a default is separated from the code that actually does something with it. So, if the user specifies a Foo of 3, but doesn't supply a Bar, and the default is Bar 77, then I create my item as:

Item (Foo 3) (Bar 77)

This has the advantage that functions that operate on this object don't need to worry about defaults; both parameters will always be present as far as they are concerned.

However, if you really want to omit the default arguments in your data structure, you could do somthing like this:

data Bar = Bar Int | DefaultBar

example = Group (StringArg "str") (IntArg 42)
            [Item (Foo 1) (Bar 2), Item (Foo 12) DefaultBar]

Or even:

data Item = Item Foo Bar | ItemWithDefaultBar Foo

===== Edit #2 =====

So perhaps you could use something like this:

data ComplicatedItem = ComplicatedItem 
    {
      location :: (Double, Double),
      size :: Int,
      rotation :: Double,
      . . . and so on . . .
    }

defaultComplicatedItem = ComplicatedItem { location = (0.0,0.0), size = 1, rotation = 0.0), ... }

To create a ComplicatedItem, the user only has to specify the non-default parameters:

myComplicatedItem = defaultComplicatedItem { size=3 }

If you add new paramters to the ComplicatedItem type, you need to update defaultComplicatedItem, but the definition for myComplicatedItem doesn't change.

You could also override the show function so that it omits the default parameters when printing.