Re: [Boost-users] [Proto] proto::reverse_fold_tree

Subject: Re: [Boost-users] [Proto] proto::reverse_fold_tree
From: Dave Jenkins (david_at_[hidden])
Date: 2009-02-02 13:25:42

"Kim Kuen Tang" <kuentang_at_[hidden]> wrote in message 
news:498587FA.4050404_at_vodafone.de...
> Hi all,
>
> i want to use the function proto::reverse_fold_tree to build a 
> heterogeneous list from the expression "((a*b+c)*d+e)*f". The resulting 
> sequence only contains the two terminals 'a' and b'. So  i am a little bit 
> confused.
>
> But using the function proto::fold_tree it produces correctly the sequence 
> [f,e,d,c,b,a]. (Btw the two functions proto::fold_tree and proto::fold 
> produce the same sequence [f,e,d,c,b,a], what is their difference? )

Hi Kim,

I think the basic problem is that fold_tree and reverse_fold_tree expect
the child nodes type to be the same in the flattened sequence.
Your expression "((a*b+c)*d+e)*f" is mixing plus nodes and multiply nodes.

To show why fold_tree appears to work and reverse_fold_tree doesn't,
consider the expression "a*b+c".
With fold_tree it produces the correct sequence [c b a],
but reverse_fold_tree produces the incorrect sequence [a b].

What's happening is FoldToListReverse processes the children
of plus<> in reverse order, so it first pushes "c" on the sequence.
Then it sees the <multiply> node and gets a mismatch against
the original plus<> tag,
So, it recursively calls FoldToListReverse.
This clears the sequence to nil (throwing away "c").
Then it flattens multiply<a,b> and pushes "a b" on the sequence,
which is what you see displayed.

With FoldToList, it appears to work because it processes the children
of plus<> in forward order.
So it immediately recursively calls FoldToList because
the tags <plus> and <multiply> tags don't match.
But at this point, clearing the sequence doesn't matter.
It processes multiply<a,b>, pushing them on the sequence.
Then it returns and pushes "c" on the sequence.  That's why it appears to 
work.

You can see that both are broken if you try the expression 
"(a*b+c)*(do*e+f)".
That displays [f e d] for reverse_fold_tree and [a b] for fold_tree.

Regards,
Dave Jenkins