封裝遞歸函數在Perl

Question

我有那麼這裏工作的代碼：

#!/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; 
} 

什麼是正確的做法？

Answer 1

我想不出你想要什麼findPathsAll返回，所以這可能不是你想要的。總之，這裏的的findPaths翻譯成詞法遞歸CODEREF：

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中的coderef獲取到自身的引用，因此它永遠不會被清除（直到程序退出）。我現在使用the weaken function from Scalar::Util（如唱歌魚在his blog entry中提到的）來避免這種情況。 $strongRef僅用於在我們完成之前使coderef不被垃圾收集。

Answer 2

我blogged about this very issue有一天。