Listas Perezosas

La evaluación perezosa es una estrategia de cómputo que intenta retrasar los cálculos de las expresiones hasta que sean realmente necesarios. Los iteradores vistos en la sección 4.18.3 pueden considerarse una forma de evaluación perezosa: en vez de generar una lista potencialmente enorme de objetos (permutaciones, subconjuntos, o cualesquiera que sean) sólo se genera un item de cada vez. Los items que no sean usados por el programa no serán nunca generados y no se malgastará tiempo y espacio en ellos.

Otro ejemplo de evaluación perezosa lo constituyen las listas perezosas. Una lista enlazada perezosa es casi igual que una lista enlazada ordinaria. Cada nodo esta formado por una parte de información y un enlace que permite acceder al siguiente nodo de la lista. No hay diferencia señalable de las subrutinas node y head del siguiente código con el que escribirıamos para implantar una lista enlazada ordinaria. La diferencia está en la cola de la lista (accedida mediante la subrutina tail). La cola de la lista es una referencia a un código que - cuando la cola es accedida - permite calcular el siguiente elemento de la lista. Una cola se denomina una promesa o promise. La función tail comprueba si la cola es una promesa (i.e. una referencia a código) y si es ası pasa a computar el siguiente nodo mediante la función referenciada.

El siguiente código crea una lista (perezosa) conteniendo las lıneas de un fichero hasta la primera lınea que casa con una expresión regular dada como argumento.

La subrutina file2lazylist abre el fichero y retorna la función que será usada como promesa. Esta función trabaja en clausura guardando el acceso al manejador de fichero $fh (que también es retornado).

lhp@nereida:~/Lperl/src/hop/Chap6$ cat -n useStreams1.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3  use Carp;
 4  use IO::File;
 5
 6  sub node($$) {
 7    my ($h, $t) = @_;
 8    [$h, $t];
 9  }
10
11  sub head {
12    my ($s) = @_;
13    $s->[0];
14  }
15
16  sub tail {
17    my ($s) = @_;
18    if (is_promise($s->[1])) {
19      $s->[1] = $s->[1]->();
20    }
21    $s->[1];
22  }
23
24  sub is_promise {
25    ref($_[0]) eq 'CODE';
26  }
27
28  sub show_until_match {
29    my ($s, $regexp) = @_;
30    while ($s and head($s) !~ /$regexp/) {
31      print head($s);
32      $s = tail($s);
33    }
34    print head($s) if $s;
35  }
36
37  sub file2lazylist {
38    my $fn = shift;
39    my $fh = new IO::File;
40    $fh->open("< $fn") or carp "No se pudo abrir $fn: $!";
41
42    my $nl;
43    $nl = sub {
44      return unless defined($_ = <$fh>);
45      return node($_, $nl);
46    };
47    return ($fh, $nl)
48  }
49
50  my $file = shift;
51  my $regexp = shift;
52  my ($fh, $fl) = file2lazylist($file);
53  my $node = $fl->();
54  show_until_match($node, $regexp);
55  close($fh);

Al ejecutar el código anterior obtendremos una salida similar a esta:

lhp@nereida:~/Lperl/src/hop/Chap6$ useStreams1.pl useStreams.pl '\(.*\)'
#!/usr/bin/perl -w
use strict;
use Carp;
use IO::File;

sub node($$) {

Para saber mas sobre listas perezosas consulte el libro Higher Order Perl [13].