Lazy sequences

An iterator does not have to walk anything stored. Value( ) can return a number it computed, and MoveNext( ) can compute the next one. The sequence then exists only as far as a loop asks for it.

'' A sequence computed as it is walked: nothing is stored.
type CollatzIterator
    as int64 n
    as boolean done
    declare function IsValid( ) as boolean
    declare function Value( ) as int64
    declare sub MoveNext( )
end type

function CollatzIterator.IsValid( ) as boolean
    return not done
end function

function CollatzIterator.Value( ) as int64
    return n
end function

sub CollatzIterator.MoveNext( )
    if n = 1 then
        done = true                 '' 1 was the last element
    elseif n mod 2 = 0 then
        n \= 2
    else
        n = 3 * n + 1
    end if
end sub

type Collatz
    as int64 start
    declare function GetIterator( ) as CollatzIterator
end type

function Collatz.GetIterator( ) as CollatzIterator
    return type( start, false )
end function

dim six as Collatz = ( 6 )
for each n in six
    print n;
next
print

'' A long walk: only the running totals are kept.
dim twentySeven as Collatz = ( 27 )
dim as int64 steps = 0, highest = 0
for each n in twentySeven
    steps += 1
    if n > highest then highest = n
next
print "27 takes"; steps - 1; " steps and climbs to"; highest

'' exit for stops the walk: the rest is never computed.
dim huge as Collatz = ( 989345275647 )
dim as int32 shown = 0
for each n in huge
    print n;
    shown += 1
    if shown = 4 then exit for
next
print " ..."

Output

 6 3 10 5 16 8 4 2 1
27 takes 111 steps and climbs to 9232
 989345275647 2968035826942 1484017913471 4452053740414 ...

The Collatz sequence halves an even number and turns an odd one into 3 * n + 1, until it reaches 1. CollatzIterator holds one number and a flag: MoveNext( ) applies the rule, and on reaching 1 marks the walk as done after that element has been seen.

• The walk from 6 prints every element.
• The walk from 27 visits 112 numbers, and the loop keeps only a count and the highest value. Nothing else is stored.
• The walk from 989345275647 stops at exit for after four elements. The rest of the sequence is never computed.

The cost of laziness is that nothing is remembered: walking twentySeven a second time computes every element again.

Activities

1. Write a Squares type whose iterator yields 1, 4, 9, ... for ever, and print the first square above 1000 with exit for.
2. Change the program to find which start below 100 takes the most steps.