関数型言語入門：副作用のないプログラミング

「同じ入力なら、必ず同じ出力」— 参照透過性の力と最古の関数型言語 Lisp、そしてフィボナッチ数列とハノイの塔で学ぶ漸化式・再帰・メモ化

関数型言語とは

多くのプログラミング言語は命令型です — 「変数に代入せよ」「繰り返せ」という命令を上から順に実行して、状態を書き換えながら進みます。関数型言語は別の考え方をします。プログラムを「式の評価」として組み立て、数学の関数のように「入力を受け取って出力を返す」ことだけをする関数を部品にするのです。

関数型言語では、関数そのものが値です。変数に入れられ、引数として渡せ、戻り値として返せます（こうした関数を第一級関数（first-class function）と呼びます）。「関数を受け取る関数」「関数を作って返す関数」が、ごく普通の道具として使われます。

副作用がない、とは：参照透過性

ここで核心の概念が出てきます。副作用とは、関数が「戻り値を返す」以外に行う仕事のことです — グローバル変数の書き換え、画面への出力、ファイルへの書き込み。副作用がなく、入力以外の外部の状態にも依存しない関数は、いつ・何回・どこで呼んでも、同じ入力に対して必ず同じ出力を返します。この性質を参照透過性（referential transparency）と呼びます。

利点は実感しやすいものばかりです。第一に、テストが簡単です — 入力と出力だけ見ればよく、「事前にどんな状態にしておくか」を気にせずに済みます。第二に、理解が局所的で済みます — 関数呼び出しの前後で世界が変わらないので、コードを部分ごとに読めます。第三に、並行処理で安全です — 共有された状態を書き換えないので、複数の処理を同時に走らせても壊れません。

「関数の意味が、入力と出力の関係だけで決まる」— 本サイトの形式手法のコンテンツを読んだ方には、見覚えのある考え方のはずです。「事前条件・事後条件で契約を書く」という発想と同じです。副作用が少ないほど、入出力の契約は書きやすく、検証しやすくなります。

Lisp：最古の関数型言語

関数型言語の元祖が Lisp です。1958 年に John McCarthy が考案し、今も使われている高級言語としては FORTRAN に次ぐ古さです。Common Lisp・Scheme・Clojure といった方言が現役で使われています。

Lisp の構文は驚くほど小さく、S 式（S-expression）— (関数引数引数 ...) という括弧の式 — だけでできています。そしてこの形はリストというデータ構造そのものでもあります。コードとデータが同じ形をしているため、「プログラムを生成するプログラム」が自然に書けます。

;; S 式: (関数引数1 引数2 ...) — 構文はこれだけ (+ 1 2) ; => 3 (* (+ 1 2) 4) ; => 12 (if (< 1 2) "yes" "no") ; => "yes"

以降のコード例には方言のひとつ Common Lisp を使います。

漸化式：小さい問題から値を定める

漸化式（recurrence relation）とは、n 番目の値や大きさ n の問題を、それより小さい番号・規模の値を使って定義する式です。「答えを直接書く」のではなく、「既に分かっている小さな答えから、次の答えをどう作るか」を規則にします。

1. 初期条件（計算を止められる既知の値）

F(0)=0, \qquad F(1)=1

2. 漸化規則（小さい問題から次の値を作る規則）

F(n)=F(n-1)+F(n-2), \qquad n \ge 2

漸化規則だけでは値は決まりません。小さい番号へ戻る規則だけでは出発点がないため、計算は戻り続けます。初期条件を組み合わせて、初めてすべての値が一意に定まります。

漸化式は数学上の定義で、再帰（recursion）は関数が自分自身を呼び出してその定義を計算するプログラム上の仕組みです。密接に対応しますが同じものではありません。再帰関数には、計算を止める基底条件と、呼び出すたびに問題を基底条件へ近づける規則が必要です。

漸化式の「初期条件」は再帰関数の「基底条件」に、漸化規則は「より小さい引数での再帰呼び出し」に対応します。この対応を見つけると、数学的な定義をコードへ素直に移せます。

例題：n 番目のフィボナッチ数

フィボナッチ数列 0, 1, 1, 2, 3, 5, 8, 13, … は、「前の 2 つの和が次の項になる」数列です。数学では漸化式で定義されます：F(0) = 0、F(1) = 1、F(n) = F(n−1) + F(n−2)。

関数型言語の魅力がここに表れます。この数学の定義が、ほぼ字面のままコードになるのです。

;; 漸化式をそのまま書き写した定義（Common Lisp） ;; F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) (fib 10) ; => 55

if が「場合分け」、再帰呼び出しが「漸化式の右辺」にそのまま対応しています。仕様（数学の定義）と実装の距離が、これ以上ないほど近い書き方です。ただし、この素朴な定義には重大な問題が潜んでいます。

問題：同じ計算の爆発

(fib 5) の呼び出しの木: (fib 5) ├─ (fib 4) │ ├─ (fib 3) │ │ ├─ (fib 2) ... │ │ └─ (fib 1) │ └─ (fib 2) ... └─ (fib 3) ├─ (fib 2) ... └─ (fib 1) (fib 3) を 2 回、(fib 2) を 3 回 — 同じ計算が何度も繰り返される

呼び出しの木を描いてみると、(fib 3) が 2 回、(fib 2) が 3 回 — 同じ計算が何度も現れています。n が大きくなると重複は指数的に増え、計算量はおよそ O(1.62ⁿ)。fib 40 あたりから、待ちきれないほど遅くなります。

メモ化：計算した結果を覚える

解決策は単純です。一度計算した結果を表に覚えておき、同じ引数が来たら計算せずに表から返す — これをメモ化（memoization）と呼びます。

;; メモ化版: 計算済みの結果をハッシュ表に覚えておく（Common Lisp） (let ((table (make-hash-table))) (defun fib-memo (n) (or (gethash n table) ; 表にあれば、それを返す (setf (gethash n table) ; なければ計算して表に入れる (if (< n 2) n (+ (fib-memo (- n 1)) (fib-memo (- n 2)))))))) (fib-memo 100) ; => 354224848179261915075 — 一瞬で返る

各 n の計算は 1 回きりになり、計算量は O(1.62ⁿ) から O(n) に落ちます。fib 100 でも一瞬です。

メモ化が安全にできるのは、fib に副作用がなく、同じ入力なら必ず同じ出力が返るからです。表から取り出しても、計算し直しても、答えは同じ — 参照透過性が「結果を使い回してよい」ことを保証しています。呼ぶたびに結果が変わるような関数では、こうはいきません。

正直な注意をひとつ。メモ化の表への書き込みは、内部的には状態の変化（副作用）です。しかし外から見た入出力の関係は変わらないため、「見かけの純粋さを保つ最適化」として関数型の世界で広く使われています。Clojure には関数を 1 行でメモ化する memoize が標準で備わっているほどです。

課題：ハノイの塔を再帰で考える

ハノイの塔は、大きさの異なる円盤を3本の棒の間で移すパズルです。最初はすべての円盤が出発の棒Aに、大きいものを下にして積まれています。補助の棒Bを使いながら、同じ順序の塔を目的の棒Cへ移します。

3 段のハノイの塔（初期状態）: [=] | | [===] | | [=====] | | +-------------+ +-------------+ +-------------+ A: 出発 B: 補助 C: 目的地目標: すべての円盤を A から C へ移す

1回の操作で移せる円盤は1枚だけ。

動かせるのは、それぞれの棒の一番上にある円盤だけ。

小さい円盤の上に、それより大きい円盤を置いてはいけない。

n段の塔で一番大きい円盤をAからCへ移すには、まず上のn−1段をAからBへ退避させる必要があります。最大の円盤をCへ1回で移した後、退避したn−1段をBからCへ移します。同じn−1段の問題が2回現れるため、最小手数は次の漸化式で表せます。

\begin{aligned} T(0) &= 0, \\ T(n) &= T(n-1) + 1 + T(n-1) \\ &= 2T(n-1) + 1 \qquad (n \ge 1). \end{aligned}

漸化式を一段ずつ展開する

ここでいう「展開」は、式の中に現れる小さい段数の項を、同じ漸化式で置き換えることです。まず3段で確かめます。最初の置き換えでは2段の場合を1段の場合へ、次の置き換えでは1段の場合を0段の場合へ変えます。括弧の外の係数は、括弧内のすべての項に掛かる点に注意してください。

\begin{aligned} T(3) &= 2T(2) + 1 \\ &= 2\bigl(2T(1) + 1\bigr) + 1 \\ &= 4T(1) + 2 + 1 \\ &= 4T(1) + 3 \\ &= 4\bigl(2T(0) + 1\bigr) + 3 \\ &= 8T(0) + 4 + 3 \\ &= 8 \cdot 0 + 7 \\ &= 7. \end{aligned}

一般の段数でも同じです。1回置き換えるたびに段数は1減り、外側の係数は2倍されます。同時に、各段階の「最大の円盤を1回動かす」という操作も、重みを倍にしながら積み重なります。段数と同じ回数だけ置き換えると、0段の初期条件へ到達します。

\begin{aligned} T(n) &= 2T(n-1) + 1 \\ &= 2^2T(n-2) + (2 + 1) \\ &= 2^3T(n-3) + (2^2 + 2 + 1) \\ &\ \vdots \\ &= 2^nT(0) + \left(2^{n-1} + \cdots + 2 + 1\right), \\ T(0)=0 &\ \Longrightarrow\ T(n) = \sum_{k=0}^{n-1} 2^k. \end{aligned}

最後に残る和に名前を付けます。この和を2倍した式から元の式を引くと、途中の項がすべて相殺されます。最後に加わった項と最初の1だけが残るため、和を求められます。

\begin{aligned} S &= 1 + 2 + 4 + \cdots + 2^{n-1}, \\ 2S &= \phantom{1 + {}}2 + 4 + \cdots + 2^{n-1} + 2^n, \\ 2S-S &= 2^n - 1, \\ S &= 2^n - 1, \\ \therefore\quad T(n) &= 2^n - 1. \end{aligned}

置き換えのたびに係数が2倍されるため、答えには2の累乗が現れます。最後に1を引く形になるのは、各段階で加わる1回分を、重みを倍にしながら足した結果です。公式を暗記するのではなく、「小さい問題へ置き換える操作」を追うと式の形が見えてきます。

$T(n)=2^n-1$

上で求めた閉じた式に値を代入すると、3段なら7回、10段なら1,023回です。伝説に登場する64段では18,446,744,073,709,551,615回となり、段数が1増えるたびに必要な操作はほぼ2倍になります。

課題

必須課題：0以上の整数nを受け取り、n段のハノイの塔をAからCへ移すための最小手数を返すCommon Lisp関数 hanoi-moves を、再帰的な関数として作成してください。例：hanoi-moves(3) は7、hanoi-moves(10) は1,023を返します。

発展課題：上で導いた閉じた式をCommon Lispで表す別関数 hanoi-moves-closed-form も作成し、再帰版と同じ値になることを確認してください。

ヒントを表示する

ヒント：必須課題では閉じた式や expt を直接使いません。0段なら0回、円盤を1枚減らした問題を2回解き、その間に最大の円盤を1回動かす、という漸化規則をコードにします。

解答例を表示する

解答1：漸化式を使う再帰関数

;; n 段のハノイの塔を移す最小手数を返す（Common Lisp） (defun hanoi-moves (n) (check-type n (integer 0 *)) (if (= n 0) 0 (+ (* 2 (hanoi-moves (- n 1))) 1))) (hanoi-moves 1) ; => 1 (hanoi-moves 3) ; => 7 (hanoi-moves 10) ; => 1023

0段なら手数も0になる基底条件と、円盤を1枚減らした問題を2回解く再帰部分が、漸化式をそのまま表しています。再帰呼び出しでは段数が必ず1減るため、有限回で基底条件に到達します。

ここで区別したいのは、値を計算する関数の呼び出し回数と、パズルを実際に動かす工数です。hanoi-moves の再帰呼び出しは段数に比例しますが、実際に円盤を移動する操作は上で導いた回数だけ必要です。

解答2：閉じた式を使う関数

;; 展開後の閉じた式 T(n) = 2^n - 1 を使う（Common Lisp） (defun hanoi-moves-closed-form (n) (check-type n (integer 0 *)) (1- (expt 2 n))) (hanoi-moves-closed-form 3) ; => 7 (hanoi-moves-closed-form 10) ; => 1023 (= (hanoi-moves 10) (hanoi-moves-closed-form 10)) ; => T（同じ答え）

Common Lispの expt は累乗を計算し、1- は値から1を引きます。したがって (1- (expt 2 n)) が、上で導いた閉じた式に直接対応します。再帰版と結果を比較すれば、課題の検算にも使えます。

ただし、この関数には自己呼び出しがないため、再帰関数を作る必須課題の代わりにはなりません。また、ソースコードが1つの式でも、大きな整数の累乗と結果の生成まで常に一定時間になるわけではありません。

まとめ

関数型言語は「式の評価」でプログラムを組む。核心は副作用のなさ＝参照透過性（同じ入力なら必ず同じ出力）。

利点：テストが簡単・理解が局所的・並行処理で安全。

Lisp は 1958 年生まれの最古の関数型言語。S 式ひとつの構文で、コードとデータが同じ形をしている。

漸化式は初期条件と漸化規則で値を定める数学上の定義。再帰関数では基底条件と自己呼び出しに対応する。フィボナッチの重複計算はメモ化で O(n) にできる。

ハノイの塔の最小手数は T(n) = 2T(n−1) + 1 = 2ⁿ−1。再帰関数で手数を計算できるが、実際の移動工数は段数に対して指数的に増える。