How can I use a non-caching infinite lazy list in Perl 6

Question

Infinite lazy lists are awesome!

> my @fibo = 0, 1, *+* ... *;
> say @fibo[1000];
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

They automatically cache their values, which is handy ... most of the time. But when working with huge Fibonacci numbers (example), this can cause memory issues.

Unfortunately, I can't figure out how to create a non-caching Fibonacci sequence. Anyone?

Answer 1

One major problem is you are storing it in an array, which of course keeps all of its values.

The next problem is a little more subtle, the dotty sequence generator syntax LIST, CODE ... END doesn't know how many of the previous values the CODE part is going to ask for, so it keeps all of them.
( It could look at the arity/count of the CODE, but it doesn't currently seem to from experiments at the REPL )

Then there is the problem that using &postcircumfix:<[ ]> on a Seq calls .cache on the assumption that you are going to ask for another value at some point.
( From looking at the source for Seq.AT-POS )

It's possible that a future implementation could be better at each of these drawbacks.

---

You could create the sequence using a different feature to get around the current limitations of the dotty sequence generator syntax.

sub fibonacci-seq (){
  gather {
    take my $a = 0;
    take my $b = 1;

    loop {
      take my $c = $a + $b;
      $a = $b;
      $b = $c;
    }
  }.lazy
}

If you are just iterating through the values you can just use it as is.

my $v;
for fibonacci-seq() {
  if $_ > 1000 {
    $v = $_;
    last;
  }
}
say $v;

my $count = 100000;
for fibonacci-seq() {
  if $count-- <= 0 {
    $v = $_;
    last;
  }
}
say chars $v; # 20899

---

You could also use the Iterator directly. Though this isn't necessary in most circumstances.

sub fibonacci ( UInt $n ) {
  # have to get a new iterator each time this is called
  my \iterator = fibonacci-seq().iterator;
  for ^$n {
    return Nil if iterator.pull-one =:= IterationEnd;
  }
  my \result = iterator.pull-one;
  result =:= IterationEnd ?? Nil !! result
}

If you have a recent enough version of Rakudo you can use skip-at-least-pull-one.

sub fibonacci ( UInt $n ) {
  # have to get a new iterator each time this is called
  my \result = fibonacci-seq().iterator.skip-at-least-pull-one($n);
  result =:= IterationEnd ?? Nil !! result
}

---

You can also implement the Iterator class directly, wrapping it in a Seq.
( this is largely how methods that return sequences are written in the Rakudo core )

sub fibonacci-seq2 () {
  Seq.new:

  class :: does Iterator {

    has Int $!a = 0;
    has Int $!b = 1;

    method pull-one {
      my $current = $!a;
      my $c = $!a + $!b;
      $!a = $!b;
      $!b = $c;
      $current;
    }

    # indicate that this should never be eagerly iterated
    # which is recommended on infinite generators
    method is-lazy ( --> True ) {}

  }.new
}

Answer 2

Apparently, a noob cannot comment.

When defining a lazy iterator such as sub fibonacci-seq2, one should mark the iterator as lazy by adding a "is-lazy" method that returns True, e.g.:

method is-lazy(--> True) { }

This will allow the system to detect possible infiniloops better.