Common Lisp での多重リスト生成
（loopとmapcan）

by
  • Common Lispでリストを生成する方法として、loopマクロ、再帰とcons、mapcarとmapcan、dotimesとpushの4つのアプローチを比較しています。
  • loopはDSL的な構文で直感的に書けますが、Common Lisp固有の機能であり、S式の統一性の外側に別の構文規則を持ち込んでいます。
  • 再帰とconsやmapcarとmapcanはSchemeやHaskellと共通する考え方で、Lisp全般に通じる汎用的な発想です。
  • loopが標準採用された背景には、1980年代後半に理論的純粋さより現場での使いやすさを優先したCommon Lispの設計思想があります。

関連記事

1. 方法の比較

(1 2 3 4 5) のようなリストを作る方法は一通りではありません。
loop マクロ、再帰と cons、mapcar と mapcan、dotimes と push など、考え方の異なる複数のアプローチがあります。
書き方の違いを見ていくと、Lisp のリスト処理の構造が自然に浮かび上がってきます。

方法考え方他の Lisp との共通性
loopDSL で宣言的に書くCommon Lisp 固有
再帰 + cons値を積み上げる構造再帰Scheme、Clojure でも同じ
mapcar と mapcanリストを変換・結合する高階関数Scheme の map、Haskell の map と concatMap と共通
dotimes + push手続き的に積み上げるC の for に近い発想

Lisp らしさという観点では、再帰 + cons と mapcar + mapcan が他言語でも通じる考え方です。
loop は Common Lisp を書くうえで強力ですが、Scheme や Clojure には存在しない概念です。

短く意図が明確なら loop for ... collect、リスト変換を重ねる処理なら mapcar と mapcan、再帰の構造を見せたいなら labels + cons という選び方が自然です。

1.1. loop マクロ

loop は Common Lisp に標準で含まれるマクロです1。
評価前に通常の Lisp コードへ展開されます。
英語風の句を組み合わせる DSL（特定用途向けの小言語）的な構文を持っており、他の Lisp 方言にはほぼ存在しない Common Lisp 固有の機能です。

loop マクロ for i from 1 to 5 collect append collect 値をそのままリストに積む append 結果リストを連結して平らにする to / below 上限の含む・含まない ;; collect (loop for i from 1 to 5 collect i) ; => (1 2 3 4 5) ;; append (loop for i from 1 to 3 append (list i (* i i))) ; => (1 1 2 4 3 9) Common Lisp 固有のDSL構文 Scheme / Clojure には存在しない 
(loop for i from 1 to 5 collect i)
; => (1 2 3 4 5)Code language: JavaScript (javascript)

for i from 1 to 5 が変数 i を 1 から 5 まで動かし、collect が各ステップの値をリストに積み上げます。
to の上限は含まれます2。

上限を含めたくない場合は below を使います。

(loop for i from 0 below 5 collect i)
; => (0 1 2 3 4)Code language: JavaScript (javascript)

collect と append の違い

collect は値をそのまま追加します。
append は各ステップの結果がリストであることを前提に、それを連結します。

;; collect: 値をそのまま積む
(loop for i from 1 to 3 collect (list i (* i i)))
; => ((1 1) (2 4) (3 9))

;; append: 各ステップの結果リストを連結して平らにする
(loop for i from 1 to 3 append (list i (* i i)))
; => (1 1 2 4 3 9)Code language: PHP (php)

nconc は append の破壊的版で、元のリスト構造を変更しながら連結します。
速度が必要な場面で使いますが、副作用に注意が必要です3。

三重ループで直積を作る

i、j、k の全組み合わせ（三次元直積）を列挙するには、loop を入れ子にします。

(loop for i from 0 to 2 append
  (loop for j from 0 to 2 append
    (loop for k from 0 to 2 collect
      (list i j k))))Code language: JavaScript (javascript)

内側の collect が (i j 0) (i j 1) (i j 2) を作り、append が一段ずつ平らにします。
最終的に 27 要素のリストになります4。

条件フィルタリング

when と unless で条件付きの収集ができます5。

(loop for i from 1 to 10
      when (evenp i) collect i)
; => (2 4 6 8 10)Code language: JavaScript (javascript)

集約

sum、count、maximize、minimize など、集約操作も句として使えます6。

(loop for i from 1 to 5 sum i)
; => 15

(loop for i from 1 to 5 maximize i)
; => 5Code language: JavaScript (javascript)

複数の返り値

collect と集約を同時に使いたい場合は、into で中間変数に蓄積し、finally で返します7。

(loop for i from 1 to 5
      collect i into nums
      sum i into total
      finally (return (values nums total)))
; => (1 2 3 4 5)
;    15Code language: JavaScript (javascript)

loop のマクロ展開を確認する

loop が内部でどんなコードに変換されるかは macroexpand-1 で確認できます。

(macroexpand-1 '(loop for i from 0 to 2 collect i))

展開結果は処理系依存ですが、概念的にはこのような形になります。

(block nil
  (let ((result nil))
    (do ((i 0 (+ i 1)))
        ((> i 2) (nreverse result))
      (push i result))))Code language: JavaScript (javascript)

do、let、block など通常の Lisp 構文に展開されているのがわかります8。

1.2. 再帰と cons

cons はリストの先頭に要素を追加する基本操作です。

再帰と cons cons セル構造 1 → 2 → 3 (1 . (2 . (3 . nil))) cons で先頭セルを積み上げる Scheme / Clojure でも同じ考え方 labels + アキュムレータ (rec (1- i) (cons i acc)) n から減らしながら先頭に積む → 昇順 ;; 基本の cons (cons 1 ‘(2 3)) ; => (1 2 3) ;; labels パターン (labels ((rec (i acc) (if (= i 0) acc (rec (1- i) (cons i acc))))) (rec n nil)) append 版は末尾追加のたびに リストを走査 → 大きなリストに非効率 cons 版 + nreverse が定石 
(cons 1 '(2 3))
; => (1 2 3)

リストは内部的に (1 . (2 . (3 . nil))) という入れ子構造になっており、cons はその先頭セルを作ります9。

再帰を使うと、繰り返し処理ができます。
たとえば、appendで末尾に追加することで、連番のリストを生成できます。

(defun range (n)
  (if (= n 0)
      nil
      (append (range (- n 1)) (list n))))

(range 5)
; => (1 2 3 4 5)Code language: PHP (php)

しかし、この方法は非効率です。
append では、呼び出しのたびにリストの末尾を走査するからです。
小さなリストでは問題ありませんが、大きなリストには向きません。

末尾再帰とアキュムレータ

発想を転換して、逆順で追加していけば、appendではなく consを使えます。

(defun range (n)
  (labels ((rec (i acc)
             (if (= i 0)
                 acc
                 (rec (1- i) (cons i acc)))))
    (rec n nil)))

(range 5)
; => (1 2 3 4 5)Code language: PHP (php)

n から 1 ずつ減らしながら cons で先頭に積むと、自然に昇順のリストができます。
labels は関数内でだけ使えるローカル関数を定義する構文です。

Common Lisp でも SBCLなど多くの処理系で、末尾呼び出しは最適化されます10。
labels でローカル再帰関数を作り、結果を蓄積する変数としてアキュムレータを使う書き方は Lisp の慣用表現として広く使われます。

この考え方は Scheme でも同じで、named let を使えば次のように書けます。

(define (range n)
  (let loop ((i n) (acc '()))
    (if (= i 0)
        acc
        (loop (- i 1) (cons i acc)))))

構文は違いますが構造は同じです11。

1.3. mapcar と mapcan

mapcar と mapcan mapcar — 1対1変換 入力 1 2 3 f(x) = x² 出力 1 4 9 mapcan — 展開して連結 入力 1 → (1 1) 入力 2 → (2 4) 入力 3 → (3 9) nconc で連結 ⇒ (1 1 2 4 3 9) 入れ子にならない (mapcar #'(lambda (x) (* x x)) ‘(1 2 3 4 5)) ; => (1 4 9 16 25) (mapcan #'(lambda (x) (list x (* x x))) ‘(1 2 3)) ; => (1 1 2 4 3 9) 他言語との対応 mapcar Scheme map / Haskell map mapcan Scheme flatmap Haskell concatMap 他言語でも通じる汎用的な考え方

mapcar

mapcar はリストの各要素に関数を適用し、同じ長さのリストを返します。

(mapcar #'(lambda (x) (* x x)) '(1 2 3 4 5))
; => (1 4 9 16 25)Code language: PHP (php)

1+ など単引数の関数であればそのまま渡せます。

(mapcar #'1+ '(0 1 2 3 4))
; => (1 2 3 4 5)Code language: PHP (php)

「0 から n-1 のリストを 1 から n に変換する」という形で range を書くこともできます。

mapcan

mapcan は各要素に関数を適用した結果を nconc で連結します。
Scheme の flatmap に相当します12。

(mapcan #'(lambda (x) (list x (* x x))) '(1 2 3))
; => (1 1 2 4 3 9)Code language: PHP (php)

mapcar を使うと ((1 1) (2 4) (3 9)) という入れ子になりますが、mapcan は一段平らにします。

mapcan で直積を作る

先ほどの loop 三重ネストは mapcan と mapcar でも書けます。

(let ((xs '(0 1 2)))
  (mapcan (lambda (i)
            (mapcan (lambda (j)
                      (mapcar (lambda (k) (list i j k))
                              xs))
                    xs))
          xs))

内側が mapcar、外側 2 層が mapcan という構造は loop 版と同じです。
loop の collect が mapcar に、append が mapcan にそれぞれ対応しています。

1.4. dotimes と push

dotimes は指定回数だけ繰り返す手続き的なマクロです。
リストを走査する dolist と対になります13。

dotimes と push 処理の流れ (n=3) i=0: push 1 → result=(1) i=1: push 2 → result=(2 1) i=2: push 3 → result=(3 2 1) nreverse → (1 2 3) push = (setf x (cons v x)) の省略形 (defun range (n) (let (result) (dotimes (i n (nreverse result)) (push (1+ i) result)))) (range 5) ; => (1 2 3 4 5) 他のアプローチとの比較 loop 宣言的・読みやすい 再帰 + cons 関数型・汎用的 mapcar 変換特化・簡潔 dotimes + push 手続き的・C に近い 副作用を伴う処理に向く 
(defun range (n)
  (let (result)
    (dotimes (i n (nreverse result))
      (push (1+ i) result))))

(range 5)
; => (1 2 3 4 5)Code language: JavaScript (javascript)

push は (setf result (cons v result)) の省略形で、リストの先頭に要素を追加します。
先頭に積んでいくので、最後に nreverse で順序を正します。
nreverse は元のリスト構造を破壊的に反転します。

loop より低レベルで、C の for ループに近い書き方です。
手続き的に書きたいときや副作用を伴う処理が必要なときに使われます。

2. loop が示す Common Lisp の設計思想

loop マクロは、Lisp コミュニティの中でも賛否が分かれる存在です。
「Lisp らしくない」という批判は今も根強くあります。
その違和感の正体は、loop の構文が Lisp の基本原則と相容れない部分を持っているからです。

loop が示す Common Lisp の設計思想 Scheme 末尾再帰を保証 最小限の構文セット S式の統一性を維持 「正しい Lisp」 を追求 Common Lisp 多様な構文を標準化 産業実用を優先 loop など独自DSL採用 「使える Lisp」 を追求 loop の批判点 S式の外側に 独自構文規則を持込む for / from / collect… 採用された理由 意図が英文に近い形で 表現できる ANSI策定 1980年代後半 方言統合の過程で 実用性を優先

Lisp の構文はすべて (operator arg1 arg2 ...) という S 式で統一されています。
コードもデータも同じ構造で表現できるため、マクロがコードを自由に操作できます。
ところが loop の内部では for、from、collect、when といったキーワードが特別な意味を持ち、loop マクロ自身がそれを独自に解析します。
これは S 式の統一性の外側に、別の構文規則を持ち込んでいることになります14。

それでも loop が標準に採用されたのは、実際に書きやすく読みやすいからです。
loop for i from 1 to 10 when (evenp i) collect i は、意図を英文に近い形で表現できます。
再帰や mapcan の入れ子で同じことを書くより、コードの見た目と処理の意図が一致しやすい場面があります。

Common Lisp が ANSI 規格として策定された 1980 年代後半は、Lisp が研究用途を超えて産業での実用を目指していた時期です。
異なる処理系に散在していた方言を統合する過程で、理論的な純粋さより現場での使いやすさを優先する選択が重ねられました15。
loop はその象徴のひとつです。

Scheme が末尾再帰の保証や最小限の構文セットで「正しい Lisp」を追求したのとは対照的に、Common Lisp は「使える Lisp」として多様な道具を標準に抱え込みました。
loop の存在はその判断を体現しています。
どちらの設計が優れているかという問いに答えはなく、何を優先するかという価値観の違いです16。

  1. loop マクロの起源は Interlisp の Warren Teitelman が実装したイテレーション構文にさかのぼります。Lisp Machine Lisp と MacLisp を経由して Common Lisp 標準に採り込まれました。 – CLHS Section 1.1.2 – History
  2. for/as 句によるイテレーション制御の詳細な文法は CLHS Section 6.1.2.1 に定義されています。to・upto・below・downto・above・by など複数のキーワードが使えます。 – CLHS Section 6.1.2.1
  3. nconc は rplacd を使って最後のセルの CDR を書き換えます。同じリストを二度 nconc に渡すと循環リストが生成される危険があります。CLHS の例では (nconc x y) 後に x の値が変化することが示されています。 – CLHS: Function NCONC
  4. loop マクロは展開時に変数束縛を確立する let または lambda に相当する形式を生成します。変数の初期化順序はユーザーが指定した順に従うことが仕様で定められています。 – CLHS: 6.1.1.4 Expanding Loop Forms
  5. loop の条件句は if・when・unless の 3 種類が使えます。else 節と end によるネストにも対応しています。 – CLHS: Macro LOOP
  6. loop の集約句には collect・append・nconc（リスト系）と sum・count・maximize・minimize（数値系）があります。各句には ing 形（summing・collecting 等）の別名も存在します。 – CLHS Section 6.1.3
  7. into var を使うと loop はその値を自動で返さなくなるため、finally (return ...) で明示的に返す必要があります。loop-finish を使うと finally 節を実行しながら途中でループを終了できます。 – CLHS: Local Macro LOOP-FINISH
  8. loop の代替ライブラリとして iterate があります。loop に近い構文を持ちながら S 式の規則に従った設計になっており、独自のイテレーション構造を拡張定義できます。 – A Road to Common Lisp – Steve Losh
  9. car（先頭要素）と cdr（残りのリスト）という名前は、初期の Lisp が動いた IBM 704 のレジスタ構造に由来します。car は “Contents of Address part of Register”、cdr は “Contents of Decrement part of Register” の略です。 – cons – Wikipedia
  10. ANSI Common Lisp の仕様は末尾再帰の最適化（TCO）を処理系に要求していません。SBCL や Clozure CL は TCO に対応していますが、LispWorks や Allegro CL では引数の数や呼び出し構造によって最適化が適用されないケースがあります。 – Tail Call Optimisation in Common Lisp Implementations
  11. Scheme（R7RS）はすべての処理系に末尾再帰の最適化を義務付けています。「proper tail-recursive」と呼ばれるこの性質は、Steele と Sussman が設計した最初の Scheme インタプリタに由来し、アクターモデルの tail call と関数呼び出しが等価であるという観察から来ています。 – Revised7 Report on the Algorithmic Language Scheme
  12. mapcan が nconc を使うため、渡した関数が返すリストを後から変更すると予期しない結果になることがあります。関数内で list を使って毎回新しいリストを作るのが安全な使い方です。X3J13 は 1989 年に mapping 中の破壊的副作用に関する制限を追加しています。 – CLHS: Function MAPC, MAPCAR, MAPCAN…
  13. dotimes の構文は (dotimes (var count-form result-form) body) です。result-form はループ終了後に評価されて返り値になります。省略すると nil が返ります。 – CLHS: Macro DO, DO*
  14. loop のキーワードは通常の Lisp シンボルとして扱われますが、loop マクロが内部でそれらを解析する独自のパーサーを持っています。この設計は CLHS でも「ループ施設（The Loop Facility）」として独立した章に分離されており、仕様書自体がこの構文の特殊性を認識しています。 – CLHS: Macro LOOP
  15. 1981 年の DARPA スポンサードの会議を機に Symbolics、SPICE プロジェクト、NIL プロジェクト、S-1 Lisp プロジェクトが協力して Common Lisp の設計を開始。1986 年に ANSI 標準化委員会 X3J13 が発足し、ポータビリティの強化・CLOS・条件システム・イテレーション機能などの目標が追加されました。 – Common Lisp – Wikipedia
  16. Scheme は Guy L. Steele Jr. と Gerald Jay Sussman が設計した Lisp の方言で、レキシカルスコープ・レキシカルクロージャ・ファーストクラス継続・簡潔な構文を主要な貢献として挙げられます。Common Lisp もレキシカルスコープとクロージャは Scheme から取り込みましたが、末尾再帰の保証は採用しませんでした。 – Scheme (programming language) – Wikipedia