関数型かんすうがたプログラミングの基本きほん

1導入どうにゅう

この講義こうぎでは、関数かんすうの適用てきようと式しきの評価ひょうかを中心ちゅうしんに計算けいさんを構成こうせいする関数型かんすうがたプログラミングを説明せつめいする。純粋関数じゅんすいかんすう、不変性ふへんせい、高階関数こうかいかんすう、参照透過性さんしょうとうかせいを定義ていぎし、これらが局所的きょくしょてきな推論すいろんに寄与きよする理由りゆうを解説かいせつする。

関数型かんすうがたと命令型めいれいがたは、相互排他的そうごはいたてきな分類ぶんるいではない。現実げんじつの言語げんごは両者りょうしゃの機能きのうを併用へいようすることが多おおく、問題もんだいに応おうじて状態更新じょうたいこうしんと純粋じゅんすいな計算けいさんを適切てきせつに配置はいちすることが重要じゅうようである。

2基本用語きほんようご

純粋関数じゅんすいかんすうPure functionとは、返値かえりちが引数ひきすうだけによって決定けっていされ、評価ひょうかによって外部がいぶから観察可能かんさつかのうな状態変化じょうたいへんかを生しょうじさせない関数かんすうである。

副作用ふくさようSide effectとは、返値かえりちの計算けいさんとは別べつに発生はっせいする、外部がいぶから観察可能かんさつかのうな変化へんかである。共有変数きょうゆうへんすうの更新こうしん、入出力にゅうしゅつりょく、例外れいがいの送出そうしゅつなどが該当がいとうする。

不変性ふへんせいImmutabilityとは、値あたいを生成せいせいした後あとにその内容ないようを変更へんこうしない性質せいしつである。変更後へんこうごの情報じょうほうが必要ひつような場合ばあいは、既存きそんの値あたいを改変かいへんせずに新あたらしい値あたいを生成せいせいする。

第一級関数だいいちきゅうかんすうFirst-class functionとは、他ほかの値あたいと同様どうように、引数ひきすう、返値かえりち、データ構造こうぞうの要素ようそなどとして扱あつかえる関数値かんすうちである。高階関数こうかいかんすうHigher-order functionとは、関数かんすうを引数ひきすうとして受うけ取とるか、関数かんすうを返値かえりちとして返かえす関数かんすうである。

参照透過性さんしょうとうかせいReferential transparencyとは、ある式しきを、その式しきの値あたいで置換ちかんしてもプログラムの観察可能かんさつかのうな振舞ふるまいが変化へんかしない性質せいしつである。

3純粋関数じゅんすいかんすうと不変性ふへんせい

たとえば、整数せいすうを $$1$$1 増加ぞうかさせる純粋関数じゅんすいかんすうは次つぎのように記述きじゅつできる。

increment(n) = n + 1

increment(3) は評価ひょうかするたびに $$4$$4 となり、その評価ひょうかは共有状態きょうゆうじょうたいを変更へんこうしない。これに対たいして、共有きょうゆうカウンタを更新こうしんしてから返かえす関数かんすうは、そのカウンタの現在値げんざいちに結果けっかが依存いぞんするため、純粋関数じゅんすいかんすうではない。

不変ふへんなリスト xs の先頭せんとうに $$x$$x を追加ついかする操作そうさは、xs を変更へんこうせず、$$x$$x と xs から新あたらしいリストを構成こうせいする。旧きゅうリストを参照さんしょうする他ほかの式しきの意味いみは、この操作そうさによって変化へんかしない。

4参照透過性さんしょうとうかせいと等式推論とうしきすいろん

式しき $$e$$e が値あたい $$v$$v に評価ひょうかされ、$$e$$e が参照透過的さんしょうとうかてきであるとする。このとき、プログラム内ないの $$e$$e を $$v$$v で置換ちかんしても観察結果かんさつけっかは変化へんかしない。この性質せいしつにより、式しきの変形へんけいを等式とうしきとして検証けんしょうする等式推論とうしきすいろんEquational reasoningが可能かのうになる。

ただし、入出力にゅうしゅつりょくそのものが不要ふようになるわけではない。関数型言語かんすうがたげんごは、効果こうかを明示めいじする型かたや構文こうぶん、または純粋じゅんすいな計算けいさんと効果こうかを伴ともなう境界きょうかいの分離ぶんりによって、必要ひつような入出力にゅうしゅつりょくを扱あつかう。

5高階関数こうかいかんすう

map(f, [])       = []
map(f, x :: xs)  = f(x) :: map(f, xs)

map は関数かんすう $$f$$f を引数ひきすうとして受うけ取とるため、高階関数こうかいかんすうである。リストの走査方法そうさほうほうを map に集約しゅうやくし、各要素かくようそへの処理しょりを $$f$$f として分離ぶんりできる。この分離ぶんりは処理しょりの再利用さいりようと合成ごうせいを促進そくしんする。

6命令型めいれいがたとの関係かんけい

命令型めいれいがたプログラミングは、代入だいにゅうなどの命令めいれいによる状態遷移じょうたいせんいを中心ちゅうしんに記述きじゅつする。関数型かんすうがたプログラミングは、式しきの評価ひょうかと関数適用かんすうてきようを中心ちゅうしんに記述きじゅつする。この相違そういは記述きじゅつの重点じゅうてんにあり、どちらか一方いっぽうだけが常つねに適切てきせつであることを意味いみしない。

たとえば、呼出よびだしごとに局所的きょくしょてきな可変配列かへんはいれつを使用しようし、その参照さんしょうを外部がいぶへ漏洩ろうえいさせず、呼出履歴よびだしりれきが観察結果かんさつけっかへ影響えいきょうしないなら、外部がいぶには純粋じゅんすいな関数かんすうとして提示ていじできる。

7要点ようてん

• 純粋関数じゅんすいかんすうは返値かえりちを引数ひきすうだけから決定けっていし、観察可能かんさつかのうな副作用ふくさようを生しょうじさせない。
• 不変性ふへんせいと参照透過性さんしょうとうかせいは、式しきを局所的きょくしょてきに推論すいろんするための基盤きばんとなる。
• 高階関数こうかいかんすうは、計算けいさんの共通構造きょうつうこうぞうと個別処理こべつしょりを分離ぶんりする。
• 実用的じつようてきなプログラムでは、純粋じゅんすいな計算けいさんと必要ひつような効果こうかを明確めいかくな境界きょうかいで統合とうごうする。

8次つぎに進すすむ講義こうぎ