Range Over Iterators in Chapel

In this example, we will use Chapel to demonstrate the concept of iterators, similar to the example shown previously in another language. Starting with version 1.23, the language has added support for iterators, which lets us iterate over pretty much anything.

Let’s look at the List type that we will define. The list will consist of elements, and we’ll add an AllElements iterator to return all elements in the list. We will also show how to create a Fibonacci sequence iterator.

Here’s the full source code.

use List;

record element {
    var next: owned element?;
    var val: int;
}

record List {
    var head: owned element?;
    var tail: owned element?;
}

proc List.push(v: int) {
    if this.tail == nil {
        this.head = new owned element(nil, v);
        this.tail = this.head;
    } else {
        this.tail.next = new owned element(nil, v);
        this.tail = this.tail.next;
    }
}

iter List.allElements() {
    var e = this.head;
    while e != nil {
        yield e.val;
        e = e.next;
    }
}

proc genFib() {
    var a, b = (1, 1);
    while true {
        yield a;
        const temp = a;
        a = b;
        b += temp;
    }
}

proc main() {
    var lst = new List();
    lst.push(10);
    lst.push(13);
    lst.push(23);

    for elem in lst.allElements() {
        writeln(elem);
    }

    var all = [elem in lst.allElements()];
    writeln("all: ", all);

    for n in genFib() do {
        if n >= 10 then break;
        writeln(n);
    }
}

Explanation#

1. List and Element Definition:

   • The element record defines the structure for storing elements in the list, with a next pointer and a value val.
   • The List record contains head and tail pointers to manage the list.

2. Push Method:

   • The push method adds a new value to the list. If the list is empty, it initializes both head and tail with the new element. If not, it links the new element to the tail and updates tail.

3. AllElements Iterator:

   • The allElements iterator iterates over the list, yielding each value. This iterator can be used in a for loop to traverse the list.

4. Fibonacci Iterator:

   • The genFib function generates an indefinite sequence of Fibonacci numbers and continues as long as the for loop in main does not break.

5. Main Function:

   • Demonstrates pushing elements into the list.
   • Uses the allElements iterator to print each element.
   • Collects all elements into an array and prints it.
   • Generates and prints Fibonacci numbers stopping at 10 using the genFib iterator.

This example illustrates how Chapel’s iterators and lists can be used to manage and traverse collections of data efficiently.