Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Infinitely Lazy

by sleepingsquirrel (Hermit)
on Feb 07, 2005 at 16:43 UTC ( #428733=perlmeditation: print w/ replies, xml ) Need Help??

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


-- All code is 100% tested and functional unless otherwise noted.

Comment on Infinitely Lazy
Download Code
Re: Infinitely Lazy
by halley (Prior) on Feb 07, 2005 at 19:31 UTC
    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?

    --
    [ e d @ h a l l e y . c c ]

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


      -- All code is 100% tested and functional unless otherwise noted.
      Although I haven't seen it myself, maybe chapters 3 & 6 of Higher-Order Perl will provide additional motivation.


      -- All code is 100% tested and functional unless otherwise noted.

      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.

Re: Infinitely Lazy
by DrHyde (Prior) on Feb 08, 2005 at 11:02 UTC
Re: Infinitely Lazy
by spurperl (Priest) on Feb 08, 2005 at 11:06 UTC
    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://428733]
Approved by sschneid
Front-paged by neniro
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (21)
As of 2014-07-29 14:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (217 votes), past polls