（18/11/29 追記）
おまけにジェネレーターを使ったパターンを追加しました。
初投稿です。もっと良い方法があればご指摘頂けるとありがたいです。
Kotlinでリスト操作の楽しさに気づきハマっているのですが、
フィボナッチ数列のリスト作るのって意外と面倒！？と思ったので書いてみました。
作るもの
- フィボナッチ数列のリスト
- イミュータブルなリスト
- 値の範囲は 0～100
- 0, 1 を初期値に取るタイプ（再帰関数は使いません）
とりあえずwhile文で作ってみる
何も考えずに押し入れに布団を押し込むが如く、リストに値を押し込んで作ってみました。
val fibList = mutableListOf(0, 1)
while (true) {
val nextValue = fibList[fibList.lastIndex-1] + fibList.last()
if (nextValue > 100) break
fibList.add(nextValue)
}
昔ながら感のある書き方ですね、せっかくなので以下のように改善したいです。
- while文は使いたくない
- 添字アクセスも使いたくない
- リストをイミュータブルにしたい
リスト操作でイミュータブルに
ミュータブルリストの生成は以下のようにイミュータブルに変えられるはず。
val mlist = mutableListOf<Int>()
(1..5).forEach {
mlist.add(it * it)
}
// 実際に初期化する際は MutableList(5) { it * it } でＯＫですね。
こやつを、
val list = (1..5).map { it * it }
このように。
こちらの方が簡潔で、副作用も無くなっていいですよね。
フィボナッチ数列もこう変えられるはず。
無限シーケンス
「0～100までの値の範囲で作る」で while の代わりに使えるのが無限シーケンス。
Kotlin では generateSequence 関数で無限の長さのシーケンスを作れます。
Iterable<T> は即時評価されますが、Sequence<T> は遅延評価するため無限を表現できます。
generateSequence { 1 }.forEach(::print)
これで無限ループとなり永遠に 11111... と表示されます。
while と同じく使い方を誤ると危ない、という部分は変わりませんね。
初期値を元に値を変化させていきたい場合は、こちらを使います
generateSequence(初期値) { 加工式 }
第二引数のラムダ式に初期値が渡り、以降はラムダ式の結果が次のラムダの引数となります。
generateSequence(1) { it * 2 }
とすれば、[1, 2, 4, 8, 16, 32, 64...] という無限シーケンスができるわけですね。
フィボナッチ数列
実際に無限シーケンスとリスト操作関数を使ってフィボナッチ数列を作ってみました。
val fibList = generateSequence(0 to 1) { (a, b) -> b to (a + b) } // (1)
.map { it.first } // (2)
.takeWhile { it <= 100 } // (3)
.toList() // (4)
- 無限シーケンスで
0 to 1を初期値に、フィボナッチ数列の隣り合う値のペアを作っていく。
[0 to 1, 1 to 1, 1 to 2, 2 to 3, 3 to 5, 5 to 8...]となる。 - ペアから左値のみ取り出す。
[0, 1, 1, 2, 3, 5, 8...] - 要素の値が100以下のもののみ残し、有限シーケンス化。
-
Sequence<T>をList<T>に変換
出力
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
上手くいきました。
Pair を使うところが少し残念ですが、目標は達成できました。
おまけ
ラムダで Pair を返す必要があるところや、map { it.first } とする必要があるところが微妙なので、２引数を初期値とする generateSequence も作ってみたいと思います。
generateSequence は Sequence<T>#iterator() をオーバーライドした GeneratorSequence<T> というクラスのオブジェクトを生成しているようです。
真似して最小限にクラスとそのオブジェクトを返す関数を定義してみます。
// ２引数を初期値とする無限シーケンス
class GeneratorSequence<T : Any>(
private val firstValue: T,
private val secondValue: T,
private val getNextValue: (T, T) -> T
) : Sequence<T> {
override fun iterator() = object : Iterator<T> {
var prevItem = firstValue
var nextItem = secondValue
var callCount = 0
fun calcNext(): T {
val (prev, next) = nextItem to getNextValue(prevItem, nextItem)
prevItem = prev
nextItem = next
return nextItem
}
override fun next(): T {
callCount++
return when (callCount) {
1 -> firstValue
2 -> secondValue
else -> calcNext()
}
}
override fun hasNext() = true
}
}
作るのが少し面倒ですが、
前回、前々回の結果を内部で保持して、ラムダの２つの引数として渡しています。
// ２引数を初期値とする無限シーケンスを生成する関数
fun <T : Any> generateSequence(
firstSeed: T,
secondSeed: T,
nextFunction: (T, T) -> T
): Sequence<T>
= GeneratorSequence(firstSeed, secondSeed, nextFunction)
作った関数でフィボナッチ数列を作ってみます。
val fibList = generateSequence(0, 1) { a, b -> a + b }
.takeWhile { it <= 100 }
.toList()
最初よりスッキリ書けました。
やっぱりリスト操作は直観的に書けて気持ちいいですね！
ジェネレーターを使ったパターン
Kotlin1.3 よりジェネレーターである sequence が追加されていましたね。
しかもなんと、公式にフィボナッチ数列リストを作るパターンがそのまま載ってました Σ（・□・；）
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/sequence.html
もはやほぼ丸パクリして、２つの初期値を取る generateSequence関数を sequence を使って書く直してみました。
fun <T : Any> generateSequence(
firstSeed: T,
secondSeed: T,
nextFunction: (T, T) -> T
): Sequence<T> = sequence {
var terms = firstSeed to secondSeed
while (true) {
yield(terms.first)
terms = terms.run { second to nextFunction(first, second) }
}
}
めっちゃ簡単！早く気づいとけよ自分！