Wednesday, February 3, 2010

Binary Tree

So, while reading over #perl6 today, I noticed comments about how out-of-date Exegesis 2's first example was. Even the updates to it are out of date! I thought it would be fun and simple to update it to working modern Perl 6, as embodied in Rakudo master. (As ng has still not landed.)

Well, it seemed like a good idea when I started. However, I've run into an odd issue. Here's my simplified which doesn't work:

# bintree - binary tree demo program 
# adapted from "Perl Cookbook", Recipe 11.15
# converted to modern Perl 6 by SF
use v6;

my (%root, $n);
for (1..1000).pick(2) {
say "Inserting $_";
insert(%root, $_);
say %root.perl;
}

say %root.keys;
say "Doom";

#########################################
sub insert(Hash $tree is rw, Int $val) {
unless $tree {
my %node;
%node<LEFT> = Hash;
%node<RIGHT> = Hash;
%node<VALUE> = $val ; # but Found(0);
say %node.perl;
$tree = %node;
say $tree.perl;
return;
}
if ($tree<VALUE> > $val) { insert($tree<LEFT>, $val) }
elsif ($tree<VALUE> < $val) { insert($tree<RIGHT>, $val) }
else { warn "dup insert of $val\n" }
}


And here's sample output:

Inserting 640
{"VALUE" => 640, "RIGHT" => Hash, "LEFT" => Hash}
{"VALUE" => 640, "RIGHT" => Hash, "LEFT" => Hash}
{}
Inserting 461
{"VALUE" => 461, "RIGHT" => Hash, "LEFT" => Hash}
{"VALUE" => 461, "RIGHT" => Hash, "LEFT" => Hash}
{}

If you match that back up with the says in the code, you'll see that a value is assigned to $tree in insert, but that value does not make it back to the point where insert is called, despite $tree is rw. I've no idea why this should be the case, the same sort of code seems to work quite well in the REPL. Does anyone have an idea? Am I doing something stupid here, or did I just find a bug in a very-soon-to-be-obsolete version of Rakudo?

Update: Not sure if this is just something I don't understand or a rakudobug. It turns out that the problem is the line $tree = %node. If I use equals to assign something to $tree, that doesn't get passed back out. On the other hand, if I add hash keys directly to $tree, they are passed out just like I would expect.

3 comments:

  1. I believe it's because $tree starts as a reference to %root, but then becomes a reference to %node. That assignment won't alter %root at all.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. try 'sub insert( %tree is ref ' - note changed sigil and trait, as well as lack of type qualifier. The % sigil adds an automatic 'where { * ~~ Associative }'

    ReplyDelete