Generadores

Un generador es una rutina que provee una forma de iterar sobre una estructura de datos. Habitualmente no toda la estructura reside en memoria y el generador la recorre realizando las operaciones necesarias para la construcción del siguiente elemento.

La Idea

~/Lperl/src$ perl allsubsets.pl A B C D | perl -ne 'printf "%2d:%4b %s",$k,$k,$_; $k++'
 0:   0 ()
 1:   1 (A)
 2:  10 (B)
 3:  11 (A, B)
 4: 100 (C)
 5: 101 (A, C)
 6: 110 (B, C)
 7: 111 (A, B, C)
 8:1000 (D)
 9:1001 (A, D)
10:1010 (B, D)
11:1011 (A, B, D)
12:1100 (C, D)
13:1101 (A, C, D)
14:1110 (B, C, D)
15:1111 (A, B, C, D)

Programa

pp2@nereida:~/src/perl/coro$ cat -n allsubsetsco.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use Coro::State;
 4
 5  sub create_generator {
 6    my @set = @_;
 7    my $powern = 1 << @set;
 8    my $n = -1;
 9    my @RESULT;
10
11    my $caller = Coro::State->new;
12    # Create coroutine
13    my $coroutine;
14    $coroutine = Coro::State->new( sub {
15      while () {
16        $n = -1 if $n == $powern;
17        $n++;
18        @RESULT = map {  $n & (1 << $_)? ($set[$_]) : () } 0..$#set;
19        $coroutine->transfer($caller);
20      }
21    } );
22
23    return sub {
24      $caller->transfer($coroutine);
25      return @RESULT;
26    };
27  };
28
29  sub traverse {
30    my $t = shift;
31    my $length = shift;
32    my @q;
33    do {
34      @q = $t->();
35
36      local $" = ', ';
37      print "(@q)";
38      print "\n";
39
40    } while (@q != $length);
41  }
42
43  my $t = create_generator(qw{a b c d});
44  my $s = create_generator(qw{0 1 2});
45
46  traverse($t, 4);
47  print "\n**********************\n";
48  traverse($s, 3);

Ejecución

pp2@nereida:~/src/perl/coro$ allsubsetsco.pl | cat -n
     1  ()
     2  (a)
     3  (b)
     4  (a, b)
     5  (c)
     6  (a, c)
     7  (b, c)
     8  (a, b, c)
     9  (d)
    10  (a, d)
    11  (b, d)
    12  (a, b, d)
    13  (c, d)
    14  (a, c, d)
    15  (b, c, d)
    16  (a, b, c, d)
    17
    18  **********************
    19  ()
    20  (0)
    21  (1)
    22  (0, 1)
    23  (2)
    24  (0, 2)
    25  (1, 2)
    26  (0, 1, 2)