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

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<
       ExprTreeLeaf
     , 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 http://tinyurl.com/rnue 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.)

Eric