[boost] Using tuple/variant for recursive algebraic datatypes?

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-20 05:10:36

Is it possible to use tuple/variant to define recursive algebraic
datatypes?  In Haskell I might say something like

   type Operand = String   -- e.g. "+" or "<<"
   data ExprTreeNode = ETN Operand ExprTree ExprTree 
   data ExprTreeLeaf = ETL Int
   type ExprTree = Either ExprTreeLeaf ExprTreeNode

If I try to translate this directly into C++, I might say

   typedef std::string Operand;
   typedef tuple<Operand,ExprTree*,ExprTree*> ExprTreeNode;
   typedef int ExprTreeLeaf;
   typedef variant<ExprTreeLeaf,ExprTreeNode> ExprTree;

except that this doesn't work, since we need to somehow forward-declare
that ExprTree is a typename or something.

Is there any way to do this?  Is there a good way to do this?

It kinda boils down to the same problem as this one:

   typedef std::pair< int, Cons* > Cons;   // oops, rats

which I've seen discussed before, but can't find good resolutions to.
My hunch is that there's no good way to do this unless C++ adds language
support (e.g. to forward-declare typedef typenames), but I'd be thrilled
if someone would prove me wrong.

(Offhand, the "best" solution I can think of is

   struct Cons : public std::pair< int, Cons* > {
      // replicate constructors
   };

which is just awful.)

-- 
-Brian McNamara (lorgon_at_[hidden])