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

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-20 10:18:57

On Mon, Oct 20, 2003 at 10:38:36AM -0400, David Abrahams wrote:
> Brian McNamara <lorgon_at_[hidden]> writes:
> > 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?
> 
> Isn't this very close to what you're doing?
> 
>      http://www.boost-consulting.com/boost/libs/variant/doc/sample.html#tree

Yes and no.  Yes, for obvious reasons.  No, because I'm not using a
struct to create the opportunity for a forward declaration to break
the recursion.

Try to rewrite that example with
   struct non_leaf_node { ... };
replaced by
   typedef tuple<int,tree_node,tree_node> non_leaf_node;
and you'll see the problem.

-- 
-Brian McNamara (lorgon_at_[hidden])