Sequences and iterators

What you’ll build

A few number sequences, the Fibonacci numbers among them, which make each value only when it’s asked for, so a sequence can go on forever. Then a playlist type that a For ... In goes over as it would an array.

An iterator

An iterator gives a sequence’s values one at a time. A For ... In asks it for the next value by calling its Next Method, until Next gives Null for “no more”. This one counts down, and it’s a type of its own, written with three parts that Your own types covers in full:

• Struct Countdown ... End Struct declares a type whose value is a group of fields, here one field, From, declared with Field.
• Implements Iterator<Int> says the type keeps the promise of std.core’s Iterator<Int> Interface: that it has a Next Method giving an Int?. That’s what lets a loop and the iterator’s other Methods use it.
• ByRef Method marks a Method that changes the Struct’s fields, as Next does each time it counts.

Import std.core

Struct Countdown Implements Iterator<Int>
    Field From: Int

    ByRef Method Next(): Int?
        If From == 0 Then Return Null
        From -= 1
        Return From + 1
    End Method
End Struct

For n In Countdown(3)
    Print("{n}...")
End For
Print("Liftoff.")

3...
2...
1...
Liftoff.

A Struct is made by calling its name with its fields’ values in order, so Countdown(3) starts with From at 3.

A sequence without an end

An iterator needn’t end. This one gives the Fibonacci numbers, each the sum of the two before it, for as long as it’s asked. Fibonacci() leaves both fields out, so Current starts at its zero, 0, and Following at its default, 1. Take(10) asks for the first ten, and ToArray collects them.

Import std.core

Struct Fibonacci Implements Iterator<Long>
    Field Current: Long
    Field Following: Long = 1

    ByRef Method Next(): Long?
        Local value = Current
        Current = Following
        Following += value
        Return value
    End Method
End Struct

Print(Fibonacci().Take(10).ToArray())
Print(Fibonacci().TakeWhile(Function(n) => n < 100).Sum())

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
232

Lazy steps

Map, Filter, Take, and the iterator’s other adapters make a new iterator, which asks the one before it for values only as it’s asked for its own. Nothing runs until a consumer, like ToArray, Sum, Count, or First, asks for the values. A For ... In asks too.

Import std.core

Local squared = 0
Local squares = (1 To 1_000_000).Map(Function(n): Int
    squared++
    Return n * n
End Function)
Local firstOver50 = squares.Find(Function(square) => square > 50)

Print("first square over 50: {firstOver50 ?? 0}")
Print("squares worked out: {squared}")

first square over 50: 64
squares worked out: 8

Only 8 of the million numbers were squared: Find stopped asking once it had its answer. The lambda writes its result type, : Int, since Map works out the type of what it gives from the lambda. Each adapter comes from std.core’s Iterator<T>, so an iterator of your own has them all.

A type that goes in a loop

A For ... In also takes any value with an Iterate() Method, which gives the iterator to go over. Here a Playlist Class keeps its songs in an array and hands out the array’s iterator, so a loop over a playlist goes over its songs. It lists Implements Iterable<String> too, so a function that takes any collection of Strings, an Iterable<String>, takes a playlist.

Import std.core
Import std.collections

Class Playlist Implements Iterable<String>
    Field songs: String[] = []

    Method Add(song: String)
        songs.Add(song)
    End Method

    Method Iterate(): ArrayIterator<String> => songs.Iterate()
End Class

Function Count(songs: Iterable<String>): Int
    Local count = 0
    For song In songs
        count++
    End For
    Return count
End Function

Local mix = Playlist()
mix.Add("Intro")
mix.Add("Main theme")
mix.Add("Outro")
For i, song In mix.Iterate().Enumerate()
    Print("{i + 1}. {song}")
End For
For song In mix
    Print(song)
End For
Print("{Count(mix)} songs")

1. Intro
2. Main theme
3. Outro
Intro
Main theme
Outro
3 songs

Enumerate pairs each value with its position, which the loop takes apart into i and song.

What you learned

• An Iterator<T> gives values one at a time from Next, and Null when it’s done.
• A For ... In goes over an iterator, or over a value whose Iterate() gives one.
• A type that lists Implements Iterable<T> goes where any collection of Ts is taken.
• An iterator can be endless; Take and TakeWhile stop it.
• Adapters like Map and Filter are lazy: they run only as values are asked for.
• Consumers like ToArray, Sum, Find, and Count ask for the values.