diotalevi has asked for the wisdom of the Perl Monks concerning the following question:

I assume many of you are used to doing logic programming in perl but this is new to me. I wrote up a simple optree-recursing (this won't work in practice because of NULL nodes) expression which finds a given node in a tree and returns the path required to reach it. Is there a common way to write a more plausible implementation of $ROOT->(parent|sibling)* $target that doesn't require a regex to handle all the bookkeeping of tracking successes, failures and to-do work?

sub path_to_op
{
    my ( $root, $tgt ) = @_;

    local $op = $root;
    local @path;

    '' =~
        /(?:
            (?(?{ my $name = $op->oldname;
                  local $op = $op->parent;
                  local @path = ( @path, "$name/" ); })(?=)|(?!))
            |
            (?(?{ my $name = $op->oldname;
                  local $op = $op->sibling;
                  local @path = ( @path, "...," ); })(?=)|(?!))
         ) *

         (?(?{ $$op == $$tgt })(?=)|(?!)) /x;

    @path;
}

[download]

Replies are listed 'Best First'.
Re: Logic programming without using the RE engine as a crutch
by demerphq (Chancellor) on Jun 30, 2004 at 17:36 UTC

    Maybe im totally missing the point, but the following will traverse a tree composed of hashes and return the path. 

    sub path_to_op {
  my ($node,$tgt,$path)=@_;
  $path||='';
  return $path if $node==$tgt;
  
  foreach my $key (keys %$node) {
     my $path=path_to_op($node->{$key},$tgt,"$path{$key}");
     return $path if $path;    
  }
  return ''
}

    [download]

    But this seems so blindingly obvious to me that I'm having trouble believing I understand the question. After all I know you are very competent programmer so im at a loss to accept that I understand the question correctly....


    ---
    demerphq

      First they ignore you, then they laugh at you, then they fight you, then you win.
      -- Gandhi
[reply]
[d/l]
      Oh uh. Yeah. Heh.
[reply]

        Sounds like you got yourself stuck in something that I believe psychologistics call "functional fixidity" you were preconditioned (probably by reading too many nodes by abigail-ii ;-) that you forgot that tree traversal is a simple thing.

        Anyway I offer this little perspective to maybe help you avoid such things in the future. You can metally model most perl regexes as representing a tree, a tree whose job is to see if there is a path in a given string that can traverse the tree to a legal "accepting" terminal node. So in a sense using a regex to find a path toa given node is almost the opposite of what you really want.

        BTW, this is only really true of an NFA based regex engine. A DFA based regex engine would traverse all the branches of the equivelent NFA engine simultaneously, arriving at the same point, but without ever backtracking.


        ---
        demerphq

          First they ignore you, then they laugh at you, then they fight you, then you win.
          -- Gandhi
[reply]
      http://search.cpan.org/search?m=all&q=prolog&s=1&n=50 Might help some.
[reply]
[reply]
Re: Logic programming without using the RE engine as a crutch
by Zaxo (Archbishop) on Jun 30, 2004 at 17:42 UTC

    The task doesn't seem too different from that done by File::Find or any other treewalking program.

    How about keeping partial solutions on a stack? Backtrack with pop, go forward with push. You could implement that with recursive calls and let the stack be local and mainly implicit in the return conditions.

    I don't know if that could be called functional programming. It is pretty much how functional languages work under the hood.

    After Compline,
    Zaxo

[reply]

Back to Seekers of Perl Wisdom