How do I use Haskell's type system to enforce correctness while still being able to pattern-match?

Question

Let's say that I have an adt representing some kind of tree structure:

data Tree = ANode (Maybe Tree) (Maybe Tree) AValType
          | BNode (Maybe Tree) (Maybe Tree) BValType
          | CNode (Maybe Tree) (Maybe Tree) CValType

As far as I know there's no way of pattern matching against type constructors (or the matching functions itself wouldn't have a type?) but I'd still like to use the compile-time type system to eliminate the possibility of returning or parsing the wrong 'type' of Tree node. For example, it might be that CNode's can only be parents to ANodes. I might have

parseANode :: Parser (Maybe Tree)

as a Parsec parsing function that get's used as part of my CNode parser:

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \maybeanodel ->
                  parseANode >>= \maybeanoder ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode maybeanodel maybeanoder cval))
             ) <|> return Nothing

According to the type system, parseANode could end up returning a Maybe CNode, a Maybe BNode, or a Maybe ANode, but I really want to make sure that it only returns a Maybe ANode. Note that this isn't a schema-value of data or runtime-check that I want to do - I'm actually just trying to check the validity of the parser that I've written for a particular tree schema. IOW, I'm not trying to check parsed data for schema-correctness, what I'm really trying to do is check my parser for schema correctness - I'd just like to make sure that I don't botch-up parseANode someday to return something other than an ANode value.

I was hoping that maybe if I matched against the value constructor in the bind variable, that the type-inferencing would figure out what I meant:

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \(Maybe (ANode left right avall)) ->
                  parseANode >>= \(Maybe (ANode left right avalr)) ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode (Maybe (ANode left right avall)) (Maybe (ANode left right avalr)) cval))
             ) <|> return Nothing

But this has a lot of problems, not the least of which that parseANode is no longer free to return Nothing. And it doesn't work anyways - it looks like that bind variable is treated as a pattern match and the runtime complains about non-exhaustive pattern matching when parseANode either returns Nothing or Maybe BNode or something.

I could do something along these lines:

data ANode = ANode (Maybe BNode) (Maybe BNode) AValType
data BNode = BNode (Maybe CNode) (Maybe CNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

but that kind of sucks because it assumes that the constraint is applied to all nodes - I might not be interested in doing that - indeed it might just be CNodes that can only be parenting ANodes. So I guess I could do this:

data AnyNode = AnyANode ANode | AnyBNode BNode | AnyCNode CNode

data ANode = ANode (Maybe AnyNode) (Maybe AnyNode) AValType
data BNode = BNode (Maybe AnyNode) (Maybe AnyNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

but then this makes it much harder to pattern-match against *Node's - in fact it's impossible because they're just completely distinct types. I could make a typeclass wherever I wanted to pattern-match I guess

class Node t where
    matchingFunc :: t -> Bool

instance Node ANode where
    matchingFunc (ANode left right val) = testA val

instance Node BNode where
    matchingFunc (BNode left right val) = val == refBVal

instance Node CNode where
    matchingFunc (CNode left right val) = doSomethingWithACValAndReturnABool val

At any rate, this just seems kind of messy. Can anyone think of a more succinct way of doing this?

Answer 1

I'd still like to use the compile-time type system to eliminate the possibility of returning or parsing the wrong 'type' of Tree node

This sounds like a use case for GADTs.

{-# LANGUAGE GADTs, EmptyDataDecls #-}
data ATag
data BTag
data CTag

data Tree t where
  ANode :: Maybe (Tree t) -> Maybe (Tree t) -> AValType -> Tree ATag
  BNode :: Maybe (Tree t) -> Maybe (Tree t) -> BValType -> Tree BTag
  CNode :: Maybe (Tree t) -> Maybe (Tree t) -> CValType -> Tree CTag

Now you can use Tree t when you don't care about the node type, or Tree ATag when you do.

Answer 2

I don't understand your objection to your final solution. You can still pattern match against AnyNodes, like this:

f (AnyANode (ANode x y z)) = ...

It's a little more verbose, but I think it has the engineering properties you want.