【Common Lisp】
関数型で考えて手続き的に実装し直す考え方
（トップダウンとボトムアップの設計）

by
  • Common Lispで競技プログラミングに取り組むなかで、関数型の再帰的なコードは問題の構造を把握しやすいが、制限時間内に通らないケースも多いです。
  • そこで、再帰のトップダウン的な引数・戻り値・呼び出しスタックは、それぞれボトムアップの動的計画法に対応するように切り替えていく必要があります。
  • ただ、この変換は局所的な書き換えではなく、DP配列の次元・DP表のセル・ループ順序など、設計全体の組み直しになります。

関連記事

1. 関数で考えるトレーニング

AIがPythonやJavaScriptのコードを大量に生成できるようになったので、人間は何をプログラムしたらよいか思案していたら、関数型パラダイムに興味が湧いてきました1。
状態を持たず、問題の構造をそのまま式で表す書き方は、読みやすく、考えやすい。

そこでトレーニングとして、競技プログラミングの問題をCommon Lispで解いてみました。
ところが、すぐに気づいたのは、関数型で簡潔に書けても、それだけでは制約内に収まらないこと。
計算効率の問題を同時に解く必要があります。

「状態のないコードで問題の構造を考え、最後にパフォーマンスのために状態を持って回す」というギアチェンジが必要で、これを場当たり的にやるのではなく、いったん考え方を整理しておこうと思います。

1.1. 問題を「定義」する

プログラミングの問題を解くとき、最初にやることは問題の構造を把握することです。
このとき、短い関数を書いていくことが力を発揮します。

関数型で考えて手続的に実装する 関数型の考察 f(i) = i番目で終わる最大和 f(i) = max(a[i], f(i-1)+a[i]) 問題の構造＝コードの構造 再帰で問題を自然に分解 依存関係・状態・遷移が見えやすい 手続的な実装 dp[i] = max(a[i], dp[i-1]+a[i]) for i in range(1, n): … 配列＋ループで効率化 スタック不要・空間最適化も容易 ⚡ 考察は関数型で速く、実装は手続的に確実に

たとえば「部分列の最大和を求める」問題なら、

  • f(i) = i番目の要素で終わる部分列の最大和
  • f(i) = max(a[i], f(i-1) + a[i])

部分問題の依存関係が整理し、ベースケースがどこにあるかを関数の定義で対応させます2。
Common Lispで書くと、

(defun max-subarray-sum (a i)
  (cond 
    ((= i 0) (aref a 0))
    (t (max (aref a i)
           (+ (max-subarray-sum a (1- i))
              (aref a i))))))Code language: Lisp (lisp)

問題の定義が、ほぼそのままコードになっています。
「i番目で終わる最大和は、a[i]単体か、前の結果にa[i]を足したものの大きい方」という論理が、関数の構造として直接見えます。

1.2. 再帰と動的計画法（DP）

ただ、この再帰的なコードはそのまま提出すると、多くの場合に制限時間超過かスタックオーバーフローで落ちます。
理由は三つあります。

  • 1つ目は、スタック深さの制限です。
    Common Lispを含む多くの処理系では、再帰の深さに実用上の上限があり、入力サイズが 10^5 を超えると、素朴な再帰ではスタックが尽きます34。
  • 2つ目は、関数呼び出しのコストです。
    再帰呼び出しは、引数の保存、スタックフレームの確保、リターンアドレスの管理を毎回行います。
    ループと比べて定数倍のコストがかかり、タイトな制限時間では積み重なります。
  • 3つ目は、メモリ空間最適化の難しさです。

競技プログラミングでは「正しく解ける」と「制約内で動く」が同じ重さで要求されます。
計算順序を明示的に制御できるボトムアップの形でないと、どの値を捨てていいかが判断できません。

トップダウンで「この問題を解くには何が必要か」を自然に分解できるため、関数型の考察は前半を速くしますが、後半には別の設計が必要になります。

再帰の代わりとして使えるのが、「動的計画法（Dynamic Programming）」。

「DP」は、問題を小さな部分問題に分割し、その結果を表に記録しながら再利用することで、同じ計算を繰り返さずに効率よく解く手法です。

再帰的なメモ化解から始めることは広く使われているアプローチですが、とくに計算効率を意識するプログラミングでは、再帰よりもループ＋配列が好まれる傾向があります5。
そこで、「素朴な再帰を書いてからメモ化し、ボトムアップに変換する」という3ステップが定番で6。
再帰メモ化のままでは、DPの1次元圧縮、つまり dp[i][j] を dp[j] に落とすような最適化は適用しにくいからです7。
そこで再帰で書けた問題を、配列とループで底上げ（ボトムアップ）に書き直すことになります。

1.3. 引数と戻り値を状態とDP表に変える

先ほどの max-subarray-sum をボトムアップに変換するとこうなります。

;; After: DP配列に変換
(defun max-subarray-sum-dp (a)
  (let* ((n (length a))
         (dp (make-array n :element-type 'fixnum)))
    (setf (aref dp 0) (aref a 0))
    (loop for i from 1 below n
          do (setf (aref dp i)
                   (max (aref a i)
                        (+ (aref dp (1- i)) (aref a i)))))
    (reduce #'max dp)))Code language: Lisp (lisp)

引数 i が dp の添字になり、戻り値が (aref dp i) というセルに収まりました。
「f(i)はf(i-1)から作る」という依存関係が、ループの順序に代わります。

2. ケーススタディ：深さ優先探索を明示スタックに変える

木構造の深さ優先探索（DFS）も、再帰で自然に書ける処理です。

DFS：再帰 → 明示スタックへ 再帰DFS（Before） root A B C D 行き・帰りがけが自然に書ける ✕ 深い木でスタック超過 → 明示スタック（After） (root, -1, :pre) (A, root, :pre) (root, -1, :post) phase で行き/帰りを管理 ✓ 再帰スタックに依存しない 呼び出しフレーム → (node, parent, phase) タプルに変換 
;; Before: 再帰DFS（帰りがけで部分木のサイズを集約）
(defun dfs (graph node parent size)
  (setf (aref size node) 1)
  (dolist (child (aref graph node))
    (unless (= child parent)
      (dfs graph child node size)
      (incf (aref size node) (aref size child)))))Code language: Lisp (lisp)

行きがけと帰りがけの処理がそのまま書けます。

ただ、再帰呼び出しで解ききれないなら、自前でループとスタックで管理する必要があります。

この変換では、再帰の呼び出しスタックが「どこまで処理したか」を暗黙に覚えていた情報を、自前で持つために、phase という変数が必要になります。

;; After: 明示スタックで同じ処理
(defun dfs-iterative (graph root size)
  (let ((stack (list (list root -1 :pre))))  ; (node parent phase)
    (loop while stack
          do (destructuring-bind (node parent phase) (pop stack)
               (cond
                 ((eq phase :pre)
                  (setf (aref size node) 1)
                  (push (list node parent :post) stack)
                  (dolist (child (aref graph node))
                    (unless (= child parent)
                      (push (list child node :pre) stack))))
                 ((eq phase :post)
                  (dolist (child (aref graph node))
                    (unless (= child parent)
                      (incf (aref size node) (aref size child))))))))))Code language: Lisp (lisp)

(node parent phase) のタプルが、再帰の各フレームに対応しています。
phase が :pre か :post かで行きがけと帰りがけを切り分けており、スタックの深さに依存しなくなります。

2.1. 局所的な書き換えではない

状態の持ち方が変われば配列の形が変わり、計算順序が変わればループの構造が変わります。

solve(i, s) という再帰が出てきたら dp[i][s] を疑う、
rec(l, r) なら区間DPだ、

という読み替えは定跡として使えますが、その先にあるループの順序やデータ構造の選択まで変わります。

このため、結局コードのほぼ全体を書き直すことになります。
関数型の考察から始めても最終的な実装がまったく別の形になるわけです。

3. ケーススタディ：クエリの前処理で回答順を最適化する

たとえば、AtCoder ABC449E「A += v」は、長さNの整数列Aに対して、1からMのうち出現回数が最小の値を末尾に追加する操作を10^100回繰り返したあと、クエリで指定した位置の値を答える問題でした8。

クエリをまとめて処理する 長さNの数列、インデックス最大10¹⁸のクエリ 数列を実際に構築することは不可能 → フェーズ分割で対処 Phase 1 元の配列 index 1〜N Phase 2 補充区間 k順にFenwick Tree Phase 3 周期区間 (x-1) mod M + 1 設計の転換 ✕ クエリを1件ずつ探索 → ループ爆発・時間切れ → ✓ クエリをk順にバケット分類 → Fenwick Treeで一括回答

クエリのインデックスは最大10^18まであるため、数列を実際に構築するわけにはいきません。
問題の構造を素直に実装してみると、出現回数の最少値を毎回探すだけで二重ループが発生し、すぐに時間切れになります。

3.1. 最初の観察：フェーズ分割

観察すると、数列はいくつかのフェーズで構成されることがわかりました。

  • Phase 1: 元の配列（インデックス1〜N）
  • Phase 2: 出現数の少ない値を補充していく区間
  • Phase 3: 1〜Mが周期的に繰り返す区間

Phase 3以降は (x - 1) mod M + 1 で答えが出ます。
問題はPhase 2の処理です。

  • 「levelを一つずつ引き上げながら、閾値以下の出現数の値を順に追加する」方法で実装してみると、最悪ケースでN×M個の要素が必要になり、メモリが尽きました。
  • 答えだけをハッシュテーブルに記録する方針に切り替えてみると、今度はループのイテレーション数が多すぎて時間切れになりました。

部分的な修正では行き詰まり、「数列を構築してからクエリに答える」という発想から離れる必要がありました9。

3.2. 設計の転換

そこで、「1クエリずつ数列の中を探す」のをやめて、「クエリを先に分類してから、まとめて答える」形にします。

「クエリxの答えを求める関数」として考えていたものが、最終的には「クエリをkで分類し、kを増やしながらFenwick Treeで順位を問い合わせるループ」に変わりました。

(defun make-answers (N M A X)
  (let* ((A-ary          (to-fixnum-array A))
         (freqs          (frequencies M A))
         (sorted-freqs   (sorted-frequencies freqs))
         (values-ordered (values-in-frequency-order M freqs))
         (lengths        (lengths-after-addition N M sorted-freqs))
         (buckets        (make-array (1+ M) :initial-element '()))
         (answer-vec     (make-array (1+ (length X))
                                     :element-type 'fixnum
                                     :initial-element 0)))
    ;; 各クエリをkごとのバケットに分類する
    (loop for qid from 1
          for x in X
          do (let ((req (query->request x qid lengths)))
               (if (direct-answer-p req)
                   (setf (aref answer-vec (direct-answer-qid req))
                         (aref A-ary (direct-answer-index req)))
                   (push req (aref buckets (rank-request-k req))))))
    ;; kを1から順に処理しながらFenwick Treeを育てる
    (let ((tree (make-fenwick M)))
      (loop for k from 1 to M
            do (fenwick-update! tree (aref values-ordered (1- k)) 1)
               (loop for req in (aref buckets k)
                     do (setf (aref answer-vec (rank-request-qid req))
                              (fenwick-kth tree (1+ (rank-request-rank req)))))))
    (loop for qid from 1 to (length X)
          collect (aref answer-vec qid))))Code language: Lisp (lisp)

このように、途中の計算状態をデータとして持って、関数を回す必要があります。

クエリは (k, rank) という状態になり、呼び出し順序はkの昇順というループ順序になり、毎回の検索は一括処理になっています。
関数の引数が状態に、戻り値がDP表に、呼び出し順序がループ順序に対応した、典型的な変換です。

4. 設計の切替

このように関数型のトップダウン的な考察から、そのまま解けない問題も多いです。

設計の切替：対応表 関数型（隠れている） 手続的（明示する） 関数の引数 DP配列の次元（状態） 戻り値 DP表のセル 呼び出しスタック ループ順序 / 明示スタック 再帰的な再計算 メモ化 / 表計算 変換はコードの修正ではなく、設計全体の組み直し

そこで、トップダウンで考察したあとに、次の問いを立てることが大切だと気づきました。

  • 「この関数の引数のうち、答えを一意に決める最小の情報は何か」
  • 「その状態数と評価順序はどうなるか」
  • 「戻り値ではなく表に置いたら何になるか」

ここ起点として、ボトムアップの設計に切り替えていくのです。

関数型の考察を手続的な実装に落とすとき、基本的な見方はひとつです。
「関数型のコードが隠していたものを明示化する」こと。

具体的には次の四つの対応で整理できます。

関数型で隠れているもの手続的な実装で明示するもの
関数の引数DP配列の次元（状態）
戻り値DP表のセル
呼び出しスタックループの順序または明示スタック
再帰的な再計算メモ化または底上げの表計算

4.1. まとめ

関数型の考え方は考察のフェーズを速くします。
部分問題の依存関係を見つけ、状態と遷移を整理するとき、再帰的な定義はそのまま問題の構造を映します。

ただし競技プログラミングでは、最適な状態表現・データ構造・計算順序の設計が別途必要になります。
関数型のコードが隠していた引数・戻り値・呼び出しスタック・再計算を、それぞれ状態・DP表・ループ順序・メモ化または表計算に対応させる変換がそこで発生します。

この変換はコードを少し書き換えるのではなく、設計全体を組み直す作業です。
定跡を意識することで、考察と実装の間のギアチェンジが、場当たりではなく意識的な設計判断になります。

  1. 関数型プログラミングでは、副作用を排除し、状態を持たない純粋関数で処理を記述します。イミュータブルなデータと高階関数の組み合わせにより、並列化のしやすさや、コードの予測可能性が高まります。 – Perish or Flourish? A Holistic Evaluation of Large Language Models for Code Generation in Functional Programming
  2. この漸化式はKadane’s Algorithmとして知られており、1970年代後半にCarnegie Mellon大学のJay Kadane教授がO(n)で解いたことに由来します – Maximum subarray problem – Wikipedia
  3. SBCLでは末尾でない再帰の階乗関数を (fact 100000) で呼び出すとcontrol stack overflowが発生します。一方、末尾再帰版はTCOが適用されスタックを消費しません。 – Tail call optimization – CS Dartmouth
  4. Common LispのTCO（末尾呼び出し最適化）は言語仕様には含まれておらず、処理系依存です。SBCLは速度宣言時にTCOを適用しますが、相互再帰には効きません。CLISPは自己再帰のみTCOを実装しています。 – Tail Call Optimisation in Common Lisp Implementations
  5. TopCoderのred coderによる32件の解答を調べたところ、上位12件はすべてループ＋配列を使っており、メモ化再帰を使ったのは6件だったという調査があります。 – Why do top guys favor array-based versus recursive DP? – Codeforces
  6. 競技プログラマーの間では「再帰 → メモ化 → ボトムアップDP」の3段階変換はよく知られたアプローチです。 – How do you approach DP problems for which the recursive solution isn’t obvious? – Codeforces
  7. ローリング配列（rolling array）とも呼ばれるこの手法は、状態遷移が直前の行（または列）だけに依存するとき、配列全体を保持せず1行分だけを使い回すことで空間計算量をO(n×m)からO(m)に削減します。0/1ナップサック問題が典型例で、内ループを逆順に走査することで整合性を保ちます。 – Optimize Space Complexity for Dynamic Programming
  8. 問題文と制約の詳細はAtCoderの問題ページを参照してください。 – E – A += v（AtCoder Beginner Contest 449）
  9. 公式解説では、出現頻度を昇順にソートした配列を使って追加ブロックの開始インデックスを事前計算し、クエリをkごとのバケットに分類してFenwick Treeで順位を求めるアプローチが示されています。 – 解説 – AtCoder Beginner Contest 449