Encapsulation récursive Fonction en Perl

Question

J'ai un code qui fonctionne bien ici:

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

Ce que je veux faire est de générer un sous-programme plus général de sorte qu'il suffit de prendre \%graph, $start,$end en entrée et le retour tableau final.

J'ai essayé de le faire de cette façon mais il ne compile pas.

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; 
} 

Quelle est la bonne façon de le faire?

Answer 1

Je ne peux pas comprendre ce que vous voulez findPathsAll pour revenir, donc cela peut ne pas être tout à fait ce que vous voulez. Quoi qu'il en soit, voici une traduction de findPaths dans un coderef récursive lexical:

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. 
} 

Quelques notes:

Vous déclarez un coderef comme ceci:

$var = sub { ... }; 

Notez le opérateur d'affectation et le point-virgule final. Si vous voulez que le coderef soit récursif, vous devez avoir déjà déclaré $var. (Si vous dites my $var = sub { ... };, la nouvelle variable n'existe pas tant que après la sous est créée, donc il ne peut pas se référer à $var.)

Vous l'appelez comme ceci:

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

(Il y a d'autres syntaxes qui fonctionnent, mais je pense que c'est la préférée.)

Il y avait une fuite de mémoire subtile dans la première version que j'ai publiée. Perl utilise un garbage collector de comptage de références, ce qui signifie qu'il ne peut pas supprimer les structures de données auto-référentielles. Puisque le coderef dans $findPaths_sub capturé une référence à lui-même, il ne serait jamais nettoyé (jusqu'à la sortie du programme). J'utilise maintenant the weaken function from Scalar::Util (comme mentionné par chanterfish dans his blog entry) pour éviter cela. $strongRef est utilisé uniquement pour empêcher le coderef d'être récupéré avant que nous n'en ayons fini avec.

Answer 2

I blogged about this very issue l'autre jour.