狠狠撸

蹿颈产蝉を読む～意図と意味を分ける～
chiguri

大仰なタイトル
?これはHaskellにおけるフィボナッチ数列の定義 > fibs = 0:1:zipWith (+) fibs (tail fibs) について、
?今からなにを説明するのか
?どの順で説明するのか
?を考えながら説明するものです。
?詳しい人ほど、全部いっぺんに話しますが、私の頭はそんなにメモリはありません。順序よく。

注意
?n番目、については基本0-originで行きます。
?別に1-originでもいいですけど、些末事です。
?そんなことにこだわるくらいならこのスライド閉じましょう。

まず
?愚直なn番目のフィボナッチ数を計算するコード fib(0) = 0 fib(1) = 1 fib(n+2) = fib(n)+fib(n+1) を書いておきます。
?0番目は0、1番目は1、2番目以降は2つ前と1つ前を足したものです。
?このコード、愚直にこのまま実装すると当然遅いですが、これが大元です。まずは定義に立ち返る。

fibsの定義
?fibsの定義は、関数じゃなくてリストです。 fibs = 0:1:zipWith (+) fibs (tail fibs)
?「fibsは0番目は0、1番目は1と続いて、残りはfibsと fibsの一つ後ろの列を足し算で合わせた残り」
?再帰的なのでちょっとぴんときません。「なんでfibsがそこで使えるの？」といったところです。

fibsと、それの指す内容
?fibsはフィボナッチ数列であるという意図です。 fibs = 0:1:zipWith (+) fibs (tail fibs)
?もっというと、fibsは「フィボナッチ数を0番目から並べたもの」です。
?とりあえずfibsはそういうものだ、と思うことにします。

フィボナッチ数を 1番目から並べたもの
?fibsの意図からすると、1番目から並べたものは次のものです。 1:zipWith (+) fibs (tail fibs) = tail fibs
?fibsの先頭を省いただけです。
?fibsがもし適切にフィボナッチ数を0番目から並べたものであれば、これは確かに1番目から並べたものです。

2番目から並べたもの
?当然ですが、2番目から並べたものは次の通り。 zipWith (+) fibs (tail fibs)
?fibsとtail fibsの意図は先ほど説明しました。
?fibs：フィボナッチ数を0番目から並べたもの
?tail fibs：フィボナッチ数を1番目から並べたもの
?つまり、「2番目から並べたもの」は、「0番目から並べたもの」と「1番目から並べたもの」を「足して並べたもの」になります。

大まかな図
0
1
1
2
3
5
8
1
1
2
3
5
8
1
2
3
5
8

フィボナッチ数の定義とすると
0
1
1
2
3
5
8
1
1
2
3
5
8
1
2
3
5
8
2つ前
1つ前
2番目以降

定義そのまま
0
1
1
2
3
5
8
1
1
2
3
5
8
1
2
3
5
8
fib(n)
fib(n+1)
fib(n+2)

?計算過程は、こんなつたない図よりも、 @fumieval さんの書いた図 https://twitter.com/fumieval/status/529973251875688448 の方が断然わかりやすいです。
?是非見ましょう。
?最初の二つが定義されれば、次の要素は前二つから計算できるので、全体が定義できる、ということがわかりやすいです。

意図から記号へ
?fibsの定義を、記号的にいじってみます。 fibs = 0:1:zipWith (+) fibs (tail fibs)
?右辺のfibsを定義によって一段階剥がしてみます。 0:1:zipWith (+) (0:1:zipWith (+) fibs (tail fibs)) (tail (0:1:zipWith (+) fibs (tail fibs))) = 0:1:zipWith (+) (0:1:zipWith (+) fibs (tail fibs)) (1:zipWith (+) fibs (tail fibs)) = 0:1:1:zipWith (+) (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs))

fibsの数の増え方がヤバい
?最初の定義には二つ、一段階展開すると四つ???
?足し算もzipWithをやったものを足してる。
?元の定義通りだと思えば、当たり前といえば当たり前。
?展開する、というのは関数の再帰呼び出しみたいなものだから。

浮かぶ疑問
?Q：遅くないの？計算したら無限ループとかにならないの？
?A：再帰的定義だけど、リストの前から順に計算して必要なところまで進めるから大丈夫です。
?前から順に計算する部分が@fumieval さんの図

遅延評価
?一般にHaskellの処理系は遅延評価を採用している。
?しなくてもいいらしいけど、してる。
?fibsの5番目が必要なら、「前から順に」5番目まで計算する。
?残りは「続きはこんな計算」と覚えておき、必要になったら計算する。＝計算を遅延させる。

遅延評価でのfibsの動き
?fibsは定義の中でfibsを使っているけれど、fibsが指しているのは値なので、右辺で使われたfibsは計算で作られた値を指しています。
?残りの計算では次の値を取り出して、の繰り返し。
?以下、計算過程を図で表示します。なお、図中では、リストを下のように表します。
?0:1:？（何かリストが続く）を表している。
0
1
?

fibsの作られる過程 fibの定義
0
fibs
1
zipWith (+) fibs (tail fibs)

fibsの作られる過程 fibsをその値で書き換える
0
fibs
1
zipWith (+) (tail )

fibsの作られる過程 tailの計算：リストを一つ進める
0
fibs
1
zipWith (+)

fibsの作られる過程値を取り出し、矢印を進める
0
fibs
1
zipWith (+) (0: ) (1: )

fibsの作られる過程 zipWithを進めてリストを作る
0
fibs
1
zipWith (+)
1

fibsの作られる過程値を取り出し、矢印を進める
0
fibs
1
1
zipWith (+) (1: ) (1: )

fibsの作られる過程 zipWithを進めてリストを作る
0
fibs
1
1
zipWith (+)
2

後は分かるね？
?もう次は想像できましたね？次に1と2が取り出されて矢印を進めて、???を繰り返します。
?つまり、実際の「次の値」の計算はzipWith (+)による計算一回分に過ぎませんから、計算量としては全然大したことがないわけです。
?単純な繰り返し＋α程度。
?意図通り、二つ前の要素と一つ前の要素を見るようにうまく定義されている。

終わりに
?今回は、fibsの定義について
?どういう考えで作られているかという「意図」と
?どう動くのかという「意味」と
を分けて説明しました。
?記号を相手にするときは、「意図」と「意味」を分けながら考えましょう。
?意図を表せていないならどうしようもない。
?意味がそぐわないなら、どうそぐわないかを考える。

?実際には「意味」から「意図」を取らなければならないことが多々あります。
?undocumentedな実装
?なぜかなにをやりたいのか全然分からない回答
?その場合でも、全体の成す意図は分かっていることが多いので、フローを元に全体の意図を分割しましょう。
?ちなみに、意味が分からない（ものの解釈をしようがない）のならどうしようもありません。

あなたの説明は意図と意味を分けていますか？

参考：記号的に表示した計算の流れ
?0:1:zipWith (+) fibs (tail fibs)

fibsを展開（どの部分まで計算したかを覚える）
?0:1:zipWith (+) fibs (tail fibs) = 0:1:zipWith (+) (0:1:ここから先) (tail (0:1:ここから先))

zipWithを進める（tailはスキップしている）
?0:1:zipWith (+) fibs (tail fibs) = 0:1:zipWith (+) (0:1:ここから先) (tail (0:1:ここから先)) = 0:1:1:zipWith (+) (1:ここから先) (ここから先)

決定した部分で進行
?0:1:zipWith (+) fibs (tail fibs) = 0:1:zipWith (+) (0:1:ここから先) (tail (0:1:ここから先)) = 0:1:1:zipWith (+) (1:ここから先) (ここから先) = 0:1:1:zipWith (+) (1:1:ここから先) (1:ここから先) 次は1だとわかったから矢印を進めた

zipWithを進める
?0:1:zipWith (+) fibs (tail fibs) = 0:1:zipWith (+) (0:1:ここから先) (tail (0:1:ここから先)) = 0:1:1:zipWith (+) (1:ここから先) (ここから先) = 0:1:1:zipWith (+) (1:1:ここから先) (1:ここから先) = 0:1:1:2:zipWith (+) (1:ここから先) (ここから先)

狠狠撸

蹿颈产蝉を読む

More Related Content

蹿颈产蝉を読む