Инкапсуляция рекурсивной функции в Perl - PullRequest
Новая
       28

Инкапсуляция рекурсивной функции в Perl

1 голос
/ 01 ноября 2010

У меня есть код, который хорошо работает здесь: 

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;



        my %graph =(
            F => ['B','C','E'],
            A => ['B','C'],
            D => ['B'],
            C => ['A','E','F'],
            E => ['C','F'],
            B => ['A','E','F']
        );

        sub findPaths {
            my( $seen,  $start, $end ) = @_;

            return [[$end]] if $start eq $end;

            $seen->{ $start } = 1;
            my @paths;
            for my $node ( @{ $graph{ $start } } ) {
                my %seen = %{$seen};
                next if exists $seen{ $node };
                push @paths, [ $start, @$_ ] for @{ findPaths( \%seen, $node, $end ) };
            }
            return \@paths;
        }


            my $start = "B";
            my $end   = "E";
        print "@$_\n" for @{ findPaths( {}, $start, $end ) };

Что я хочу сделать - это создать более общую подпрограмму так что он просто принимает \%graph, $start,$end в качестве входных данных и возвращает окончательный массив.

Я пытался сделать это таким образом, но он не компилируется. 

sub findPathsAll {

    my ($graph,$start,$end) = @_;

    my $findPaths_sub;
        $findPaths_sub {
            my( $seen) = @_;

            return [[$end]] if $start eq $end;

            $seen->{ $start } = 1;
            my @paths;
            for my $node ( @{ $graph{ $start } } ) {
                my %seen = %{$seen};
                next if exists $seen{ $node };
                push @paths, [ $start, @$_ ] for @{ &$findPaths_sub( \%seen, $node, $end ) };
            }
            return \@paths;
        }


    my @all;
    push @all,@$_ for @{ &$findPaths_sub( {}, $start, $end ) };
    return @all;
}

Какой правильный способ сделать это?

Ответы [ 2 ]

4 голосов
/ 01 ноября 2010

Я не могу понять, что вы хотите findPathsAll вернуть, так что это может быть не совсем то, что вы хотите. В любом случае, вот перевод findPaths в лексический рекурсивный код: 

use Scalar::Util 'weaken';

sub findPathsAll {
  my ($graph,$start,$end) = @_;

  my $findPaths_sub;
  my $strongRef = $findPaths_sub = sub {
    my( $seen, $start, $end ) = @_;

    return [[$end]] if $start eq $end;

    $seen->{ $start } = 1;
    my @paths;
    for my $node ( @{ $graph->{ $start } } ) {
      my %seen = %{$seen};
      next if exists $seen{ $node };
      push @paths, [ $start, @$_ ]
          for @{ $findPaths_sub->( \%seen, $node, $end ) };
    }
    return \@paths;
  };

  weaken($findPaths_sub);       # Prevent memory leak

  my @all;
  push @all,@$_ for @{ $findPaths_sub->( {}, $start, $end ) };
  return @all;

  ## The above turns all the paths into one big list of nodes.
  ## I think maybe you meant this:
  #    return @{ $findPaths_sub->( {}, $start, $end ) };
  ## which would return a list of arrayrefs, one for each path.
}

Некоторые заметки:

Вы объявляете coderef следующим образом: 

$var = sub { ... };

Обратите внимание на оператор присваивания и конечную точку с запятой. Если вы хотите, чтобы coderef был рекурсивным, вы, должно быть, уже объявили $var. (Если вы скажете my $var = sub { ... };, новая переменная не будет существовать до после , когда подпрограмма создана, поэтому она не может ссылаться на $var.)

Вы называете это так: 

$var->(arg1, arg2, ...);

(Есть другие синтаксисы, которые работают, но я думаю, что это предпочтительный.)

В первой опубликованной мной версии произошла небольшая утечка памяти. В Perl используется сборщик мусора с подсчетом ссылок, что означает, что он не может удалять структуры данных, ссылающиеся на себя. Поскольку кодовая ссылка в $findPaths_sub захватывает ссылку на себя, она никогда не будет очищена (до завершения программы). Теперь я использую функцию weaken из Scalar :: Util (как упомянул singingfish в его записи в блоге ), чтобы избежать этого. $strongRef используется только для того, чтобы предотвратить сбор мусора до того, как мы закончили с этим.

1 голос
/ 01 ноября 2010
...