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

Dave Jenkins wrote:

"Kim Kuen Tang" wrote in message news:498587FA.4050404@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.

Right. Thanks Dave, you beat me to the punch again.

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

I trust your analysis, although I haven't had time to look deeply into it myself. I'll merely add that it appears as if Kim is recursively invoking his transform, whereas the purpose of the fold_tree and reverse_fold_tree transforms is to do the recursion for you in the common case that you're only interested in folding sub-trees that all have the same node type. The docs show how fold_tree is implemented in terms of fold: http://boost-sandbox.sourceforge.net/libs/proto/doc/html/boost/proto/fold_tr... My suggestion is to copy the implementation of fold_tree and modify it to do what you want by ignoring node type or whatever. HTH, -- Eric Niebler BoostPro Computing http://www.boostpro.com