CodeIQ MAGAZINE

フィボナッチ数列で学ぶ「Swift」の関数型プログラミング

2015.07.21 Category：技術コラム Tag：Swift ,フィボナッチ ,ヤフー ,数学

「プログラマのための数学勉強会」を主催しているヤフー佐野@taketo1024さんに、注目の新言語「Swift」と「関数型プログラミング」について執筆いただきました。

数学好きなプログラマの皆さん必見の、フィボナッチ数列題材レポートです！ by 馬場美由紀（CodeIQ中の人）

フィボナッチ数列を題材に、Swiftと関数型プログラミングを学ぼう

どうも、@taketo1024こと佐野です。

僕はヤフーで iOS アプリ開発をしており、今年から「プログラマのための数学勉強会」を隔月で開催しております。

7月24日には第4回の開催を予定しており、これまでCodeIQさんには第2回、第3回とも素晴らしいレポート記事を書いていただきましたので、そのお返しに僕からも数学とプログラミングに関する記事を書かせていただくことにしました。

この記事ではみんな大好きな「フィボナッチ数列」を題材に、Appleの新言語「Swift」の「関数型プログラミング」を学んでいきましょう。

フィボナッチ数列とは？

フィボナッチ数列はプログラマにとっても馴染みあるものだと思います。1, 1から始まって「前の二つを足して次の項を作っていく」ルールによって作られる数列です。

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]

各項がその前の2項の和になっていますね。プログラマのスキルを試す問題として「フィボナッチ数列を関数として実装せよ」は定番ですよね。これは再帰呼び出しを使えば１行で書けます：

func fib(n: Int) -> Double {
    return (n < 2) ? 1.0 : fib(n - 1) + fib(n - 2)
}

f(0) = 1, f(1) = 1で、f(2) = f(1) + f(0) = 2, f(3) = f(2) + f(1) = 5と次々求まっていくのが分かると思います。
（このやり方だと関数呼び出しが2^nのオーダーで膨れ上がるので、実用上は値をキャッシュする必要があります）

フィボナッチ数列は数がどんどん足されて無限に大きくなっていきますが、この「増え方」には実は秩序があるのです。隣り合う項の比をとって見ると、

0: 1 / 1 = 1
1: 2 / 1 = 2
2: 3 / 2 = 1.5
3: 5 / 3 = 1.666... 
...

という具合で、これを続けていけば：

4: 1.6
 5: 1.625
 6: 1.61538461538462
 7: 1.61904761904762
 8: 1.61764705882353
 9: 1.61818181818182
10: 1.61797752808989
11: 1.61805555555556
12: 1.61802575107296
13: 1.61803713527851
14: 1.61803278688525
...

と、何やら1.618...みたいな値に落ち着いていきそうです。

実はこの極限は黄金比φ = 1.618033988749894...になるのです。

黄金比とは？

この図を見たことある方は多いでしょう。縦横の比が黄金比になっている長方形は、短辺側の正方形を取り除いても同じ比率の長方形が残るのが特徴です。

簡単な比の計算から、黄金比φを求めることができます。

から、

$φ(φ - 1) = 1 \Leftrightarrow φ^2 - φ - 1 = 0$

というφに関する2次方程式が得られ、解の公式から、

と求まります。ここで±と値が二つありますが、片方はマイナスになるので正の方が黄金比です。実際に計算してみると

(1.0 + sqrt(5)) / 2 // 1.618033988749895

となります。

フィボナッチ数列の比は黄金比へと近づいていく。このことは漸化式をいじって極限を取ることで示すこともできるのですが、もっと深くこの事実を洞察して、その内奥に潜む構造を見てみることにしましょう。

フィボナッチ数列の一般化～関数型アプローチ

まずフィボナッチ数列生成のルール：

$a_{n+2} = a_{n+1} + a_n$

は守りつつ、初期値は自由に取れるようにした「一般のフィボナッチ数列」を考えてみましょう。例えば数列を3, -1 から始めることにすれば、「前の二つを足して次の項を作っていく」ルールによって、

3, -1, 2, 1, 3, 4, 7, 11, 18, 29, ...

が得られます。「一般のフィボナッチ数列」の実装は、初期値を数列の関数のパラメータに含めることで：

func fib(a0: Double, _ a1: Double, _ n: Int) -> Double {
    switch n {
    case 0:  return a0
    case 1:  return a1
    default: return fib(a0, a1, n - 1) + fib(a0, a1, n - 2)
    }
}

とできますが、これだと上の数列は：

fib(3, -1, 0) // 3
fib(3, -1, 1) // -1
fib(3, -1, 2) // 2
fib(3, -1, 3) // 1
...

と書いていかねばならず、全然数列って感じがしません。オブジェクト指向であればここで「フィボナッチ数列クラスを作ってコンストラクタに初期値を…」となりますが、ここでは「関数型」のアプローチを取ってみましょう。こうです：

func Fib(a0: Double, _ a1: Double)(_ n: Int) -> Double {
    switch n {
    case 0:  return a0
    case 1:  return a1
    default: return Fib(a0, a1)(n - 1) + Fib(a0, a1)(n - 2)
    }
}

さっきと何が変わったのでしょう？ fibが大文字のFibになって、2番目と3番目の引数がカッコで分離されただけです。ところが、こうすることで：

let f = Fib(3, -1)
f(0) // 3
f(1) // -1
f(2) // 2
f(3) // 1
f(4) // 3
f(5) // 4
f(6) // 7

と、Fibに(3, -1)を与えることでそれを初期値とするフィボナッチ数列fが得られたのです。このFibは元の3変数関数fibの「カリー化」と呼ばれるもので、フィボナッチ数列（を表す関数）を返す関数（つまり高階関数）となります。

Fibはこう書いても同じです：

func Fib2(a0: Double, _ a1: Double) -> ((Int) -> Double) {
    return { n in
        let f = Fib2(a0, a1)
        switch n {
        case 0:  return a0
        case 1:  return a1
        default: return f(n - 1) + f(n - 2)
        }
    }
}

二つの初期値を取り、戻り値の型は「Intを引数にとってDoubleを返す関数」つまり数列です。Fib2の中では、戻り値となる関数（クロージャ）を即座に返しています（{ n in ... }の部分がクロージャです）。
このクロージャの中身は元の3変数関数fibとほぼ同じですね。

こうみるとFibはフィボナッチ数列の「コンストラクタ」のようなものだと思えるでしょう。「だったら最初からクラスでいいじゃないか」と思われるかと思いますが、まぁひとまずクラスのことは忘れてついてきてください。

数列はベクトルか？

さてFibで作られる一般のフィボナッチ数列のうち、(1, 0)で始まるものと(0, 1)で始まるものの二つを取ってみます：

let e1 = Fib(1, 0)
let e2 = Fib(0, 1)

また普通のフィボナッチ数列f = Fib(1, 1)も取り、その列を並べてみると：

e1: [1, 0, 1, 1, 2, 3,  5,  8, 13, 21, 34, ...]
e2: [0, 1, 1, 2, 3, 5,  8, 13, 21, 34, 55, ...]
f : [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...]

なんということでしょう、f = e1 + e2 になっているではありませんか！（縦に数字を足してみてください）さっきの f = Fib(3, -1) の場合はどうでしょう。e1, e2 をそれぞれ 3倍、-1倍した数列を並れば、

3 * e1 : [3,  0,  3,  3,  6,  9, 15,  24,  39,  63, 102, ...]
   -e2 : [0, -1, -1, -2, -3, -5, -8, -13, -21, -34, -55, ...]
     f : [3, -1,  2,  1,  3,  4,  7,  11,  18,  29,  47, ...]

やはりf = 3 * e1 - e2になっています！

今、形式的に関数を足したり定数倍したりしたような書き方をしましたが、実はこれも実装できちゃうのです。先に数列の型を定義しておきます。数列とは「自然数をとって実数を返す関数」であると見て：

typealias NumSeq = (Int) -> Double

次に数列同士の和を定義します。Swift では演算子のオーバーロードがサポートされているので、遠慮なく使っていきましょう：

func +(f: NumSeq, g: NumSeq) -> NumSeq {
    return { f($0) + g($0) }
}

これはつまり、f + gという関数を、(f + g)(n) = f(n) + g(n)によって定義したということです。クロージャによって与えられた f, gを包み込んだ新しい関数を作っているわけです。$0 は f + gに渡されるn: Intを表しています。こうして「数列と数列の和」＝「二つの関数から一つの関数を返す関数」が定義できました。

同様に実数倍も：

func *(a: Double, f: NumSeq) -> NumSeq {
    return { a * f($0) }
}

と定義します。これで：

let f = Fib( 3, 4)
let g = Fib(-1, 3)
let h = f + g  // Fib(2, 7) と同じ

のように、数列がただの2次元ベクトルのように扱えるようになりました（Fibを無視すればただの成分の和に見えますよね？）。もはやNumSeqの実体は関数であったことを忘れてしまいそうですが、

h(0) // 2
h(1) // 7
h(2) // 9
...

で、ちゃんと数列になっています。高校では数列とベクトルは全く別のものとして習ったと思いますが、ここではもう開き直って、「数列とは値を返す機能つきのベクトルだ！」と思うことにしましょう。

フィボナッチベクトルは黄金比の方向へ

話を戻せば「フィボナッチ数列の比の極限は黄金比」になることをみようというのでした。このことは数列をベクトルと見れば、(1, 1) を次々に進めていけば「黄金比の方向」へと向かっていくということなのです。

「次々進める」とはどういうことでしょう。ここで f = Fib(1, 1)に対して次のような変換を考えます：

       f: [1, 1, 2, 3,  5,  8, 13, 21, 34,  55,  89, ...]
shift(f): [1, 2, 3, 5,  8, 13, 21, 34, 55,  89, 144, ...]

上下をジグザグに見ていけば分かる通り、shift(f)は「fの並びをひとつ手前にズラした形」になっています。これを分かりやすくかけば：

       f: [f(0), f(1), f(2), f(3), f(4), f(5), f(6), ...]
shift(f): [f(1), f(2), f(3), f(4), f(5), f(6), f(7), ...]

となります。このshift(f)の方も数列で、nを与えれば「fにおけるn + 1番目の値」が返ってきます：

shift(f)(0) // = f(1) = 1
shift(f)(1) // = f(2) = 2
shift(f)(2) // = f(3) = 3
shift(f)(3) // = f(4) = 5
shift(f)(4) // = f(5) = 8
...

つまりshift(f)は「f をひとつ進めた数列」なのです（返ってくる値が手前にズレたということは、元の関数で入力を次に進めたものが返ってくるということです）。実装は数式の通りです：

func shift(s: NumSeq) -> NumSeq {
    return { s($0 + 1) }
}

なぜこんなものを考えるかというと、フィボナッチ数列は最初の2項を並べたベクトルとして表現すると、2項目より先の様子が見えなくなります。そこでfをn回shiftすることで、f(n), f(n + 1)が最初の2項にやって来るので、n 項目の値がベクトルとして見えるようになるというわけです。

さて、フィボナッチ数列(1, 1)に対して次々shiftを作用させた結果は次の通りです：

(1, 1) -> (1, 2) -> (2, 3) -> (3, 5) -> (5, 8) -> (8, 13) -> (13, 21) -> ...

もうお分かりの通り、このベクトルの傾きが f(n + 1) / f(n) で「フィボナッチ数列の比」です。「フィボナッチ数列の比の極限が黄金比」だということは、(1, 1) を次々 shift させて行けばどんどん黄金比の方向に進んでいくということです！

実際に計算してみると、

let f = Fib(1, 1)
let g = (shift^10)(f)
g(1) / g(0)  // 1.617977528089888

となり、冒頭で求めた10番目の比の値と一致しています。10番目でもうこれだけ極限値に近いんですから、かなり収束が速いことが分かります。これでフィボナッチ数列の比が黄金比に向かっていく様子が想像できるようになったと思います！

※ ちなみに上の「n回合成する」という演算子^は次のように実装しました（3次の高階関数）：

func ^(F: (NumSeq -> NumSeq), k: Int) -> (NumSeq -> NumSeq) {
    return (k == 0) ? {$0} : { (F^(k - 1))(F($0)) }
}

黄金等比数列

ところで、最初から「黄金比の方向」のフィボナッチ数列を取ったらどうでしょう。つまり(1, φ)を初期値として数列を作っていくのです：

let φ = (1.0 + sqrt(5)) / 2.0 // 1.618033988749895
let f = Fib(1, φ)

f(1) / f(0) // 1.618033988749895
f(2) / f(1) // 1.618033988749895
f(3) / f(2) // 1.618033988749895
f(4) / f(3) // 1.618033988749895
f(5) / f(4) // 1.618033988749895
...

極限を取るまでもなく、比は常に黄金比となっています。隣り合う項の比が一定の数列といえば…？そうです「等比数列」です。 (1, φ)から始まるフィボナッチ数列は、黄金比を公比とする等比数列になるのです！

より詳しく、公比φの等比数列は：

$\{a_n\} = \{φ^n\} = \{1, φ, φ^2, φ^3, ...\}$

と書けますが、これをフィボナッチ数列の漸化式：

$a_{n+2} = a_{n+1} + a_n$

に代入してみると：

$φ^{n+2} = φ^{n+1} + φ^{n} \Leftrightarrow φ^2 = φ + 1$

で、この式は長方形から黄金比を求めたときの2次方程式ではありませんか！

逆に言えば黄金比とは、一般のフィボナッチ数列のうち、それが特別に等比数列となるときの公比だったわけです（もちろん普通のフィボナッチ数列を見れば分かる通り、一般にこの漸化式を満たす数列は等比数列にはなりません）。

線形代数で種明かし

ここまで次々と式が出てきて何かうまく言いくるめられたように思われたかもしれないので、これまでの議論を線形代数の視点から解き明かしていきましょう。

まず「数列はベクトルだ」と言いましたが、これは数学的に全く正しい主張です。「一般のフィボナッチ数列全体」は、f1 = Fib(1, 0)とf2 = Fib(0, 1)を基底とする2次元のベクトル空間となります。

数列空間は一般には有限次元とはならないのですが、この空間を定めていた漸化式：

$a_{n+2} = a_{n+1} + a_n$

によって、空間は2次元に制限されるのです。この漸化式が線形であるところがポイントで、定数項や2乗の項が入ってきたりすると上手くいきません。

次にshiftという作用を考えましたが、これはこのベクトル空間における線形変換になっています。

(1, 0), (0, 1)の移り先はそれぞれ(0, 1), (1, 1)なので、先ほどの基底に関する行列表示は：

$A = \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right)” title=”$

です。この変換の固有方程式が：

$\det(φI - A) = φ^2 - φ - 1 = 0$

で、これは黄金比φを求めるときに出てきた方程式ですよね。つまり、φはフィボナッチ数列空間における線形変換shiftの固有値だったのです。この固有値に対する固有ベクトルは、

$shift(f)(n) = f(n + 1) = φ \cdot f(n)$

となるので、これはすなわち等比数列：

$\{φ^n\} = \{1, φ, φ^2, φ^3, ...\}$

です。もう一方の固有値はφ¯=1−φで、その固有ベクトルは：

$\{\bar{φ}^n\} = \{1, \bar{φ}, \bar{φ}^2, \bar{φ}^3, ...\}$

です。こうして2つの1次独立な固有ベクトルが得られたので、これを新たな基底としてフィボナッチ数列を表せば、一般項：

$a_n = \frac{φ^n - \bar{φ}^n}{\sqrt{5}}$

フィボナッチ数列は0, 1, 1, 2, 3, 5, 8, ...と自然数が並ぶ列ですが、この一般項は分子にも分母にも思いっきり無理数が出てきているので不思議ですよね。φとφ¯が絶妙のバランスで互いに打ち消しあって、自然数であることを保っているのです。またこの式を見れば、比の極限が黄金比に収束していくことも分かるはずです！

一般のフィボナッチ数列がshiftによってどう進んでいくかを考えると、以下のような図が得られます。ほとんどの数列は黄金比の方向に進んでいくのですが、唯一それに直交する(1,φ¯)の方向だけはshiftのたびに振動しながら0に収束していきます。shiftが線形変換としてフィボナッチ数列空間に作用する様子が見えたでしょうか…!?

まとめ

今回は関数型プログラミングの特徴である「関数を直接操作の対象として扱う」ということを理解するために、数列を「自然数を取り実数値を返す関数」と定義し、そこに和や実数倍という演算を入れ、さらに shift という関数に対する作用を導入してその動きを見ていきました。

実際のコードではこのようなことはすべきでなく struct として数列型を定義した方がいいとは思いますが、数学における「関数空間」がプログラムにおける「関数」と対応する形で実装できるのは面白いかなと思い、敢えてこのような形にしてみました。

今回のサンプルコードは[コチラ]です。さらに余力のある方は「トリボナッチ数列」で：

以上 「関数型プログラミングで学ぶフィボナッチ数列」 でした！

最後に

僕は大学で数学を専攻していました。当時は好きで勉強していただけで将来誰かの役に立つなどとは考えていませんでした。ところが昨今のIT界隈では3Dゲーム開発のオープン化や機械学習・AIの発展に伴って、俄かにプログラマたちの数学への意識が高まってきているようです。

それならばと開催した勉強会では毎回定員を超える人数の応募があり、さらに「私も数学の話がしたい！」と発表者も次々に集まってきてくれて、想像を超える盛り上がりに驚きつつ嬉しく思っています。

プログラマの中には数学を超えられない壁のように感じ「あのとき真面目に勉強していなかった仇が…」と後悔をしている人もいるようです。

個人的にはもっと気楽に、数学も技術も必要と興味の赴くままに学んでいけばいいと思いますし、元々二つはとても近いところにあるので「プログラマは数学を学ぶということに関しては有利だ」ということを伝えていければと思っています。

この記事を読んで数学に興味を持たれた方、気軽に「プログラマのための数学勉強会」に足を運んでみてください。最後まで読んでいただきありがとうございました！

ブログ: [Imaginary & Imaginative]
Twitter: [@taketo1024]

**CodeIQ高校　教育実習生 Lala*さんからの問題**

「プログラマのための数学勉強会」バックナンバー

自分の書いたコードを誰かに評価されたいエンジニアは、けっこう多い？

ITエンジニアのための実務スキル評価サービス『CodeIQ』で出題されている「コード銀行」問題に挑戦すると、あなたのコードが評価されます。

評価(1)出題者からの評価　　⇒評価フィードバック例を見る

企業ではたらくという観点からあなたのコードをチェックします
フィードバックされた観点をふまえてコードを書くと世の中の企業にとって「いいコード」が書けるようになります

評価(2)企業からの評価　　⇒評価フィードバック例を見る

「あなたと一緒にはたらきたい」という企業からスカウトが届きます
あなたのコードが社会でどこまで通用するか、リアルな評価が得られます

CodeIQ MAGAZINE

CodeIQ MAGAZINE

フィボナッチ数列で学ぶ「Swift」の関数型プログラミング

フィボナッチ数列を題材に、Swiftと関数型プログラミングを学ぼう

フィボナッチ数列とは？

黄金比とは？

フィボナッチ数列の一般化～関数型アプローチ

数列はベクトルか？

フィボナッチベクトルは黄金比の方向へ

黄金等比数列

線形代数で種明かし

まとめ

最後に

**CodeIQ高校　教育実習生 Lala*さんからの問題**

「プログラマのための数学勉強会」バックナンバー

自分の書いたコードを誰かに評価されたいエンジニアは、けっこう多い？

■関連記事

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQご利用にあたって

関連サイト

CodeIQ MAGAZINE

CodeIQ MAGAZINE

フィボナッチ数列で学ぶ「Swift」の関数型プログラミング

フィボナッチ数列を題材に、Swiftと関数型プログラミングを学ぼう

フィボナッチ数列とは？

黄金比とは？

フィボナッチ数列の一般化 ～ 関数型アプローチ

数列はベクトルか？

フィボナッチベクトルは黄金比の方向へ

黄金等比数列

線形代数で種明かし

まとめ

最後に

CodeIQ高校 教育実習生 Lala*さんからの問題

「プログラマのための数学勉強会」バックナンバー

自分の書いたコードを誰かに評価されたいエンジニアは、けっこう多い？

■関連記事

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQご利用にあたって

関連サイト

フィボナッチ数列の一般化～関数型アプローチ

**CodeIQ高校　教育実習生 Lala*さんからの問題**