Iterators
Iterators are a design pattern that can be used to access elements of a container without depending on the implementation or type of the container.
- Task
- Create an array like container to hold the days of the week and a linked-list like container to hold colors.
- Print all of the elements of each container.
- Print the first, fourth, and fifth elements of each container.
- Print the last, fourth to last, and fifth to last of each container.
If you language supports iterators, use them. Otherwise show how access to elements can be
separated from the containers that hold them.
C++
<lang cpp>#include <iostream>
- include <list>
- include <string>
- include <vector>
using namespace std;
// Use iterators to print all of the elements of any container that supports // iterators. It print elements starting at 'start' up to, but not // including, 'sentinel'. void PrintContainer(forward_iterator auto start, forward_iterator auto sentinel) {
for(auto it = start; it != sentinel; ++it)
{
cout << *it << " ";
}
cout << "\n";
}
// Use an iterator to print the first, fourth, and fifth elements void FirstFourthFifth(input_iterator auto it) {
cout << *it; advance(it, 3); cout << ", " << *it; advance(it, 1); cout << ", " << *it; cout << "\n";
}
int main() {
// Create two differnt kinds of containers of strings
vector<string> days{"Sunday", "Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday"};
list<string> colors{"Red", "Orange", "Yellow", "Green", "Blue", "Purple"};
cout << "All elements:\n"; PrintContainer(days.begin(), days.end()); PrintContainer(colors.begin(), colors.end()); cout << "\nFirst, fourth, and fifth elements:\n"; FirstFourthFifth(days.begin()); FirstFourthFifth(colors.begin());
cout << "\nReverse first, fourth, and fifth elements:\n"; FirstFourthFifth(days.rbegin()); FirstFourthFifth(colors.rbegin());
} </lang>
- Output:
All elements: Sunday Monday Tuesday Wednesday Thursday Friday Saturday Red Orange Yellow Green Blue Purple First, fourth, and fifth elements: Sunday, Wednesday, Thursday Red, Green, Blue Reverse first, fourth, and fifth elements: Saturday, Wednesday, Tuesday Purple, Yellow, Orange
F#
<lang fsharp> //Iterators. Nigel Galloway: Januuary 30th., 2022 let N,G=[|"Sunday"; "Monday"; "Tuesday"; "Wednesday"; "Thursday"; "Friday"; "Saturday"|],["Red"; "Orange"; "Yellow"; "Green"; "Blue"; "Purple"] N|>Array.iter(printf "%s "); printfn "" N|>Seq.iter(printf "%s "); printfn "" G|>List.iter(printf "%s "); printfn "" G|>Seq.iter(printf "%s "); printfn ""
let rec advance(n:System.Collections.IEnumerator)=function 0->() |g->n.MoveNext(); advance n (g-1) let next(n:System.Collections.IEnumerator)=n.MoveNext(); n.Current
let X=(N|>Seq.ofArray).GetEnumerator() in printfn $"{next X} {(advance X 2; next X)} {next X}" let X=(G|>Seq.ofList).GetEnumerator() in printfn $"{next X} {(advance X 2; next X)} {next X}" let X=(N|>Array.rev|>Seq.ofArray).GetEnumerator() in printfn $"{next X} {(advance X 3; next X)} {next X}" let X=(G|>List.rev|>Seq.ofList).GetEnumerator() in printfn $"{next X} {(advance X 3; next X)} {next X}" </lang>
- Output:
Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sunday Monday Tuesday Wednesday Thursday Friday Saturday Red Orange Yellow Green Blue Purple Red Orange Yellow Green Blue Purple Sunday Wednesday Thursday Red Green Blue Saturday Tuesday Monday Purple Orange Red
FreeBASIC
<lang freebasic>Dim As Integer n, m Dim As String list(1 To 2, 1 To 7) = {_ {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"}, _ {"Red","Orange","Yellow","Green","Blue","Purple"}} Dim As Integer ind(1 To 3) = {1,4,5}
Print "All elements:" For n = 1 To Ubound(list)
For m = 1 To Ubound(list, 2)
Print list(n, m); " ";
Next m
Print
Next n
Print !"\nFirst, fourth, and fifth elements:" For n = 1 To Ubound(list)
For m = 1 To Ubound(ind)
Print list(n, ind(m)); " ";
Next m
Print
Next n
Print !"\nReverse first, fourth, and fifth elements:" For m = 1 To Ubound(ind)
Print list(1, Ubound(list,2)+1-ind(m)); " ";
Next m Print For m = 1 To Ubound(ind)
Print list(2, Ubound(list,2)-ind(m)); " ";
Next m Sleep</lang>
- Output:
Same as C++ input, Julia, Phix or Wren.
J
J's operations are designed to be applied to the data structure as a whole, and this explicitly includes mapping between representations. Also, in J, all data is array-like, and type is data. And this necessarily includes linked lists (though we can introduce arbitrarily complex mechanisms to obfuscate a linked list structure).
Still, one approach here might be:
<lang J>dow=: ;:'monday tuesday wednesday thursday friday saturday sunday' col=: (,<)/;:'red orange yellow green blue purple'</lang>
This gives us:
<lang J>
dow
┌──────┬───────┬─────────┬────────┬──────┬────────┬──────┐ │monday│tuesday│wednesday│thursday│friday│saturday│sunday│ └──────┴───────┴─────────┴────────┴──────┴────────┴──────┘
col
┌───┬─────────────────────────────────────────┐ │red│┌──────┬────────────────────────────────┐│ │ ││orange│┌──────┬───────────────────────┐││ │ ││ ││yellow│┌─────┬───────────────┐│││ │ ││ ││ ││green│┌────┬────────┐││││ │ ││ ││ ││ ││blue│┌──────┐│││││ │ ││ ││ ││ ││ ││purple││││││ │ ││ ││ ││ ││ │└──────┘│││││ │ ││ ││ ││ │└────┴────────┘││││ │ ││ ││ │└─────┴───────────────┘│││ │ ││ │└──────┴───────────────────────┘││ │ │└──────┴────────────────────────────────┘│ └───┴─────────────────────────────────────────┘</lang>
Here, the implementation's array indexing would see the linked list representation as a two element array. To index arbitrary elements from the linked list, we might map back from the linked list representation to a flat array representation, perhaps using <S:0 (which is a no-op on our array of days of week).
<lang J> echo ;:inv <S:0 dow monday tuesday wednesday thursday friday saturday sunday
echo ;:inv <S:0 col
red orange yellow green blue purple
echo ;:inv 0 3 4 {<S:0 dow
monday thursday friday
echo ;:inv 0 3 4 {<S:0 col
red green blue
echo ;:inv _1 _3 _4 {<S:0 dow
sunday friday thursday
echo ;:inv _1 _3 _4 {<S:0 col
purple green yellow</lang>
The downside of this approach is that the programmer must understand the data (to know to map all relevant list structures to the desired form). For example, we might instead say that a linked list is not merely an unbalanced binary tree, but must always have its data elements in the left node. That would give us this implementation for col:
<lang J> col=: ]F..(,<) ;:'red orange yellow green blue purple' </lang>
This creates an issue that a single element nested list looks very much like a flat array. To prevent that from being a problem, we include an empty element at the end of our flat array:
<lang J> dow=: a:,~;:'monday tuesday wednesday thursday friday saturday sunday' </lang>
Now everything is the same as before, except that we need to explicitly ignore the empty trailing element:
<lang J> echo ;:inv _2 _4 _5 {<S:0 dow sunday friday thursday
echo ;:inv _2 _4 _5 {<S:0 col
red yellow green</lang>
That said, we now also have the opportunity to implement a different kind of normalization routine, which takes advantage of the difference in representation (if we had a need for that...).
However, given the intrinsic value of comprehension when programming, a requirement for comprehension (and, thus, documentation) is frequently a worthwhile price. (There's also an execution cost issue, which can be especially significant in contexts where comprehension is difficult.)
Julia
Julia has a iteration interface. Any Julia type which implements the `iterate` function is considered an iterable. In base Julia, this includes any array type or collection, including any subclass of AbstractRange, UnitRange, Tuple, Number, AbstractArray, BitSet, IdDict, Dict, WeakKeyDict, EachLine, AbstractString, Set, Pair, and NamedTuple. In particular, Julia has an extensive set of functions which act on lists and vectors. Julia's Iterators can implement the C++ example: <lang julia>using DataStructures
function PrintContainer(iterator)
iter = Iterators.Stateful(iterator) foreach(x -> print(x, ", "), Iterators.take(iter, length(iter) -1)) foreach(println, Iterators.take(iter, 1))
end
function FirstFourthFifth(iterator)
iter = Iterators.Stateful(iterator) foreach(x -> print(x, ", "), Iterators.take(iter, 1)) popfirst!(iter); popfirst!(iter) foreach(x -> print(x, ", "), Iterators.take(iter, 1)) foreach(println, Iterators.take(iter, 1))
end
const days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"] const colors = list("Red", "Orange", "Yellow", "Green", "Blue", "Purple") # this is a linked list
println("All elements:") PrintContainer(days) PrintContainer(colors)
println("\nFirst, fourth, and fifth elements:") FirstFourthFifth(days) FirstFourthFifth(colors)
println("\nReverse first, fourth, and fifth elements:") FirstFourthFifth(reverse(days)) FirstFourthFifth(reverse(colors))
</lang>
- Output:
All elements: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday Red, Orange, Yellow, Green, Blue, Purple First, fourth, and fifth elements: Sunday, Wednesday, Thursday Red, Green, Blue Reverse first, fourth, and fifth elements: Saturday, Wednesday, Tuesday Purple, Yellow, Orange
Phix
Phix does not have iterators or for that matter design patterns. Since there are only
five builtin data types it is not an issue for a routine to "know" what it is doing.
Something along the lines of Same_fringe#Phix could perhaps also be used to implement custom iterators.
with javascript_semantics procedure print_all(object s) if integer(s) then -- (a dictionary) s = apply(true,getd,{getd_all_keys(s),s}) end if printf(1,"%s\n",join(s)) end procedure procedure printFirstFourthFifth(object s, integer d=+1) if integer(s) then -- (a dictionary) s = apply(true,getd,{getd_all_keys(s),s}) end if printf(1,"%s\n",join(extract(s,sq_mul({1,4,5},d)))) end procedure sequence days = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"} integer colors = new_dict({{2,"Red"}, {2.5,"Orange"}, {3,"Yellow"}, {"a","Green"}, {"b","Blue"}, {{#CD},"Purple"}}) printf(1,"All elements:\n") print_all(days) print_all(colors) printf(1,"\nFirst, fourth, and fifth elements:\n") printFirstFourthFifth(days) printFirstFourthFifth(colors) printf(1,"\nReverse first, fourth, and fifth elements:\n") printFirstFourthFifth(days,-1) printFirstFourthFifth(colors,-1)
Originally I used keys of 1..6 on the colours dictionary, but that looked suspicious. Note that the keys here are a mix of int/flt/string/seq, but still carefully "in order".
- Output:
All elements: Sunday Monday Tuesday Wednesday Thursday Friday Saturday Red Orange Yellow Green Blue Purple First, fourth, and fifth elements: Sunday Wednesday Thursday Red Green Blue Reverse first, fourth, and fifth elements: Saturday Wednesday Tuesday Purple Yellow Orange
Raku
Raku has iterators, but is rare for casual users to ever explicitly use them. Operators and functions that are designed to work on Iterable objects generally have the iteration semantics built in; so don't need an iterator to be explicitly called. It is far, far more common to use object slices to do the task example operations.
Rakus iterators are one direction only (not reversible), since they are designed to be able to work with infinite streams. It is difficult to reverse a stream that has no end. If the object / collection is finite, it may be reversed, but that is a separate operation from iteration.
Once an iteration has been reified, it is discarded unless explicitly cached. This allows effortless iteration through multi-gigabyte sized data objects and streams without filling up main memory.
The following example iterates though a hash of Positional Iterable objects and demonstrates both using explicit iterators, and object slice operations on each; then has a semi contrived example of where directly using iterators may be actually useful in Raku; collating unique ascending values from several infinite sequence generators.
<lang perl6>my %positional-iterable-types =
array => [<Sunday Monday Tuesday Wednesday Thursday Friday Saturday>], list => <Red Orange Yellow Green Blue Purple>, range => 'Rako' .. 'Raky', sequence => (1.25, 1.5, * × * … * > 50),
sub first-fourth-fifth ($iterable) {
my $iterator = $iterable.iterator;
gather {
take $iterator.pull-one;
$iterator.skip-one xx 2;
take $iterator.pull-one;
take $iterator.pull-one;
}
}
say "Note: here we are iterating over the %positional-iterable-types hash, but the order we get elements out is not the same as the order they were inserted. Hashes are not guaranteed to be in any specific order, in fact, they are guaranteed to _not_ be in any specific order.";
for %positional-iterable-types.values {
say "\nType " ~ .^name ~ ', contents: ' ~ $_ ~ "\nUsing iterators : first, fourth and fifth from start: " ~ first-fourth-fifth($_) ~ ', and from end: ' ~ first-fourth-fifth(.reverse) ~ "\nUsing object slices: first, fourth and fifth from start: " ~ .[0, 3, 4] ~ ', and from end: ' ~ .[*-1, *-4, *-5] ~ "\n";
};
say "\nWhere iterators really shine; when you are collating the values from several infinite generators.";
my @i = (1, * × 2 … *).iterator, (1, * × 3 … *).iterator, (1, * × 5 … *).iterator;
my @v = @i[0].pull-one, @i[1].pull-one, @i[2].pull-one;
my @seq = lazy gather loop {
take my $min := @v.min;
for ^@v { @v[$_] = @i[$_].pull-one if @v[$_] == $min };
}
say @seq[^25];</lang>
- Output:
Note: here we are iterating over the %positional-iterable-types hash, but the order we get elements out is not the same as the order they were inserted. Hashes are not guaranteed to be in any specific order, in fact, they are guaranteed to _not_ be in any specific order. Type Range, contents: Rako Rakp Rakq Rakr Raks Rakt Raku Rakv Rakw Rakx Raky Using iterators : first, fourth and fifth from start: Rako Rakr Raks, and from end: Raky Rakv Raku Using object slices: first, fourth and fifth from start: Rako Rakr Raks, and from end: Raky Rakv Raku Type Seq, contents: 1.25 1.5 1.875 2.8125 5.273438 14.831543 78.2132149 Using iterators : first, fourth and fifth from start: 1.25 2.8125 5.273438, and from end: 78.2132149 2.8125 1.875 Using object slices: first, fourth and fifth from start: 1.25 2.8125 5.273438, and from end: 78.2132149 2.8125 1.875 Type Array, contents: Sunday Monday Tuesday Wednesday Thursday Friday Saturday Using iterators : first, fourth and fifth from start: Sunday Wednesday Thursday, and from end: Saturday Wednesday Tuesday Using object slices: first, fourth and fifth from start: Sunday Wednesday Thursday, and from end: Saturday Wednesday Tuesday Type List, contents: Red Orange Yellow Green Blue Purple Using iterators : first, fourth and fifth from start: Red Green Blue, and from end: Purple Yellow Orange Using object slices: first, fourth and fifth from start: Red Green Blue, and from end: Purple Yellow Orange Where iterators really shine; when you are collating the values from several infinite generators. (1 2 3 4 5 8 9 16 25 27 32 64 81 125 128 243 256 512 625 729 1024 2048 2187 3125 4096)
Ring
<lang ring> list = [["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"],
["Red","Orange","Yellow","Green","Blue","Purple"]]
ind = [1,4,5] revInd = reverse(ind)
see "working..." +nl see "All elements:" + nl
for n = 1 to len(list)
for m = 1 to len(list[n])
see list[n][m] + " "
next
see nl
next
see nl + "First, fourth, and fifth elements:" + nl
for n = 1 to len(list)
for m = 1 to len(ind)
see list[n][m] + " "
next
see nl
next
see nl +"Reverse first, fourth, and fifth elements:" + nl
for n = 1 to len(list)
for m = 1 to len(revInd)
see list[n][m] + " "
next
see nl
next
see "done..." +nl </lang>
- Output:
All elements: Sunday Monday Tuesday Wednesday Thursday Friday Saturday Red Orange Yellow Green Blue Purple First, fourth, and fifth elements: Sunday Monday Tuesday Red Orange Yellow Reverse first, fourth, and fifth elements: Sunday Monday Tuesday Red Orange Yellow
Wren
In Wren an iterable object is a sequence whose class implements the iterate and iteratorValue methods. These methods enable one to walk through the sequence and look up the value of the each element.
Iterable objects, which include the built-in classes: List, Range and String, generally inherit from the Sequence class which provides a number of useful methods including: map, where and reduce.
Wren has no built-in linked list class but the Wren-llist module provides singly and doubly-linked implementations of them. Nor does it have a built-in way to iterate through a sequence in reverse though it is possible to write one. Here, we simply reverse the sequence first to do this.
The iterator protocol methods are not usually called directly as Wren's 'for' statement (and the Sequence methods) call them automatically under the hood. However, in the spirit of this task, they are called directly. <lang ecmascript>import "./llist" for DLinkedList
// Use iterators to print all elements of the sequence. var printAll = Fn.new { |seq|
var iter = null
while (iter = seq.iterate(iter)) System.write("%(seq.iteratorValue(iter)) ")
System.print()
}
// Use iterators to print just the first, fourth and fifth elements of the sequence. var printFirstFourthFifth = Fn.new { |seq|
var iter = null
iter = seq.iterate(iter)
System.write("%(seq.iteratorValue(iter)) ") // first
for (i in 1..3) iter = seq.iterate(iter)
System.write("%(seq.iteratorValue(iter)) ") // fourth
iter = seq.iterate(iter)
System.print(seq.iteratorValue(iter)) // fifth
}
// built in list (elements stored contiguously) var days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
// custom doubly linked list var colors = DLinkedList.new(["Red", "Orange", "Yellow", "Green", "Blue", "Purple"])
System.print("All elements:") printAll.call(days) printAll.call(colors)
System.print("\nFirst, fourth, and fifth elements:") printFirstFourthFifth.call(days) printFirstFourthFifth.call(colors)
System.print("\nReverse first, fourth, and fifth elements:") printFirstFourthFifth.call(days[-1..0]) printFirstFourthFifth.call(colors.reversed)</lang>
- Output:
All elements: Sunday Monday Tuesday Wednesday Thursday Friday Saturday Red Orange Yellow Green Blue Purple First, fourth, and fifth elements: Sunday Wednesday Thursday Red Green Blue Reverse first, fourth, and fifth elements: Saturday Wednesday Tuesday Purple Yellow Orange
XPL0
XPL0 doesn't have iterators as intended here. It has no built-in linked lists, thus an array is used instead. This translation is about as close as XPL0 can come to meeting the requirements of the task.
<lang XPL0> \\ Use iterators to print all of the elements of any container that supports \\ iterators. It print elements starting at 'start' up to, but not \\ including, 'sentinel'. proc PrintContainer(Start, Sentinel); int Start, Sentinel, It; [It:= 0; while Start(It) # Sentinel do
[Text(0, Start(It)); Text(0, " "); It:= It+1; ];
Text(0, "^m^j"); ];
\\ Use an iterator to print the first, fourth, and fifth elements proc FirstFourthFifth(Start, Dir); int Start, Dir, It; [It:= 0; Text(0, Start(It)); It:= It + 3*Dir; Text(0, ", "); Text(0, Start(It)); It:= It + 1*Dir; Text(0, ", "); Text(0, Start(It)); Text(0, "^m^j"); ];
\\ Create two different kinds of containers of strings int Days, Colors; [Days:= ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday",
"Friday", "Saturday", 0];
Colors:= ["Red", "Orange", "Yellow", "Green", "Blue", "Purple", 0];
Text(0, "All elements:^m^j"); PrintContainer(Days, 0); PrintContainer(Colors, 0);
Text(0, "^m^jFirst, fourth, and fifth elements:^m^j"); FirstFourthFifth(Days, +1); FirstFourthFifth(Colors, +1);
Text(0, "^m^jReverse first, fourth, and fifth elements:^m^j"); FirstFourthFifth(@Days(7-1), -1); FirstFourthFifth(@Colors(6-1), -1); ]</lang>
- Output:
All elements: Sunday Monday Tuesday Wednesday Thursday Friday Saturday Red Orange Yellow Green Blue Purple First, fourth, and fifth elements: Sunday, Wednesday, Thursday Red, Green, Blue Reverse first, fourth, and fifth elements: Saturday, Wednesday, Tuesday Purple, Yellow, Orange