LanX:
On rereading this thread, I think you may misunderstand what my code is doing. When you said that my code wasn't "lazy", I thought you meant that it was working too hard, but in retrospect I think you're meaning that I'm flattening the entire tree at once before returning anything.
But I'm not doing that--Instead, I'm properly visiting the tree, traversing the left subtree(s) until I find the first (leftmost) leaf. The unused right subtrees are left on the stack for processing later.
Since my test data was small and the tree left-heavy, though, it's hard to see that. Below (in readmore tags for those uninterested) is a run of the original iterator that you instrumented with a more "interesting" tree. I also have the output of my better version (also instrumented):
$ perl fringe.pl --- [[1, [[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]]]] [1, [[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]]] leaf: 1 --- [[[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]]] [[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]] [2, 3, [4, [[[5, 6], [7, 8]], [9, 10]]]] leaf: 2 --- [3, [4, [[[5, 6], [7, 8]], [9, 10]]]] leaf: 3 --- [[4, [[[5, 6], [7, 8]], [9, 10]]]] [4, [[[5, 6], [7, 8]], [9, 10]]] leaf: 4 --- [[[[5, 6], [7, 8]], [9, 10]]] [[[5, 6], [7, 8]], [9, 10]] [[5, 6], [7, 8], [9, 10]] [5, 6, [7, 8], [9, 10]] leaf: 5 --- [6, [7, 8], [9, 10]] leaf: 6 --- [[7, 8], [9, 10]] [7, 8, [9, 10]] leaf: 7 --- [8, [9, 10]] leaf: 8 --- [[9, 10]] [9, 10] leaf: 9 --- [10] leaf: 10 --- []
Here's the outout of my better algorithm with the _explicit instrumentation version (I added a dump inside the while loops), so you can more easily see it making the decisions:
$ perl fringe.pl --- tree: [1, [[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]]] rtrees: [] traverse L tree: 1 rtrees: [[[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]]] leaf: 1 --- tree: [[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]] rtrees: [] traverse L tree: [2, 3] rtrees: [[4, [[[5, 6], [7, 8]], [9, 10]]]] traverse L tree: 2 rtrees: [[4, [[[5, 6], [7, 8]], [9, 10]]], 3] leaf: 2 --- tree: 3 rtrees: [[4, [[[5, 6], [7, 8]], [9, 10]]]] leaf: 3 --- tree: [4, [[[5, 6], [7, 8]], [9, 10]]] rtrees: [] traverse L tree: 4 rtrees: [[[[5, 6], [7, 8]], [9, 10]]] leaf: 4 --- tree: [[[5, 6], [7, 8]], [9, 10]] rtrees: [] traverse L tree: [[5, 6], [7, 8]] rtrees: [[9, 10]] traverse L tree: [5, 6] rtrees: [[9, 10], [7, 8]] traverse L tree: 5 rtrees: [[9, 10], [7, 8], 6] leaf: 5 --- tree: 6 rtrees: [[9, 10], [7, 8]] leaf: 6 --- tree: [7, 8] rtrees: [[9, 10]] traverse L tree: 7 rtrees: [[9, 10], 8] leaf: 7 --- tree: 8 rtrees: [[9, 10]] leaf: 8 --- tree: [9, 10] rtrees: [] traverse L tree: 9 rtrees: [10] leaf: 9 --- tree: 10 rtrees: [] leaf: 10 --- tree: undef rtrees: []
The code:
#!/usr/bin/perl use strict; use Data::Dump 'dd'; my $tree = [ 1, [[2, 3], [4, [[[5, 6], [7, 8]], [9, 10]]]] ]; #my $T = get_tree_iterator($tree); #my $T = get_tree_iterator_explicit($tree); #my $T = get_tree_iterator_2($tree); my $T = get_tree_iterator_2_explicit($tree); while (my $leaf = $T->()) { print "leaf: $leaf\n"; } sub get_tree_iterator { my @stack = (shift); return sub { print "---\n"; dd \@stack; while (@stack and ref $stack[0] eq 'ARRAY') { unshift @stack, @{shift @stack}; dd \@stack } return shift @stack; } } sub get_tree_iterator_explicit { my @stack = (shift); return sub { print "---\n"; dd \@stack; while (@stack and ref $stack[0] eq 'ARRAY') { print " split tree into left & right\n"; unshift @stack, @{shift @stack}; dd \@stack } return shift @stack; } } sub get_tree_iterator_2 { my @rtrees = (shift); my $tree; return sub { $tree = pop @rtrees; print "---\n"; print "tree: "; dd $tree; print "rtrees: "; dd \@rtrees; ($tree, $rtrees[@rtrees]) = @$tree while ref $tree; return $tree; } } sub get_tree_iterator_2_explicit { my @rtrees = (shift); my $tree; return sub { $tree = pop @rtrees; print "---\n"; print "tree: "; dd $tree; print "rtrees: "; dd \@rtrees; while (ref $tree) { print "traverse L\n"; ($tree, $rtrees[@rtrees]) = @$tree; print " tree: "; dd $tree; print " rtrees: "; dd \@rtrees; } return $tree; } }
...roboticus
When your only tool is a hammer, all problems look like your thumb.
In reply to Re^3: Challenge: Perl 5: lazy sameFinge()?
by roboticus
in thread Challenge: Perl 5: lazy sameFringe()?
by BrowserUk
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |