一緒に無限の旅へとお出かけしませんか？
コンピューターの資源は有限です。
なので本当の意味での無限はとても扱えた話ではありません。
ですが、ちょっとした工夫で無限を（一部）扱えるようするテクニックがあります。
そのテクニックを使ってちょっとだけ無限の旅にお出かけしてみましょう。
初めての人はきっと今までにない視点が得られることでしょう。
データ構造
最初にもっとも大切なデータ構造の定義を考えます。
やや天下り的ではありますが、今回は以下の定義を使います。
enum List<T> {
case Cons(T, () -> List<T>)
case Nil
}
Consは、データと、その次のリストを保持します。
Nilは終端ですね。
ここでポイントなのは、その次のリストが関数になっている点です。
ここが関数であることで、リストの次の要素は本当に必要になった時だけ決めれば良くなるのです。
さらに、この構造の良い所は、Optionalが極力出てこない事と、
きちんと空リストも表現できる点です。
※本当はListに@autoclosureを使いたかったのですが、Swift1.2では出来なくなっていたので、現時点では普通の関数型になっています
準備を整える
データ型が定まったところで、ちょっとシンプルなリストを構築してみましょう。
ただちょっとヘルパー関数があると表記が楽なので以下の関数を用意しました。
func cons<T>(value: T, list: List<T>) -> List<T> {
return List.Cons(value) { list }
}
func lazyCons<T>(value: T, f: () -> List<T>) -> List<T> {
return List.Cons(value, f)
}
consは値を１つとリストを受け取り、頭に値をくっつけたリストを返す関数です
let list = cons(1, cons(2, cons(3, .Nil)))
くっつけることが出来たなら、分離できないとおかしいですね、
なので、今度は分離をするために、以下の二つを定義します。
extension List {
var car: T? {
switch self {
case let .Cons(car, _):
return car
case .Nil:
return nil
}
}
var cdr: List<T> {
switch self {
case let .Cons(_, cdr):
return cdr()
case .Nil:
return .Nil
}
}
}
carで、そのリストが持っているデータを取り出せます
cdrで、そのリストの次のリストを取り出せます
※この辺りの名前はlispから取ってきました
さて、ついでにListをSequenceTypeに準拠させておくと、
for in にも使える上、Array(somelist)と直接Arrayに変換をかけられるので便利です。
※コメントでご指摘いただいた@satoshiaさんに感謝申し上げます
struct ListGenerator<T> : GeneratorType {
typealias Element = T
init(_ list: List<T>) {
_list = list
}
mutating func next() -> Element? {
let car = _list.car
_list = _list.cdr
return car
}
var _list: List<T>
}
extension List : SequenceType {
func generate() -> ListGenerator<T> {
return ListGenerator(self)
}
}
これを使って、先ほどのリストを開けてみましょう
let list = cons(1, cons(2, cons(3, .Nil)))
for n in list {
println(n)
}
<出力>
1
2
3
おお、素晴らしい、ちゃんとリストになっていますね。
また、ListのinitでSequenceTypeを受けれるようにすると、
配列からListに変換したい場合にもシンプルに対応できます。
※コメントでご指摘いただいた@satoshiaさんに感謝申し上げます
func toList<T: GeneratorType>(var g: T) -> List<T.Element>{
if let value = g.next() {
return lazyCons(value) {
toList(g)
}
}
return .Nil
}
extension List {
init<S : SequenceType where T == S.Generator.Element>(_ s: S) {
self = toList(s.generate())
}
}
勢い余って、ArrayLiteralConvertibleに対応するのも良いかもしれません。
extension List : ArrayLiteralConvertible {
typealias Element = T
/// Create an instance initialized with `elements`.
init(arrayLiteral elements: Element...) {
self = List(elements)
}
}
println("-- bridge --")
let array = [2, 3, 5, 7, 11, 13]
let fromArray = List(array)
for n in fromArray {
println(n)
}
println("-- literal --")
let fromLiteral: List<String> = ["13", "11", "7", "5", "3", "2"]
for n in fromLiteral {
println("\"\(n)\"")
}
<出力>
-- bridge --
2
3
5
7
11
13
-- literal --
"13"
"11"
"7"
"5"
"3"
"2"
これで準備はオッケーです。
我々は無限を手にする
さあもう準備は整っています。
手始めにずっと1を繰り返す無限リストを作りましょう。
func repeatOne() -> List<Int> {
return lazyCons(1) { repeatOne() }
}
for n in repeatOne() {
println(n)
}
<出力>
1
1
1
1
1
1
1
(略)
おっと、拍子抜けでしたでしょうか？
重要なのは１箇所だけ、 { repeatOne() } のところです。
つまり、リストの次の要素が必要になった時にまた１個だけリストを生成するような構造なのです。
もちろん上記のコードは無限ループしますのでご注意ください。
一見凄そうな物も、蓋を開けてみれば中身は単純であるというのは良くあることです。
1を繰り返すだけでは自由度が無いですね、せめて値を選べるようにしましょう。
あとはついでに型も抽象化すると、以下のようにも書けます。
func repeat<T>(value: T) -> List<T> {
return lazyCons(value) { repeat(value) }
}
for n in repeat(3) {
println(n)
}
<出力>
3
3
3
3
3
3
3
3
(略)
自然数を手にいれる
自然数は無限です。ただ局所的に見ると、1を足していくだけです。
では、やってみましょう。
func natural(n: Int) -> List<Int> {
return lazyCons(n) { natural(n + 1) }
}
for n in natural(1) {
println(n)
}
<出力>
1
2
3
4
5
6
（略）
抽象化する
上記の関数、naturalはもうちょっと抽象化が出来ます。
一つ前の値から、次の値を計算する関数を受け取るようにしてみましょう。
こういう関数のことを高階関数と呼んだりしますね。
func iterate<T>(v: T, f: T -> T) -> List<T> {
return lazyCons(v) { iterate(f(v), f) }
}
let natural = iterate(1){ $0 + 1 }
for n in natural {
println(n)
}
<出力>
1
2
3
4
5
6
（略）
let odd = iterate(1){ $0 + 2 }
for n in odd {
println(n)
}
<出力>
1
3
5
7
9
（略）
だんだん慣れてきましたでしょうか。
有限へと回帰する
計算機の都合上、ずっと無限のままだと困ります。
なので止めるために、任意の個数にリストを制限するコードを用意しましょう。
extension List {
func take(n: Int) -> List<T> {
if n > 0 {
if let v = self.car {
return lazyCons(v) { self.cdr.take(n - 1) }
}
}
return .Nil
}
}
これはnをどんどん減らしていって、0になったら終端を作る関数です。
lazyConsを使っているので、計算自体は遅延されたままです。
これを使うとさっきの自然数と有限に落とし込めますね。
let natural = iterate(1){ $0 + 1 }
for n in natural.take(5) {
println(n)
}
<出力>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ちゃんと停止する
部分から全体へ
有限のリストに落とすことができたら、リスト同士をくっつけたくなってきます。
func +<T>(a: List<T>, b: List<T>) -> List<T> {
if let v = a.car {
return lazyCons(v) { a.cdr + b }
}
return b
}
おっと、ここで評価が遅延されることが思わぬ所でメリットになっています。
もし今回のような片方向リストが先行評価なら、結合時に片方のリストを全部辿らないといけません。しかし、評価が遅延されることで、結合時には最初の要素しか開ける必要がないのです。
なぜなら、最後の要素が見つかった時に、次のリストを見に行けば良いだけなのですから。
ではこれを使って、0~4, 5~1を結合してみましょう。
for n in (iterate(0){ $0 + 1 }.take(5) + iterate(5){ $0 - 1 }.take(5)) {
println(n)
}
<結果>
0
1
2
3
4
5
4
3
2
1
リストのリスト？
ちょっと唐突ですが、
リストを操作していると、ふとした瞬間リストのリストになってしまう時があります。
例えば、
"ムーンサイドへようこそ"
という文字列を、
"ムムーーンンササイイドドへへよよううここそそ"
という文字列に変換する関数moonsideを考えてみましょう。
例えば１文字を、その一文字を繰り返すリストにmapする方法があります。
// 要素1つのリストを作成する関数
func one<T>(value: T) -> List<T> {
return cons(value, .Nil)
}
func moonside(text: String, count: Int) -> String {
let characters = Array(text).toList
// おっと、リストのリストになってしまった。
let nested = characters.map { c in one(c) + one(c) }
おっと、nestedがリストのリストになってしまいました。
こんな時は「リストのリスト」をリストに、つまり平らにする関数を用意しましょう。
func flatten<T>(list: List<List<T>>) -> List<T> {
if let out_car: List<T> = list.car {
if let in_car: T = out_car.car {
return lazyCons(in_car) { flatten(cons(out_car.cdr, list.cdr)) }
} else {
return flatten(list.cdr)
}
}
return .Nil
}
これを使って、
func moonside(text: String) -> String {
let characters = Array(text).toList
let nested = characters.map { c in one(c) + one(c) }
let flat = flatten(nested)
return String(flat)
}
println(moonside("ムーンサイドへようこそ"))
<出力>
ムムーーンンササイイドドへへよよううここそそ
とシンプルに記述できます。
※ムーンサイドとはゲームmother2に登場する架空の都市の名前です。とても面白いゲームなので、興味がある方はWiiUのバーチャルコンソールでどうぞ http://www.nintendo.co.jp/wiiu/software/vc/jbbj/
ところで、moonside関数の中で、mapしてflattenするという一連の流れは結構定型処理な気がします。なので一つにまとめて、以下のようにすると便利です。
extension List {
func flatMap<U>(f: T -> List<U>) -> List<U> {
return flatten(self.map(f))
}
}
あれ？mapしてflattenするんだからmapFlattenじゃないの？と思うかもしれませんが、
flatten(self.map(f))
のところを普通に左から読むとflatMapですね（もちろん処理順序はmapが先です）
関数合成の処理順序を追う時は右から読みます。
このflatMapがあると見通しが良くなるので、moonsideをスッキリ整理してみると、
func moonside(text: String) -> String {
return String(Array(text).toList.flatMap { c in one(c) + one(c) })
}
となります。
何をしているのか分かりやすくなり、気持ち良いですね。
再び無限へ
部分から全体へ、そして無限へ戻す方法を用意しておきましょう。
extension List {
var cycle: List<T> {
return repeat(1).flatMap { _ in
return self
}
}
func cycle(n: Int) -> List<T> {
return repeat(1).take(n).flatMap { _ in
return self
}
}
}
少々トリッキーに映りますでしょうか？
repeat(1)の1という数値には特に意味はなく、ただ無限が欲しいだけですので気にしないでください。
注意すべきは、それぞれの要素（ここでは1）が全部selfに置き換わっている点です。
実際にはリストのリストになりますが、flatten処理が入るので、一列に並んだ状態になるわけです。
これを使えば、
println("-- repeat --")
for n in iterate(0, { $0 + 1 }).take(3).cycle(4) {
println(n)
}
<結果>
0
1
2
0
1
2
0
1
2
0
1
2
さらに、結合と組み合わせることで少し複雑な構造も作れますね
for n in (iterate(0){ $0 + 1 }.take(3) + iterate(3){ $0 - 1 }.take(3)).cycle.take(20) {
println(n)
}
<出力>
0
1
2
3
2
1
0
1
2
3
2
1
0
1
2
3
2
1
0
1
0, 1, 2, 1, ...と上がって下がってをずーっと繰り返すリストです。
やっぱりmap, filter, reduceは欲しいよね？
この辺はやっぱり欲しくなるので、用意してみましょう。
extension List {
func map<U>(f: T -> U) -> List<U> {
if let car = self.car {
return lazyCons(f(car)) { self.cdr.map(f) }
}
return .Nil
}
func filter(f: T -> Bool) -> List<T> {
if let car = self.car {
if f(car) {
return lazyCons(car) { self.cdr.filter(f) }
} else {
return self.cdr.filter(f)
}
}
return .Nil
}
func reduce<R>(var initial: R, combine: (R, T) -> R) -> R {
for value in self {
initial = combine(initial, value)
}
return initial
}
}
let natural = iterate(1){ $0 + 1 }
println("-- map --")
for n in natural.take(10).map({ $0 * $0 }) {
println(n)
}
println("-- filter --")
for n in natural.take(10).filter({ $0 % 2 == 0 }) {
println(n)
}
println("-- reduce --")
println(natural.take(10).reduce(0, combine: +))
<出力>
-- map --
1
4
9
16
25
36
49
64
81
100
-- filter --
2
4
6
8
10
-- reduce --
55
そんなにごつい実装でなくても定義できました。
そろそろ添え字が欲しくなりました？
ではzipで用意しましょう
Listを２種用意して、タプルとして結合する関数です
シンプルなのに、強力です。
func zip<T, U>(a: List<T>, b: List<U>) -> List<(T, U)> {
if let va = a.car, vb = b.car {
return lazyCons((va, vb)) { zip(a.cdr, b.cdr) }
}
return .Nil
}
添え字とは0から始まって1ずつ増える無限リストなのでzipでくっつけてしまいましょう。
let index = iterate(0){ $0 + 1 }
for (i, n) in zip(index, iterate(0, { $0 + 5 })).take(10) {
println("\(i) : \(n)")
}
<出力>
0 : 0
1 : 5
2 : 10
3 : 15
4 : 20
5 : 25
6 : 30
7 : 35
8 : 40
9 : 45
ちなみにどちらかの要素が末尾に達すると停止します。
もちろん、両方無限なら、zipの結果も無限です。
ついでに可能性も無限です。（それ、いいすぎ）
組み合わせを列挙する
組み合わせを総当たりで出す関数があると、便利な時があります。
例えば、1~9までのリストを２つ用意して、
(1, 1)
(1, 2)
(1, 3)
~略~
(2, 1)
(2, 2)
(2, 3)
~略~
(9, 7)
(9, 8)
(9, 9)
といった具合です。
これは例えば以下のように実装できます。
func pair<T, U>(lhs: List<T>, rhs: List<U>) -> List<(T, U)> {
return lhs.flatMap { lhsValue in
return rhs.map { rhsValue in
(lhsValue, rhsValue)
}
}
}
これを使って、九九一覧を出力してみましょう。
let natural = iterate(1){ $0 + 1 }
let ninenine = pair(natural.take(9), natural.take(9)).map { (a, b) in
return "\(a) x \(b) = \(a * b)"
}
for line in ninenine {
println(line)
}
<出力>
1 x 1 = 1
1 x 2 = 2
1 x 3 = 3
〜（略）〜
9 x 6 = 54
9 x 7 = 63
9 x 8 = 72
9 x 9 = 81
ベタに書く時と比べ、２重ループを取っ払うことが出来ました。
このような対応は必ずしも適切ではないケースも多いですが、こういうアプローチに初めて触れる人は新鮮に思うのではないでしょうか。
え？もうちょっと実用的な例が欲しいって？
では乱数なんてどうでしょうか？
簡単だけど、結構品質が良い擬似乱数生成には、xorshiftがあります。
擬似乱数は、これはシードさえ決まれば、あとは永遠に続きます。
これはまさに無限リストで綺麗に表現できそうです。
func xorshift(var x: UInt32, var y: UInt32, var z: UInt32, var w: UInt32) -> List<UInt32> {
var t = x ^ (x << 11)
x = y
y = z
z = w
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))
return lazyCons(w) { xorshift(x, y, z, w) }
}
for n in xorshift(24903412, 53346, 34, 24).take(30).map({$0 % 10}) {
println(n)
}
<出力>
2
2
0
4
8
5
0
9
4
4
9
5
6
9
2
2
0
2
2
7
2
3
8
4
0
3
5
0
1
4
いい感じです。
※ 剰余を使って数値を制限するのは、よくないケースがあります
ニュートン法で平方根は無限リスト！
誤差をだんだん減らしていく例では、ニュートン法があります。
リストを開けていくとその分だけ計算をして、最後の奴が一番精度が良いはずです。
func newton_sqrt(x: Double, a: Double) -> List<Double> {
let f = { x in (x + a / x) * 0.5 }
return lazyCons(x) { newton_sqrt(f(x), a) }
}
for n in newton_sqrt(2.0, 2.0).take(6) {
println(n)
}
<出力>
2.0
1.5
1.41666666666667
1.41421568627451
1.41421356237469
1.41421356237309
※こちらを参考にしています https://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/Programming/2005/note/6/Slide03.html
ネイピア数だって表現しちゃう！
自然対数の底は、以下の定義があります
lim_{t \to 0} (1 + t)^\frac{1}{t}
無限リストを使って、nをどんどん小さくすれば、収束の様子の一部を見ることができます！
func napiers_constant(n: Double) -> List<Double> {
let f = { t in pow(1.0 + t, 1.0 / t) }
return lazyCons(f(n)) { napiers_constant(n * 0.5) }
}
for n in napiers_constant(1.0).take(50) {
println(n)
}
<出力>
2.0
2.25
2.44140625
2.56578451395035
2.6379284973666
2.67699012937818
2.6973449525651
2.70773901968802
2.71299162425343
2.71563200016899
2.71695572946644
2.71761848233688
2.71795008118967
2.7181159362658
2.71819887772197
2.71824035193029
2.7182610899046
2.71827145910931
2.71827664376605
2.71827923610801
（略）
まとめ
いかがだったでしょうか。
無限リスト、いろいろ調べる前は、なんだかややこしくてとっつきにくかったのですが、実際に試しながらコードを書いてみると、意外に気持ち良く、とっても面白いものでした。
Swiftだとコードもとても短くて済みますし、
なによりplayground環境は素晴らしいです。
こういった練習にはもってこいですね！
もしまだ触れたことがない人であれば、是非一度戯れてみてはいかがでしょうか？
ちなみに、無限リスト、と銘打って記事を書きましたが、
他の名前としては、遅延ストリーム、とか、遅延評価リスト、とか単にストリームとか呼ばれたりします。
興味がある方は調べてみると、新しいものが見つかるかもしれません。
最後にこれまでのソースを参考までにあげて終わりにしたいと思います。
https://github.com/Ushio/Inifinity-List