Laurent_R:

Don't worry about it, post your solution--One of the fun things about programming is seeing how other people do things, and then learning their techniques! Not only that someone might offer a suggestion to you that could lead in a different and better direction. As LanX mentioned, mine's computationally expensive. That's not a real problem in this case. But if someone needed to compute as many fringes per second as possible, then a faster solution would be helpful. I can't help but feel that there's an even nicer way to do it, but I haven't thought of it yet.

Also, the code above wasn't my first shot at it. It was an interesting problem, so I spent a bit of time on it. I went through six iterations to get it as simple as it is now. Once I had some functional code, I thought that there was just too much special-case handling code. So I tried to rearrange things to remove the special cases. It's pretty simple in the final version, but I didn't see the simple version at first--I seem to have a habit of seeing the trees before noticing the forest.

It took me six iterations to get to the version I posted. My first version was this:

sub tree_iterator {
    return undef unless @stack;
    my $tos = pop @stack;
    return $tos unless ref $tos eq 'ARRAY';
    my ($L, $R) = @$tos;
    print "ENTER ($L, $R)\n";
    while (1) {
        print "LOOP: ($L, $R)\n";
        push @stack, $R if defined $R;
        if (defined $L) {
            return $L if ref $L ne 'ARRAY';
            ($L, $R) = @$L;
            redo;
        }
        else {
            ($L, $R) = @{pop @stack};
        }
    }
}
[download]

(This is before I wrapped up the stack in a closure to make the iterator useful.) As you can see, there are just too many special cases in there. Each time I removed one special case, it gave me an idea for the next one. I'm pretty happy with the version I ultimately wound up with, even though I suspect that it could be better yet. It would be pretty nice if I could think up a nice simple way to do it and reduce the array rebuilds, too. I tried to switch back to the push/pop, as I think that would be more efficient, but most of the special cases were due to my use of push/pop at the start. Switching to shift/unshift allowed me to remove one or two odd bits.

I think I have a rosetta code login at work, so I'll try to remember to post it there on Monday.

And, even though IT managers usually don't really understand the difference, they do if you tell them: "well this I can do in two weeks with XYZ super-duper object language , and in 2 days in Perl or Haskel (or Lisp, or whatever).

I wish the people at $work were susceptible to that argument. I used this very argument at work the other day. They needed a file generated, so I quoted a day in Perl or a week in .Net or PL/SQL. Also, I mentioned that due to time pressures on the current project, I could just squeeze the Perl version into my schedule. There's little Perl expertise at $work, and they're fearful enough of it, that they opted to do it in PL/SQL. 10 days later and it works. Luckily, due to the time pressures, *I* didn't have to do the task. But I'm frequently surprised when it's "rush rush rush!" but when you want to do it with a tool they're uncomfortable with, saving all the time in the world wouldn't be enough for them. ...sigh...

...roboticus

When your only tool is a hammer, all problems look like your thumb.