Infinitely Lazy

[sleepingsquirrel]

The topic of lazy code came up recently in regards to Perl6. But with a little extra effort, we can do lazy lists in Perl5. So I thought I present a little taste of my favorite use for laziness: infinite lists...

#!/usr/bin/perl 

#make a finite lazy list (1,2,12,3.14)
$g=cons(1,cons(2,cons(12,cons(3.14,undef))));

#double the values
$twice = lazyMap(sub{2*$_[0]}, $g);

#print values to check correctness...
#should be 2,4,24,6.28
#don't try unlazyMap on infinite lists...
print "twice: ",join(",", unlazyMap(sub{$_[0]}, $twice))."\n";

$z = zeros();    #create infinite list of zeros (a la /dev/zero)
$inf=cons(3,$z); #a infinite list of zeros with a 3 on the front

$double_plus1 = lazyMap(sub{2*$_[0]+1}, $inf);
$take8 = take(8, $double_plus1); #grab first 8 values of infinite list
print "double_plus1: ",join(",", unlazyMap(sub{$_[0]}, $take8))."\n";

$nums  = take(10, nums());
print "integers: ",join(",", unlazyMap(sub{$_[0]}, $nums))."\n";

$fibs  = take(10, fibs(1,0)); 
print "fibs: ",join(",", unlazyMap(sub{$_[0]}, $fibs))."\n";
print "1000th Fibonacci: ",Nth(1000,fibs(1,0)),"\n";
                            
$primes  = take(10, primes(3,2));
print "primes: ",join(",", unlazyMap(sub{$_[0]}, $primes))."\n";

sub zeros { sub{ (0,zeros()) } }
sub nums  { sub{ (0, sub{ (1, lazyMap(sub{$_[0]+2},nums())) })}}
sub fibs  { my ($x, $y)=@_; sub{ ($x+$y, fibs($y,$x+$y)) } }

sub primes{ my ($n, @ps) = @_;
            (scalar grep !($n % $_), @ps)
                ? primes($n+2,@ps)
                : sub{ ($n, primes($n+2,$n,@ps)) } }

###### Helper subroutines ###############
sub cons  { my ($val, $list) = @_;
            sub { return ($val, $list) } }

sub head  { my ($h, $t)=$_[0]->() if defined($_[0]);
            return $h;                               }

sub tail  { my ($h, $t)=$_[0]->() if defined($_[0]);
            return $t;                               }

sub unlazyMap{  my ($f, $list) = @_;
                my ($h, $t) = $list->() if defined($list);

                defined($t) ? ($f->($h),unlazyMap($f,$t))
                            :  $f->($h)                   }

sub lazyMap {  my ($f, $list) = @_;
               my ($h, $t) = $list->() if defined($list);

               defined($t)  ? sub{ ($f->($h),lazyMap($f,$t)) }
                            : sub{ ($f->($h),undef         ) }    }

sub take  {  my ($n, $list) = @_;
             return undef if ($n <= 0 or !defined($list));
            (my $h, my $t) = $list->();
             sub{ ($h, take($n-1, $t)) }                   }

sub Nth   {  my ($n, $list) = @_;
             return undef if (!defined($list));
            (my $h, my $t) = $list->();
             $n<=1 ? $h : Nth($n-1, $t);        }

[halley]

I think I might divine what you mean by 'lazy lists' in this example, but maybe you'd give the "fifty words or less" overview of what they are, and maybe a little more to explain why you'd want to implement them at all?

I don't follow Perl 6 development too closely, but I feel like after the Apocalypse 5, things have been going damned goofy in the design of Perl 6. It seems to me that while Perl 5 is trying to be pragmatic and primordial, Perl 6 is bloating up on every "interesting" computer science concept that strikes some developer's fancy.

Perl 6 is shaping up to be the Prego of the computing world: you want it, it's in there. Will this help admins script their glue and read other people's scripts? Or will it impede adoption by being too esoteric and diverse?

[sleepingsquirrel]

Maybe Lazy Evaluation would be a good place to jump in?

[sleepingsquirrel]

Although I haven't seen it myself, maybe chapters 3 & 6 of Higher-Order Perl will provide additional motivation.

[bunnyman]

Lazy evaluation isn't esoteric and unfamiliar. If you have ever written $foo = $ENV{"FOO"} || "foo"; then you have used it.

Ever seen this code before?

if(grep /needle/, @haystack) { print "found it! }

If @haystack is large and begins with "needle", then this code is searching the entire array even though it has enough information to stop after the first element. If grep were using lazy evaluation, then this code could go faster.

Update:

@matches = ( grep /$pattern/, @ReallyBigList )[ 0 .. $n ];

This code gets the first $n matches in the list, but Perl is not smart enough to know it is allowed to stop searching after it has enough matches. It will search down the entire list no matter what. Lazy evaluation would be nice here too.

[DrHyde]

See also Language::Functional and Set::Infinite.

[spurperl]

You might want to take a look at MJD's article on streams. It provides motivation, background and some high-quality code for streams / infinite lists.