Lispで学ぶ再帰とリスト

Lispで学ぶ再帰とリスト操作：基本から実践まで

1. はじめに

Lisp（リスプ）は、リストを中心としたデータ構造と再帰処理が得意なプログラミング言語 です。
特に、コードがデータとして扱える特性（メタプログラミング）や関数型プログラミングの強力なサポート など、特徴的な機能を持っています。

本記事では、Lispの基本的なデータ構造「リスト」の操作と、再帰処理を活用したプログラミング について解説します。

---

2. Lispの基本構文

LispのコードはすべてS式（S-expression） で記述されます。

2.1. Lispの基本構造

(+ 3 5)  ; 足し算（出力: 8）
(* 2 4)  ; 掛け算（出力: 8）
(setq x 10)  ; 変数xに10を代入

---

3. リスト操作の基本

Lispの最大の特徴は、リストを主要なデータ構造として扱う ことです。

3.1. リストの作成

(setq my-list '(1 2 3 4 5))  ; リストの作成

3.2. car と cdr

• car はリストの最初の要素を取得
• cdr はリストの最初の要素を除いた残りを取得

(car '(10 20 30))  ; 出力: 10
(cdr '(10 20 30))  ; 出力: (20 30)

3.3. リストの結合

(append '(1 2) '(3 4))  ; 出力: (1 2 3 4)
(cons 0 '(1 2 3))       ; 出力: (0 1 2 3)

---

4. 再帰を使ったリスト処理

Lispでは、ループよりも再帰 を多用するのが一般的です。

4.1. リストの長さを求める

(defun list-length (lst)
  (if (null lst)
      0
      (+ 1 (list-length (cdr lst)))))

(list-length '(a b c d))  ; 出力: 4

4.2. リストの要素をすべて2倍にする

(defun double-list (lst)
  (if (null lst)
      nil
      (cons (* 2 (car lst)) (double-list (cdr lst)))))

(double-list '(1 2 3 4))  ; 出力: (2 4 6 8)

4.3. リストの要素を反転する

(defun reverse-list (lst)
  (if (null lst)
      nil
      (append (reverse-list (cdr lst)) (list (car lst)))))

(reverse-list '(a b c d))  ; 出力: (d c b a)

---

5. 高階関数（mapcar と reduce）

Lispには、リストを効率よく処理するための関数（高階関数） が用意されています。

5.1. mapcar（リスト全体に関数を適用）

(mapcar #'1+ '(1 2 3 4))  ; 各要素に1を加える -> (2 3 4 5)
(mapcar (lambda (x) (* x x)) '(1 2 3 4))  ; 各要素を2乗 -> (1 4 9 16)

5.2. reduce（リストを畳み込み処理）

(reduce #'+ '(1 2 3 4))  ; 合計値を計算 -> 10
(reduce #'max '(5 2 8 3)) ; 最大値を取得 -> 8

---

6. Lispで簡単なゲームを作る（数当てゲーム）

最後に、Lispで簡単な数当てゲーム を作成してみましょう。

(defun guess-the-number ()
  (let* ((target (+ 1 (random 100)))  ; 1~100のランダムな数
         (guess -1))
    (format t "1から100の間の数を当ててください！~%")
    (loop until (= guess target) do
      (format t "あなたの予想: ")
      (setq guess (parse-integer (read-line)))
      (cond ((< guess target) (format t "もっと大きい数です！~%"))
            ((> guess target) (format t "もっと小さい数です！~%"))))
    (format t "正解です！~%")))

実行すると、プレイヤーが1～100の間で数を予想し、正解するまで繰り返し入力を求められます。

---

7. まとめ

項目	内容
リスト操作	car, cdr, append, cons でリストを操作
再帰	リスト長の計算、要素の変更、リストの反転
高階関数	mapcar（要素ごとの処理）と reduce（畳み込み処理）
実践編	Lispで簡単な数当てゲームを作成

Lispは、シンプルな構文と強力な再帰・リスト処理機能 により、効率的なプログラミングが可能 です。
ぜひ、Lispを活用して、より高度なプログラムに挑戦してみてください！