Juliaで汎用イテレータ型作ってみた

## 前置き：トピック

+ Julia のイテレータの実装例の紹介
+ 関数定義のテクニック：引数の指定の仕方
+ 関数定義のテクニック：条件分岐フローを極力省いた宣言的な定義

## Julia のイテレータ
Julia のイテレータは、`start()`, `done()`, `next()` の3つの関数を multi-dispatch 定義することで新しく作ることができます[^1]。
例（`takewhile()`を実装してみた[^2]）：

```jl
immutable TakeWhile{I}
    cond::Function
    xs::I
end

takewhile(cond, xs) = TakeWhile(cond, xs)

Base.eltype(it::TakeWhile) = eltype(it.xs)
Base.start(it::TakeWhile) = start(it.xs)
Base.next(it::TakeWhile, state) = next(it.xs, state)
function Base.done(it::TakeWhile, state)
    i, _ = next(it, state)
    !it.cond(i) || done(it.xs, state)
end

# println(collect(takewhile(x -> x*x < 25, 1:10)))
# => [1, 2, 3, 4]
```

これは、「新しい型を定義してその型に合う関数の多重ディスパッチを定義（≒メソッドを追加）する」という方法であるわけですが、今ひとつしっくりこない感がします。
その理由はおそらく、以下の2点：

1. （上記のように）ただフィルターとか変換したい時でも、新しい型を作って適用させる必要がある。
2. 新しい型を作るたびに多重ディスパッチの定義をする必要がある（省略や共通化ができない[^3]）。

そこで、汎用的なイテレータ型を作って、常にその型のインスタンスを生成するようにすれば、煩雑な関数多重定義を省略できて良いんじゃないか、と考えました。
で、作ってみたら、各種イテレータ（フィルター系、変換系含む）が宣言的に簡潔に書けるし、ついでに無限リスト（ストリーム）的なモノも簡単に定義できたりと、けっこう良さげだったので、勉強成果の一つとしてここに晒してみます。
ちなみに `v"0.3.7"` および `v"0.4.0-dev+4145"` で動作確認済です。

## 汎用イテレータ型 `GPIterator`

本題。まずは本体コード。

```jl:GPIterator.jl
# GPIterator.jl

# ===== GPIterator Basics =====

# === Type Definitions ===
abstract AbstractIterator

immutable EmptyIterator <: AbstractIterator
end

immutable GPIterator{T} <: AbstractIterator
    first::T
    rest::Function  # No arguments, Must return ::AbstractIterator
end

# === Iteration Definitions ===
Base.start(it::AbstractIterator) = it
Base.rest(::AbstractIterator, xs::AbstractIterator) = xs  # for VERSION ≥ v"0.4.0-dev"

Base.eltype(::EmptyIterator) = Any
Base.done(::AbstractIterator, ::EmptyIterator) = true
Base.next(::AbstractIterator, xs::EmptyIterator) = (nothing, xs)

Base.eltype{T}(::GPIterator{T}) = T
Base.done(::AbstractIterator, ::GPIterator) = false
Base.next(::AbstractIterator, xs::GPIterator) = (xs.first, xs.rest())

# === Outer Constructors ===
emptyiterator() = EmptyIterator()

gpiterator(it::AbstractIterator) = it
gpiterator(n::Number) = GPIterator(n, emptyiterator)
gpiterator(it) = gpiterator(it, start(it))
function gpiterator(it, state)
    done(it, state) && return EmptyIterator()
    val, next_state = next(it, state)
    GPIterator(val, ()->gpiterator(it, next_state))
end

# ===== Utilities =====

# `take(n, it)` iterates first n-items of original iterator `it`
take(::Integer, xs::EmptyIterator) = xs
function take(n::Integer, xs::GPIterator)
    n < 1 ? EmptyIterator() : GPIterator(xs.first, ()->take(n - 1, xs.rest()))
end

# `takewhile(pred, it)` iterates items while satisfying the pred.
takewhile(::Function, xs::EmptyIterator) = xs
function takewhile(pred::Function, xs::GPIterator)
    pred(xs.first) ? GPIterator(xs.first, ()->takewhile(pred, xs.rest())) : EmptyIterator()
end

# `drop(n, it)` iterates after n-items of original iterator `it`
drop(::Integer, xs::EmptyIterator) = xs
function drop(n::Integer, xs::GPIterator)
    n < 1 ? xs : drop(n - 1, xs.rest())
end

# `dropwhile(pred, it)` iterates items from NOT-satisfied element.
dropwhile(::Function, xs::EmptyIterator) = xs
function dropwhile(pred::Function, xs::GPIterator)
    pred(xs.first) ? dropwhile(pred, xs.rest()) : xs
end

# multi-dispatch definition (≒overload) Base.map()
Base.map(::Function, xs::EmptyIterator) = xs
function Base.map(fn::Function, xs::GPIterator)
    GPIterator(fn(xs.first), ()->map(fn, xs.rest()))
end

# multi-dispatch definition (≒overload) Base.filter()
Base.filter(::Function, xs::EmptyIterator) = xs
function Base.filter(pred::Function, xs::GPIterator)
    pred(xs.first) ? GPIterator(xs.first, ()->filter(pred, xs.rest())) : filter(pred, xs.rest())
end
```

ポイント解説：

+ 5〜14行目。型の定義。新しく定義した型（抽象型含む）は全部で3つ：
  + `AbstractIterator` …`EmptyIterator` および `GPIterator` の共通の super type
  + `EmptyIterator` …何も列挙するモノがないことを表すイテレータ型
  + `GPIterator` …最初の要素と、2つめ以降の要素を表す `AbstractIterator` を返す関数からなる composit type。ちなみに "GP" は "general-purpose" の略です。
+ 16〜26行目。イテレーションの定義。
  + `start(it)` は、それ自身 `it` を返すだけ。
  + `done(it, xs)` は、`xs`（状態を表す引数）が `EmptyIterator` ならば `true`、そうでなければ `false`。
  + `next(it, xs)` は、値として `xs`（`<:GPIterator`）の最初の要素を、次の状態として `xs` の「残りの要素を表すイテレータを返す関数」を実行した結果（`<:AbstractIterator`）を返す。
  + これにより、「`next()` するたびに次の値を順次算出し、`EmptyIterator` が現れるまで繰り返す」という仕組みで列挙をします。  
    あとこの仕組みのおかげで、無限列挙（ストリーム）対応になっています。
  + あと前節で説明しませんでしたが、24行目の `eltype()` 関数は、引数に指定したイテレータが列挙する値の型を返すもの。これを適切に多重定義すると、例えば`collect()`関数を使用したときにはその型（=:`T`）の配列 `Array{T}` を返却してくれます。  
    なお `eltype()` のデフォルト実装は戻り値は `Any`、つまり「どんな型でもOK（どんな型が列挙されるか分からない）」という意味になります。
  + \[関数定義] 例えば 20行目（`Base.eltype(::EmptyIterator) = Any`）。関数宣言時に「その引数の型が重要であって仮引数そのものは不要」な場合には、引数名を省略して`::«型»`とだけ書くことができます。  
    このパターンマッチ的な文法好き。無駄も省けるし関数定義をコンパクトにする一助になっているし。このコード内でも多用しています。
  + \[関数定義] 24行目（`Base.eltype{T}(::GPIterator{T}) = T`）。↑と同様「その引数の型パラメータの値を取得したい」場合には、こんな書き方ができます。関数宣言部に型パラメータを記述し、仮引数の型に同じパラメータを設定。  
    このパターンマッチ的な文法好き。無駄も省けるし関数定義をコンパクトにする一助になっているし。
+ 28〜38行目。外部コンストラクタ定義。主に「（他の）イテレータから `GPIterator` を生成するモノを定義しています。
  + 32行目。Julia では `Number` も iterableで、「その数値1つだけを列挙するイテレータ」として動作（`for i=1; print(i); end`とすると「1」とだけ表示）するので、それに合わせて「数値が渡されたら、最初の要素をその数値、2つめ以降の要素はなし（`EmptyIterator`を返す）」というイテレータを返すようにしました。
  + 一番のポイントは、34〜38行目。  
    このように他のイテレータから `GPIterator` を再帰的に構築できます。  
    また `GPIterator` 以外の全てのイテレータは、`GPIterator` に変換することができます。「イテレータと言えば `GPIterator`（`<:AbstractIterator`）」として型を統一（一本化）できます！
+ 40行目以降。よくある関数群（`take`, `takewhile`, `drop`, `dropwhile`, `map`, `filter`）を（多重）定義。
  + いずれも戻り値は `<:AbstractIterator`。型を統一！  
    外部コンストラクタ `gpiterator()` の定義と同様、再帰的定義だけで目的の処理が実装出来ていることにも注目。

### 使用例

```jl:GPIteratorSample.jl
# GPIteratorSample.jl

include("./GPIterator.jl")

# ===== ADDITIONAL DEFINITIONS =====

# from(2) := 2:3:4:...
from{T<:Integer}(s::T) = steps(s, one(T))

# steps(1, 2) := 1:3:5:...
steps{T<:Integer}(s::T, t::T) = GPIterator(s, ()->steps(s + t, t))

# Natural Numbers
nats() = from(1)

# Odd Numbers (> 0)
odds() = steps(1, 2)

# Fibonacci Sequence
fibs() = fibs(one(BigInt), one(BigInt))
fibs{T<:Integer}(a::T, b::T) = GPIterator(a, ()->fibs(b, a + b))

# println(typeof(fibs()))
# # => GPIterator{BigInt}

# ===== EXAMPLES =====

# `gpiterator` and `filter` sample : odd-primes under 100
println(collect(filter(isprime, gpiterator(1:2:100))))
# => [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

# `filter` and `take` sample : first 10 odd-primes
println(collect(take(10, filter(isprime, odds()))))
# => [3,5,7,11,13,17,19,23,29,31]

# `map` sample : FizzBuzz
function fizzbuzz()
    map(nats()) do n
        n % 15 == 0 && return "FIZZBUZZ"
        n % 5 == 0  && return "Buzz"
        n % 3 == 0  && return "Fizz"
        n
    end
end

# println(collect(take(20, fizzbuzz())))  # @> ERROR: `convert` has no method matching convert(::Type{Int64}, ::ASCIIString)
println(collect(Any, take(20, fizzbuzz())))
# => Any[1,2,"Fizz",4,"Buzz","Fizz",7,8,"Fizz","Buzz",11,"Fizz",13,14,"FIZZBUZZ",16,17,"Fizz",19,"Buzz"]
println(collect(Union(Int, ASCIIString), take(20, fizzbuzz())))
# => Union(ASCIIString,Int64)[1,2,"Fizz",4,"Buzz","Fizz",7,8,"Fizz","Buzz",11,"Fizz",13,14,"FIZZBUZZ",16,17,"Fizz",19,"Buzz"]

# `takewhile` sample : fibs under 100
fibsU100 = takewhile(n->n<100, fibs())
println(typeof(fibsU100))
# => GPIterator{BigInt}
println(eltype(fibsU100))
# => BigInt
for i = fibsU100
    println(i)
end
# => 1
# => 1
# => 2
# => 3
# => 5
# => 8
# => 13
# => 21
# => 34
# => 55
# => 89

# others : Collatz Sequence
function collatz(n::Integer)
    n < 2 && return gpiterator(n)
    GPIterator(n, ()->collatz(isodd(n) ? 3n + 1 : div(n, 2)))
end

println(collect(collatz(3)))
# => [3,10,5,16,8,4,2,1]
println(collect(collatz(27)))
# => [27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
```

見ていただければだいたいどんなことをしているかは分かっていただけると思います。
ポイント抜粋して簡単に解説。

+ 5〜24行目。無限ストリームをいくつか定義。
+ \[関数定義] 21行目補足。この宣言の仕方は `fibs(a::Integer, b::Integer)` と書いても良いのでは？　と思われるかもしれません。でも意味が変わってしまいます。そのように書いてしまうと「`a`も`b`も `Integer` の subtype（だから、整数型、ではあるんだけど同じ整数型とは限らない。`a`が`Int32`で`b`が`BigInt`でもOK）」という意味になります。  
  それに対してこの宣言方法 `fibs{T<:Integer}(a::T, b::T)` は、「`a`も`b`も、ある`Integer`の subtypeで同じ型（`a`が`Int64`なら`b`も`Int64`）」という意味になります。  
  よって例えば `fibs(1, BigInt(1))` と書くと「`Int64`（もしくは`Int32`）と`BigInt`を引数に取るメソッド `fibs` はありません」という旨のエラーになります。
  + ↑より親切な設計にするならば、もう一つ `fibs(a::Integer,b::Integer) = fibs(promote(a, b)...)` という多重定義をして「引数の型が異なっていたら `promote()` 関数を使って（大きい方の）型に合わせる」ということをします。今回は省略しました。
+ 29,33行目。奇素数をいくつか列挙するサンプル[^4]。  
  `isprime()` は素数判定をする Julia 標準の関数です。
+ 36〜50行目。よくある FizzBuzz を実装してみたサンプル。  
  注意点としては、46行目。`map()`の場合関数の戻り値の型が列挙要素によって異なる場合、先ほど説明した `eltype()` の多重定義のせいで逆に `collect()` 関数で変換エラーが出ることがあります。  
  ので、47行目のように明示的に `Any` を指定してどんな型でも受け付けるようにするか、49行目のように「列挙されうる型を全て網羅した `Union` 型」を指定してあげる必要があります。  
  なおこの制限は、`for`文で列挙する上では問題ありません（動的型付なので）[^5]。
+ 52〜71行目。`takewhile`とフィボナッチ数列のサンプル。詳細略。  
  これと同様に「リュカ数列」「トリボナッチ数列」「ペラン数列」等も簡単に定義できますね。
+ 73〜82行目。おまけ：「コラッツの数列」（参照：[Wikipedia:コラッツの問題](http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E3%81%AE%E5%95%8F%E9%A1%8C "コラッツの問題 - Wikipedia")）のサンプル。

このほかに、よくある例として、`zip(it1, it2, …)`、`repeat(el[,n])`（`el`を無限に（もしくは`n`回）繰り返すイテレータ）、`cycle(it)`（イテレータ `it` の列挙を無限に繰り返すイテレータ）、`chain(it1, it2, …)`（複数のイテレータを連結して列挙するイテレータ）等も、`GPIterator` を利用して書けます。

## 考察・展望

見ていただいて分かる通り、`GPIterator` をコンストラクタから生成するとき、第2引数はだいたいラムダ式を利用したクロージャになります。ほぼ毎回 `()->〜` と書いています。
なんかこれがもったいないような気がするので、マクロか何かを使ってもう少しシンプルな書式で定義できないかなー、と少し考えています。

ちなみに Julia が標準でこのシステムを採用せず、イテレータは3つのメソッドの組合せで実現するという仕様にしているのは、おそらく一番の理由は「効率」。
この `GPIterator` もある程度効率よく動作するよう実験を繰り返して実装しましたけれど、汎用性を持たせているが故にどうしても効率を犠牲にしている部分はあります。
例えばコード例は挙げませんでしたが、`repeat()`とか`zip()`とかを考えたとき、`GPIterator` の仕組みに組み込むよりは独自の型を作ってそれに特化した `start()`/`done()`/`next()` 関数の多重定義をした方が高効率なのは目に見えています。

それでもこの `GPIterator` が有用な例がもっと見つかれば、もっときちんと体系化・モジュール化して大々的に提案してみようかなー、と目論見中[^6]。

## 参考

+ Julia Documentation（ [v0.3.x](http://docs.julialang.org/en/release-0.3/) / [v0.4.x以降](http://docs.julialang.org/en/latest/) ）
+ [Lazy.jl](https://github.com/one-more-minute/Lazy.jl "one-more-minute/Lazy.jl")（遅延リスト、およびそれに関連した各種関数・マクロを提供する Julia のパッケージ。`Pkg.add("Lazy")` でインストール可能。`GPIterator` を構築するにあたってソースを少し参考にさせていただきました。ちなみにバグがありプルリク送ったけれどなかなか直してもらえない…）
+ [LazySequence.jl](https://github.com/dcjones/LazySequences.jl "dcjones/LazySequences.jl")（↑と同様の（より少し軽い）パッケージ。2年近く更新されていない…）


[^1]: http://docs.julialang.org/en/release-0.3/stdlib/collections/#iteration, もしくは http://docs.julialang.org/en/latest/stdlib/collections/#iteration 参照
[^2]: この実装には問題がある（`next()`するたびに内部状態が変更されてしまうイテレータ（例：`Task`）だと期待通りの動作をしない）のですが、まぁだいたいこんな感じというサンプルということであまり深入りせずにどうか一つ。
[^3]: `Union`型を使って引数が複数の型に対応するよう関数を多重定義すれば、処理の共通化はできないことはありませんが、あとから追加したい場合には結局問題となります。
[^4]: このあたりくらいなら、`GPIterator` を使わなくてもやりたいことは割とコンパクトに実現できると思いますけれど、まぁこれもサンプルと言うことで。
[^5]: とはいえ実際には、きちんとした設計をして返される値の型が一定となるようにすべきなんですけれど。
[^6]: それよりそろそろ Julia をもっと実用的に使うこと（＝数値計算とか機械学習とか）を始めないと…。お仕事（本業）的に…。