Zig 言語用のイテレータライブラリを書きました
basis-concept-zig に続いて、Zig 言語のためのイテレータライブラリ iter-zig を作りました。
そこそこ頑張ってReadmeを書いたので詳細はそれを読むことで分かると思います。この記事には書きたいことを書きます(自明)。
Concept
イテレータは、値の集合から各要素を高々一度ずつかつ網羅的に列挙するデータ構造のことです*1。
iter-zig ではRustと同じくイテレータコンセプトを以下の条件を満たす型と定めました。
Self: type = @This()型を持つItem: type型を持つfn next(*Self) ?Itemというメソッドを持つ
この条件を確認するメタ関数として concept.isIterator: fn (type) bool という関数が用意されています。
comptime assert(!isIterator(u32)); comptime assert(isIterator(range.Range(u32)));
対応コンテナ
標準で提供されるコンテナをラップする以下のようなイテレータが提供されています。
- ArrayIter
- SliceIter
- ArrayListIter
- SinglyLinkedListIter
- BoundedArrayIter
- TailQueueIter
派生メソッド
このライブラリの提供するイテレータの実装型は、それぞれの next 関数のみに依存したさまざまな派生関数(？)を持っています。
例えば map, filter, fold などがあります。(Rust の Iterator trait の備えている関数は大体あります)
これらは以下のように使用できます。
var arr = [_]u32{ 1, 2, 3, 4, 5, 6 }; var it: Filter(Copied(SliceIter(u32)), fn (u32) bool) = iter.to_iter.SliceIter(u32).new(arr[0..]).copied().filter(struct { fn call(x: u32) bool { return x % 2 == 0; } }.call); assert(@as(u32,2) == it.next()); assert(@as(u32,4) == it.next()); assert(@as(u32,6) == it.next()); assert(null == it.next());
上のコード中の it の型(Filter(Copied(SliceIter(u32)), fn (u32) bool))を見ても確認出来ますが、
これらの派生関数の実装はRustと同じくいわゆるアダプタースタイルで実装されており、新たに値の列を返す関数は、イテレータ型のインスタンスを返すように実装されています。
従って新しく作られる値の列の各要素の評価は新しいイテレータの next が呼ばれた時点で行われます。
例えば it.map(f).map(g).map(h) は3回マップしてますが、 it は1度だけイテレーションされます(3重にマップされるイテレータが返る)。
ユーザ定義イテレータ
イテレータをユーザ定義することも出来ます。
例えばライブラリユーザがイテレータを定義する場合は以下のようにします。
const Counter = struct { pub const Self = @This(); pub const Item = u32; count: u32, pub fn new() Self { return .{ .count = 0 }; } pub fn next(self: *Self) ?Item { self.count += 1; if (self.count < 6) return self.count; return null; } };
この Counter はイテレータコンセプトを満たし、(当然)以下のように使うことが出来ます。
comptime assert(isIterator(Counter)); var counter = Counter.new(); assert(@as(u32, 1) == counter.next()); assert(@as(u32, 2) == counter.next()); assert(@as(u32, 3) == counter.next()); assert(@as(u32, 4) == counter.next()); assert(@as(u32, 5) == counter.next()); assert(null == counter.next());
しかしこのイテレータは map や filter を実装していません。
それらの派生関数(?)を自分で実装するのは大変です。そこで iter-zig は prelude.DeriveIterator というメタ関数を提供しており、派生関数を自動で導出することが出来ます。
const CounterExt = struct { pub const Self = @This(); pub const Item = u32; pub usingnamespace prelude.DeriveIterator(@This()); // 派生関数を導出 count: u32, pub fn new() Self { return .{ .count = 0 }; } pub fn next(self: *Self) ?Item { self.count += 1; if (self.count < 6) return self.count; return null; } };
この CounterExt イテレータは各種の派生関数を備えており、以下の例では map、filter、scan を使用しています。
var counter = CounterExt().new(); var it = counter .map(incr) // 2,3,4,5,6 .filter(even) // 2,4,6 .scan(@as(u32, 0), sum); assert(@as(u32, 2) == it.next()); assert(@as(u32, 6) == it.next()); assert(@as(u32, 12) == it.next()); assert(null == it.next());
prelude.DeriveIterator はユーザ定義の実装が存在しない関数のみ導出するため、対象の型について効率的な実装が出来る場合は、素直にそれを実装しておくだけで共存することが出来ます*2。
