15 Iterables¶

What comes next in the sequence a, b, c,…? You don’t need to think twice to know it’s d. How about 2, 4, 8, 16,…? The next power of two is 32. Again, not much of a challenge. Here’s one that’s a little trickier: O, T, T, F, F,…? What letter comes next? You can find the answer at the end of the chapter if you need it.

All these sequences were iterable, and you were the iterator by providing the next value in the sequence. In this chapter, you’ll learn what iterables and iterators are in Dart, why they’re useful and how to create your own.

What’s an Iterable?¶

An iterable in Dart is any collection that lets you loop through its elements. In more technical speak, it’s a class that implements the Iterable interface. List and Setare two iterables you’re already familiar with. Not every Dart collection is iterable, though. You learned in the previous chapter that you can’t directly loop over a map. If you want to visit all of a map’s elements, you have to iterate over the keys, values or entries, all of which are iterables.

Reviewing List Iteration¶

To review, take a look at the following example.

Add the following alphabetically sorted list to main:

final myList = ['bread', 'cheese', 'milk'];
print(myList);

Run that code, and you’ll see:

[bread, cheese, milk]

The [] square brackets tell you this is a list.

Now, iterate over the elements with a for-in loop:

for (final item in myList) {
  print(item);
}

Run that, and you’ll see each item in the list printed in order:

bread
cheese
milk

Meeting an Iterable¶

Lists are one specific kind of iterable, but you can also work directly with the Iterabletype. These are often accessible as properties of another collection. The example below will demonstrate that.

Add the following code to what you’ve already written:

final reversedIterable = myList.reversed;
print(reversedIterable);

Run that, and you’ll see the following:

(milk, cheese, bread)

The items in the list are now shown in reverse order. Additionally, they’re surrounded by () parentheses rather than [] square brackets. The parentheses are Dart’s way of telling you this is an Iterable and not a List.

So how are lists and iterables different? One important point is that an iterable is lazy. If you recall from Chapter 11, “Nullability”, a lazy property is one whose value isn’t calculated until you access it the first time. It’s similar for iterables: the elements of an iterable aren’t known until you ask for them.

You can imagine that if you had a list of a thousand elements, it would take a little work to reverse that list. You’d have to create a new list, copy the elements from the back of the original list to the front of the new list and continue all the way through for the rest of the elements. The reversed getter you saw above doesn’t do any of that work. It doesn’t create a new list. It doesn’t copy anything. It just instantly returns an Iterable. The key is that the Iterable knows how to give you the reversed elements when you need them…and not before. However, when you printed the list, you needed to know all the elements, so Dart ran through them at that point.

Converting an Iterable to a List¶

Another way to force Dart to get all the elements from an iterable is to convert the iterable to a list.

Write the following at the end of main:

final reversedList = reversedIterable.toList();
print(reversedList);

Calling toList causes the iterable to loop through its contents and store them as values in a new list.

Run the code above, and you’ll see a list with the familiar square brackets:

[milk, cheese, bread]

Note

If you know converting an iterable to a list in your application might be costly, don’t call toList until you need to or when the app isn’t busy with other tasks.

Operations on Iterables¶

This chapter will cover a few basic operations on iterables. You’ll learn other more advanced operations in Chapter 2, “Anonymous Functions”, in Dart Apprentice: Beyond the Basics.

Creating an Iterable¶

Trying to directly instantiate an Iterable will give you an error. To see that, write the code below in main:

final myIterable = Iterable();

The compiler complains that “Abstract classes can’t be instantiated.”

Look at the source code of Iterable if you want to learn more. In the code above, if you’re using VS Code, Command-click the class name Iterable on a Mac (or Control-click it on a PC). This will bring you to the iterable.dart source file, and you’ll see the following Dart source code:

abstract class Iterable<E> {
  const Iterable();

  // ...
}

Abstract classes are used to define all of the methods you want in a class. They can also include logic, which Iterable does. You’ll learn more about abstract classes in Dart Apprentice: Beyond the Basics. For now, it’s only important to know you can’t create an object directly from an abstract class unless it has a factory constructor, which const Iterable() isn’t.

But you can create an iterable by specifying the type annotation as Iterable and then assigning the variable a list value. Replace the myIterable line you wrote earlier with the following:

Iterable<String> myIterable = ['red', 'blue', 'green'];

The actual implementation is a list, which you know because of the square brackets. But by explicitly writing Iterable<int>, you surrender any superpowers that lists have and tell Dart you want to treat the collection as a humble iterable. The reason you do so here is so you can explore how to work directly with iterables in the examples that follow.

Accessing Elements¶

The way to access a particular element in the collection is to use elementAt with an index.

Write the following in main:

final thirdElement = myIterable.elementAt(2);
print(thirdElement);

Recall that 2 is the third element when the indexing starts at zero.

Run that, and you’ll see the green printed out in the console.

An iterable finds a specific element by starting at the beginning of the collection and counting to the desired element. Command-click elementAt if you’re using a Mac or Control-click it if you’re using a PC, and view the Dart source code:

E elementAt(int index) {
  // ...
  int elementIndex = 0;
  for (E element in this) {
    if (index == elementIndex) return element;
    elementIndex++;
  }
  // ...
}

Some of the code in there you may not recognize, but you should be able to see the elementIndex counting up inside the for-in loop as it searches through the elements until it finds the desired index. You can imagine that this could take some time for a large collection. This is in contrast to lists, where you can immediately access an element using a subscript notation like myList[2]. An iterable only knows how to iterate, though. So when you want to find an element, you’ve got to start counting from the beginning.

Finding the First and Last Elements¶

Use first and last to get the first and last elements of an iterable:

final firstElement = myIterable.first;
final lastElement = myIterable.last;

print(firstElement);
print(lastElement);

The code is simple, but don’t let the simplicity deceive you. This is an iterable, so it calculates these values by iterating. You don’t need to iterate far to find the firstelement, of course. However, if you want the last element, Dart finds it by starting at the beginning of the collection and moving through every element until there aren’t any left.

Getting the Length¶

Finding the number of elements in a collection is as deceptively simple as finding the last element.

Write the following in main:

final numberElements = myIterable.length;
print(numberElements);

Run that, and you’ll see 3 as the result.

The way Dart got that 3 was to loop through all the elements and count them one by one. That’s like asking a czar with a jellybean jar how many there are. “Hold on,” they say. “I’ll tell you today.” After waiting some, the answer comes: “5,381”. Then a passerby happens by: “My, a jellybean jar! I wonder how many there are.” “Just a minute,” replies the czar, “and I’ll tell you how many there are,”…and then proceeds to count them all over again. That’s how iterables work. A list knows how many elements it has. So does a set. But not an iterable. It has to count.

By this point, you may be asking, “Why would I ever want to use an iterable?” That’s a good question. If you need to frequently access elements by index or find the length, you shouldn’t use an iterable. Using a list is more efficient.

However, remember the advantage of an iterable is that it’s lazy. Imagine a two-gigabyte text file and you want to process the whole thing one line at a time. Theoretically, you could create a giant list by splitting on the newline character (see Dart Apprentice: Beyond the Basics, Chapter 1, “String Manipulation”), but that likely would freeze your computer. How much better to just wait until it’s time to start working, then grab a little data, process it and grab a little more. That’s the way an iterable works.

Other Important Methods on Iterable¶

The Iterable class has many other important methods you should learn. Here are a few of them:

map
where
expand
contains
forEach
reduce
fold

The thing is, these methods take anonymous functions as parameters, and you haven’t learned what anonymous functions are yet. Don’t worry, though — you’ll get to them in Dart Apprentice: Beyond the Basics. At that time, you’ll come back to the Iterablemethods listed above.

Exercise¶

Create a map of key-value pairs.
Make a variable named myIterable and assign it the keys of your map.
Print the third element.
Print the first and last elements.
Print the length of the iterable.
Loop through the iterable with a for-in loop.

Creating an Iterable From Scratch¶

A great way to learn how iterables work is to make an iterable collection from scratch. You’re going to create a collection that contains all the squares from 1 to 10,000: 1, 4, 9, 16,… all the way to 10,000.

There’s more than one way to make an iterable. The simplest way is probably to use a generator, but you can also go low-level and use an iterator. You’ll get a taste of both.

Using a Generator¶

The functions you’ve seen previously returned at most a single value. A generator is a function that produces multiple values before finishing. With the generator that you’re going to create in this chapter, the values come in the form of an iterable. This is known as a synchronous generator because all the values are available on demand when you need them.

Note

There’s another type of generator called an asynchronous generatorwhere you have to wait for the values to become available. You’ll learn about this in Dart Apprentice: Beyond the Basics, Chapter 13, “Streams”.

Creating a Synchronous Generator¶

Add the following function to your project file:

Iterable<int> hundredSquares() sync* {
  for (int i = 1; i <= 100; i++) {
    yield i * i;
  }
}

There are two new keywords here:

sync\*: Read that as “sync star”. You’re telling Dart that this function is a synchronous generator. You must return an Iterable from such a function.
yield: This is similar to the return keyword for normal functions except that yield doesn’t exit the function. Instead, yield generates a single value and then pauses until the next time you request a value from the iterable. Because iterables are lazy, Dart doesn’t start the generator function until the first time you request a value from the iterable.

Running the Code¶

Now that your generator function is finished, replace the contents of main with the following:

final squares = hundredSquares();
for (int square in squares) {
  print(square);
}

Dart won’t run hundredSquares until it gets to the for loop because that’s when Dart accesses the values of the squares iterable.

Run your code, and you’ll see the results below:

Next, you’ll implement this functionality again but at a lower level.

Using an Iterator¶

Iterables don’t know how to move from element to element within their collections. That’s the job of an iterator. In the previous example, the generator function served the purpose of the iterator, but in this example, you’ll create an iterator using the Iterator class.

Every Iterator must contain the following two components:

bool moveNext(): In this method, you provide the logic for how to get the next element in the collection. The method needs to return a Boolean value. As long as more elements remain in the collection, it returns true. A value of false means the iterator has reached the end of the collection.
current: This is a getter that returns the value of the element in your current progress of iterating through the collection. current is considered undefined until you call moveNext at least once. It’s also undefined after the iterator reaches the end of the collection, that is, after moveNext has returned false. Depending on the implementation, trying to access an undefined current might return a reasonable value or it might cause a crash. The behavior is undefined, though, so don’t try. That’s the agreement you make when you use an iterator.

Implementing the Iterator¶

Now, you’ll make an iterator that knows how to find the next squared number in the series of squares.

Add a lib folder to the root of your project if you don’t already have one. Then add a new file to lib named squares.dart.

Next, write the following code in squares.dart:

class SquaredIterator implements Iterator<int> {

  int _index = 0;

  // 1
  @override
  bool moveNext() {
    _index++;
    return _index <= 100;
  }

  // 2
  @override
  int get current => _index * _index;
}

You haven’t learned much about the keywords implements and override. You’ll learn about them in Dart Apprentice: Beyond the Basics. For now, just pay attention to the implementation of moveNext and current:

Every time moveNext is called, you add one to _index. This incrementally moves _index from 1 to 100. Once _index reaches 101, moveNext will return false, signaling that the iterator has reached the end of the collection.
Sometimes, it’s useful to have current return a stored private value, which you could name _current, for example. However, in this case, it was easy enough to just multiply _index by itself right here to find the square.

As you can see, you’re not storing the values of this collection anywhere. You’re simply calculating them as you need them.

Implementing the Iterable¶

Now that you have your iterator, you can write the code for your iterable.

Add the following class to lib/squares.dart:

class HundredSquares extends Iterable<int> {
  @override
  Iterator<int> get iterator => SquaredIterator();
}

Here are a few comments:

This is a class, so use upper camel case for the name HundredSquares. That’s in contrast to the lower camel case you used previously for the generator function named hundredSquares.
extends is a keyword you’ll learn about in Dart Apprentice: Beyond the Basics, Chapter 3, “Inheritance”. It means your HundredSquares class also gets to use all the logic from Iterable.
Creating a custom iterable only requires providing an iterator. This is where you return the instance of your SquaredIterator that you made in the previous step.

That’s all there is to it. It’s time to try your iterable out.

Running the Code¶

Open the file with your main method again and add the following import at the top:

import 'package:starter/squares.dart';

If your project is named something besides starter, then replace starter with your project name.

Now in main, delete the previous contents, and create your collection like so:

final squares = HundredSquares();

Because your collection is iterable, you can loop through it with a for-in loop just as you would with any other collection.

Add the following code at the bottom of main:

for (int square in squares) {
  print(square);
}

Run that to observe the list of squared numbers displayed in the console:

Note

Don’t try this without adult supervision, but if you’re adventurous, you can make an infinitely large collection simply by always returning true from the moveNext method of your iterator.

When to Use Lists, Sets, Maps or Iterables¶

Each type of collection has its strengths. Here’s some advice about when to use which:

Choose lists if order matters. Try to insert values at the end of lists wherever possible to keep things running smoothly. And be aware that searching can be slow with large collections.
Choose sets if you’re only concerned with whether something is in the collection or not. This is faster than searching a list.
Choose maps if you frequently need to look up a value by its key. This is also a fast operation.
Choose iterables if you have large collections where you need to visit all the elements lazily.

Challenges¶

Before moving on, here are some challenges to test your knowledge of iterables. It’s best if you try to solve them yourself, but solutions are available in the challenge folder for this chapter if you get stuck.

Challenge 1: Iterating by Hand¶

Create a list named myList and populate it with four values.
Use myList.iterator to access the iterator.
Manually step through the list using moveNext and print each value using current.

Challenge 2: Fibonacci to Infinity¶

Create a custom iterable collection that contains all the Fibonacci numbers. Add an optional constructor parameter that will stop iteration after the nth number.

Key Points¶

Iterables are collections in which you can step through each element individually.
Iterables are lazy, meaning no work is done to determine the collection elements until you ask for them.
Finding length or elementAt may be slow because the iterable calculates them by stepping through the elements one by one.
List and Set are iterable collections with additional features.
A synchronous generator is a function that returns multiple values on demand.
An Iterable uses an Iterator to determine the next element in the collection.

Where to Go From Here?¶

To explore more about collections and their methods in Dart, browse the contents of the dart:collection library. Also, check out Data Structures & Algorithms in Dart to learn how to build custom collections such as the following:

Stack: a collection with a first-in-last-out (FILO) data structure.
Queue: a collection with a first-in-first-out (FIFO) data structure.
Linked list: a list where one element points to the next rather than using an indexing system.
Tree: A collection where elements are arranged in a hierarchical parent-child relationship.

Solution: The answer to the sequence riddle at the beginning of the chapter is S, the first letter of the word six: One, Two, Three, Four, Five, Six.