Series, Memoization, and Limits

Out on Reddit, my last post got some interesting comments. In particular, one commenter creates a finite series of squares, and then asks “That’s all well and good, but what would I have to do to say ‘up to 900′ instead of saying ‘up to 30^2′?” That’s a great question, and I’d like to explore the answer to it, though I’m going to stick with the Fibonacci series for my examples.

First, there’s a very quick and dirty answer to this. If you modify the original series, it is easy to add a limit term:

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... 900);
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

That gives you all the Fibonacci numbers less than or equal to 900. But the list is no longer expandable; with this one, if you say @Fibonacci[100], rather than calculating the 100th value of the series, it will just act like it’s a normal out-of-bounds array access.

In an ideal world, we’d have an easy way of looking at just part of an infinite series. What tools do we have in our toolbox? Well, there’s grep:

>  my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> my @F-low := @Fibonacci.grep(* < 900); 1;
1
> say @F-low[10]
55
> say @F-low[20]

…and that last one is where the trouble starts, because it never comes back. By 20, we’re already well over 900. But grep’s been fed an infinite list, and it doesn’t know anything about it, so it just keeps on looking forever. So that won’t do.

The next tool we have is the first method.

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> say @Fibonacci.first(* <= 900)
0
> say @Fibonacci.first(* > 900)
987

As you can see, first is great at finding the first Fibonacci number greater than 900. It’s pretty useless for finding all the numbers less then 900, though.

So, the bad news here is that, as I write this, Perl 6 does not have a method which can give us a finite portion of an infinite list based on some test, other than “give us the first N elements”. The good news is that the function we want is dead simple to write:

sub take-while(@a, Mu $test) {
    gather {
        for @a.list {
            last unless $_ ~~ $test;
            take $_;
        }
    }
}

This is actually a straightforward modification of the normal grep code. $test is defined as Mu so it can be anything that can be smartmatched against, including junctions. Then we scan the list, exiting if a smartmatch against the current element fails, and otherwise returning the element in our output list.

This is just the trick for the problem in question:

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> take-while(@Fibonacci, * < 900)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
> take-while(@Fibonacci, * < 400000)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811
> take-while(@Fibonacci.grep(* %% 2), * < 400000)
0 2 8 34 144 610 2584 10946 46368 196418
> take-while(@Fibonacci, Int)
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903

So here we have it: we’ve still got the efficiency of the de facto memoized solution, but we can also carve off portions of the list based on some criteria. I threw in the last one there just to show it didn’t have to be a Code block passed in; in this case, it shows us how far we get down the series with Int values before our current limited integer math throws in the towel and gives you back a Num instead. (Note that once we get arbitrarily large Ints in Rakudo, that line will no longer work, because take-while(@Fibonacci, Int) will return an infinite list!)

And now for the even slightly better news: as of today, take-while is available in the List::Utils module.

About these ads

3 Responses to “Series, Memoization, and Limits”

  1. Patrick Michaud Says:

    To stop a grep or map, use last:

      my @F-low := @Fibonacci.map( { last if $_ > 900; $_ } );
      say @F-low[10];
      say @F-low[20];  # no longer infinite
    

    Pm

  2. Eevee Says:

    It seems intuitive to me that this should work:

    my @fib := (0, 1, -> $a, $b { $a + $b } … *);
    my @fib_capped := (@fib … 900);

    But it appears not to be the case. I think the … operator is trying to eagerly consume @fib. Perhaps it should not?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: