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

date2026-07-14document_iddoc_d7e77bd0e2008362b28f50668741e33bdescription純粋関数、不変性、高階関数、参照透過性を定義し、関数型プログラミングの基本と命令型プログラミングとの関係を説明する。prerequisitesdata/lecture/information/programming/introduction-to-programming.lecture.n.mdtype講義statusactive

informationprogramming-languageslecture

data/lecture/information/programming/introduction-to-programming.lecture.n.md

1導入どうにゅう

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

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

2基本用語きほんようご

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

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

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

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

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

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

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

text

increment(n) = n + 1

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

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

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

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

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

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

text

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

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

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

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

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

7要点ようてん

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

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

data/lecture/information/programming-languages/foundation/variable-binding-and-free-variables-basics.lecture.n.md

Functional Programming Fundamentals

data/lecture/information/programming/introduction-to-programming.lecture.n.md

1Introduction

This lecture explains functional programming, which organizes computation primarily through function application and expression evaluation. It defines pure functions, immutability, higher-order functions, and referential transparency and explains why these concepts support local reasoning.

Functional and imperative programming are not mutually exclusive categories. Practical languages often combine features from both, and effective designs place state updates and pure computations according to the needs of the problem.

2Basic Terms

A pure functionPure function is a function whose return value is determined only by its arguments and whose evaluation produces no externally observable state change.

A side effectSide effect is an externally observable change that occurs in addition to computing a return value. Updating a shared variable, performing I/O, and raising an exception are examples.

ImmutabilityImmutability is the property that a value's contents do not change after the value is created. When updated information is required, a new value is created without modifying the existing value.

A first-class functionFirst-class function is a function value that can be used like other values, including as an argument, return value, or element of a data structure. A higher-order functionHigher-order function is a function that receives a function as an argument or returns a function as its result.

Referential transparencyReferential transparency is the property that replacing an expression with its value does not change the program's observable behavior.

3Pure Functions and Immutability

For example, a pure function that increments an integer by one can be written as follows.

text

increment(n) = n + 1

Every evaluation of increment(3) produces $4$ , and the evaluation does not modify shared state. By contrast, a function that updates and returns a shared counter is not pure because its result depends on the counter's current state.

An operation that prepends $x$ to an immutable list xs constructs a new list from $x$ and xs without modifying xs. Consequently, the meaning of other expressions that refer to the old list does not change.

4Referential Transparency and Equational Reasoning

Suppose expression $e$ evaluates to value $v$ and $e$ is referentially transparent. Replacing $e$ with $v$ in the program then leaves its observable result unchanged. This property enables equational reasoningEquational reasoning, in which transformations of expressions can be verified as equations.

This does not make I/O unnecessary. Functional languages handle required I/O through types or syntax that make effects explicit, or by separating pure computations from boundaries that perform effects.

5Higher-Order Functions

text

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

map is a higher-order function because it receives function $f$ as an argument. It centralizes the traversal of a list while separating the operation on each element as $f$ . This separation facilitates reuse and composition.

6Relationship to Imperative Programming

Imperative programming describes computation primarily through state transitions caused by instructions such as assignments. Functional programming describes computation primarily through expression evaluation and function application. This distinction concerns emphasis; it does not imply that either approach is always preferable.

For example, an implementation may expose a pure function while using a mutable array local to each call, provided that no reference to the array escapes and no call history affects the observable result.

7Summary

A pure function determines its return value only from its arguments and produces no observable side effects.
Immutability and referential transparency provide a basis for local reasoning about expressions.
Higher-order functions separate common computational structure from specific operations.
Practical programs integrate pure computations and necessary effects at explicit boundaries.

8Next Lecture

data/lecture/information/programming-languages/foundation/variable-binding-and-free-variables-basics.lecture.n.md