Boost logo

Boost :

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-10-20 17:45:35

Brian McNamara wrote:

> 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?

How about this:

   typedef std::string Operand;
   typedef int ExprTreeLeaf;

   typedef recursive_variant<
     , tuple< Operand, recursive_variant_*, recursive_variant_* >
>::type ExprTree;

   typedef tuple< Operand, ExprTree*, ExprTree* > ExprTreeNode;

[You actually don't need pointers- I'm just trying to mirror your code.]

Unfortunately, I haven't yet provided reference documentation for
recursive_variant. (But do see for a tutorial on
its use.)

> 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.

Yes, the recursive_variant solution is a bit of a hack. Hopefully it
works for you. (I'd appreciate feedback on your success with it.)


Boost list run by bdawes at, gregod at, cpdaniel at, john at