Thursday, February 11, 2010

Binary Tree Complete

masak responded to my last post with a very nice post and script of his own. His code implemented the two features I left out from the original, and added several other very nice touches. I've updated my own script, stealing liberally from his and adding a few wrinkles of my own. I think this is about as far as a script which tries to stick pretty close to the original can go -- but then, I think there is still a lot of room for improvement by moving away from the original and fully embracing Perl 6.

So here's my new script. (Apologies for not posting it in-line here, but something in it breaks my copy of Syntax::Highlight::Perl6 and I don't have time to sort out how to fix it.) A quick overview of the changes:

1. I've incorporated masak's role Found verbatim. This implements a big piece of the functionality of the original that I left out in my previous attempt. (Personally, I think this is a rather silly use of roles, but that's not masak's fault, he's just matching the original script here.)

2. I tried to take masak's revamped show function to its logical conclusion. He changed it to return nodes in the iteration with take, so that you have to call gather before calling it. To my taste this combines brilliance with wrongness. I took his code, reversed his left and right so things came out in the right order, renamed show to traverse, and -- here is the key, IMO -- created a new function, collect which does gather and then calls traverse. I think this is going to be a really common idiom for iterating over recursive data structures in Perl 6.

3. That has the side effect of making printing the tree very elegant: say "Pre order: { collect(%root, pre-order) }";.

4. I grabbed masak's use of prompt verbatim, too. What a nifty little function!

5. I added a say at the end of the loop, so you get a proper newline and message indicating that the program has ended successfully.

6. I switch to %tree throughout, at masak's suggestion, and also switched to {}. masak++

I think next I'll take a stab at rewriting this using a class instead of a hash. And I see there has been crazy progress on ng lately, so with any luck it will be ready to handle the ABC project after that...


  1. You know, this was fun. How about independently doing E03 in the same way? Maybe even set at day and both post on that day, without looking at the other person's solution?

  2. That sounds like a lovely plan. Say a week from today? One or both of us should post the "challenge" and invite others to join in.

    Errr, though, I just glanced at E03 and I don't know how much of that stuff works in Rakudo, much less ng (which will be master next week, right?). What do you think?

  3. Week from today is fine by me.

    I haven't looked in detail at how supported E03 is in Rakudo, but how about letting that be a part of the challenge? Asking questions on #perl6 and p6u during the week about what Rakudo implements, is of course permitted.

    Since ng is so volatile right now, it feels difficult to know whether to do it in one branch or the other. I'll probably try both, and likely find that ng still misses one or a few features that work in master.

  4. Greetings! I was just reading your source.... is your pre-order and post-order backwards? In your pre-order, if I know how to read this, you traverse the left, right, and then take the value. Shouldn't it be the other way around?