Common Lisp のリスト分配束縛
（loop と destructuring-bind）

by

関連記事

1. Common Lispの分配束縛

Common Lisp では、リストの要素を複数の変数に割り当てる「分配束縛（destructuring bind）」があります。

;; 局所的な極値検出
(defun local-extrema (lst)
  (loop for (prev x next) on lst
        while (and x next)
        when (and (< prev x) (< next x))
          collect (list :local-max x)
        when (and (> prev x) (> next x))
          collect (list :local-min x)))

(local-extrema '(4 6 6 1 4 5 1))
;=> ((:LOCAL-MIN 1) (:LOCAL-MAX 5))Code language: Lisp (lisp)

loop マクロ内の分配束縛は歴史が古く、その後に独立したマクロ destructuring-bindが追加されました1。

分配束縛の「destructure」は、「破壊（destructing）」ではなく、「構造をほどく」「構造に従って分解する」という意味です。
つまり、リストや木構造を、その形に合わせて変数へ割り当てる、ということです。

1.1. 3つの比較まとめ

観点loop の分配束縛destructuring-bindmultiple-value-bind
対象リスト（走査中）リストvalues による多値
使う場面ループ内で各要素を分解ループなしで1回分解多値を返す関数の呼び出し後
&optional / &key使えない使える使えない
要素・値が足りないときnil で補うエラーをシグナルnil で補う
余分な要素・値捨てるエラーをシグナル捨てる
ネスト対応対応非対応

2. loop の分配束縛とは

通常の loop では for x in list のように1変数でリストを走査します。

ただし、「入れ子のリスト」、つまり木構造では、分配束縛を使って変数を一度に展開すると便利です。

(defparameter lst '((a 1) (b 2) (c 3)))

;; 分配束縛なし
(defun transform-pairs (lst)
  (loop for pair in lst
        collect (list (first pair) (* (second pair) 10))))

(transform-pairs lst)
;; => ((A 10) (B 20) (C 30))

;; 分配束縛あり
(defun transform-pairs-with-destructuring (lst)
  (loop for (key value) in lst
        collect (list key (* value 10))))

(transform-pairs-with-destructuring lst)
;; => ((A 10) (B 20) (C 30))Code language: Lisp (lisp)

for (key value) in と書くと、ペアの中身が key と value に直接束縛されます2。
リストのリストを扱うloopで、ちょっと見通しがよくなります。

2.1. on との組み合わせ

分配束縛が真価を発揮するのは、loop ... onの組み合わせです。

on は、リスト全体のコンスセルを順にたどります。
つまり、要素として部分リストを取ります。

ドット対パターン (a . b) で部分束縛すると、現在のセルの car と残りのリストを同時に取れます。

(defun adjacent-pairs (lst)
  (loop for (x . rest) on lst
        while rest
        collect (list x (car rest))))

(adjacent-pairs '(10 20 30 40))
;; => ((10 20) (20 30) (30 40))Code language: Lisp (lisp)

2.2. plistの処理で2要素ずつ進む（by #'cddr）

plist の処理では、2要素ずつ進むパターンをよく使います3。
これには、by #'cddr を組み合わせ、byに関数オブジェクトを与えます。

(defun plist-to-scaled-pairs (plist)
  (loop for (key value) on plist by #'cddr
        collect (list key (* value 10))))

(plist-to-scaled-pairs '(:a 1 :b 2 :c 3))
;; => ((:A 10) (:B 20) (:C 30))Code language: Lisp (lisp)

plistをハッシュテーブルに変換するのにもそのまま応用できます。

(defun plist-to-hash-table (plist)
  (let ((ht (make-hash-table)))
    (loop for (sym num) on plist by #'cddr
          do (setf (gethash sym ht) num))
    ht))

(plist-to-hash-table '(one 1 two 2 three 3))Code language: Lisp (lisp)

2.3. ウィンドウ走査の実用例

on と3要素パターンを組み合わせると、リストを「前・現在・次」のウィンドウで走査できます。

局所的な極値検出に使えます4。

;; 局所的な極値検出
(defun local-extrema (lst)
  (loop for (prev x next) on lst
        while (and x next)
        when (and (< prev x) (< next x))
          collect (list :local-max x)
        when (and (> prev x) (> next x))
          collect (list :local-min x)))

(local-extrema '(4 6 6 1 4 5 1))
;=> ((:LOCAL-MIN 1) (:LOCAL-MAX 5))Code language: Lisp (lisp)

3. loopのそのほかの構文

3.1. 型宣言との組み合わせ（of-type）

分配束縛のパターンに型宣言を付けられます。
コンパイラへのヒントになり、SBCL などでは最適化に利用されます5。

;; 型ごとに個別指定
(loop for (a b c) of-type (integer integer float)
      in '((1 2 4.0) (5 6 8.3))
      collect (list c b a))
;; => ((4.0 2 1) (8.3 6 5))

;; 全部同じ型なら1つで済む
(loop for (a b c) of-type float
      in '((1.0 2.0 4.0) (5.0 6.0 8.3))
      collect (list c b a))
;; => ((4.0 2.0 1.0) (8.3 6.0 5.0))Code language: Lisp (lisp)

4. with 句での分配束縛

with 句でも同じパターン構文を使えます。
ループ前に一度だけ実行される初期化で、複数の変数をまとめて束縛できます6。

(loop with (a b) = '(1.0 2.0)
      and (c d) = '(3 4)
      return (list a b c d))
;; => (1.0 2.0 3 4)Code language: Lisp (lisp)

5. そのほかのloopの分配束縛のテクニック

5.1. nil で要素をスキップする

パターン内で変数の代わりに nil を置くと、その位置の値を捨てます7。

(defun collect-first-and-third (lst)
  (loop for (a nil b) in lst
        collect (list a b)))

(collect-first-and-third '((1 2 3) (4 5 6)))
;; => ((1 3) (4 6))Code language: Lisp (lisp)

ドット対と組み合わせることもできます。

(defun collect-first-and-rest-after-second (lst)
  (loop for (a nil . b) in lst
        collect (list a b)))

(collect-first-and-rest-after-second '((1 2 3 4) (5 6 7 8)))
;; => ((1 (3 4)) (5 (7 8)))Code language: Lisp (lisp)

5.2. ネストしたパターン

サブリストにもパターンを当てられます。

(defun flatten-nested-dotted-pairs (lst)
  (loop for ((a . b) (c . d)) in lst
        collect (list a b c d)))

(flatten-nested-dotted-pairs '(((1.2 . 2.4) (3 . 4))
                               ((3.4 . 4.6) (5 . 6))))
;; => ((1.2 2.4 3 4) (3.4 4.6 5 6))Code language: Lisp (lisp)

5.3. 要素が足りないときはnilで自動補完

loop の分配束縛は純粋な構造マッチのみで、&optional や &key は使えません。
要素が足りない場合は nil が補われ、多い場合は切り捨てられます8。

(loop for (a b c) in '((1 2) (3 4 5))
      collect (list a b c))
;; => ((1 2 NIL) (3 4 5))Code language: Lisp (lisp)

6. 【補足】destructuring-bind マクロ

loop の外でリストを分解束縛するには destructuring-bind マクロを使います9。

(destructuring-bind (a b c) '(1 2 3)
  (list a b c))
;; => (1 2 3)Code language: Lisp (lisp)

この分配束縛は、もともとdefmacro内でのラムダリストを処理する仕組みとして使われていましたが、標準マクロに追加されました。
そのため、destructuring-bindは、loop の分配束縛に加え、defmacro 系のラムダリストキーワードも使えます10。
つまり、&optional、&rest、&key、&whole が使えます。

;; &optional でデフォルト値
(destructuring-bind (a &optional (b 99)) '(1)
  (list a b))
;; => (1 99)

;; &rest で残余要素
(destructuring-bind (head &rest tail) '(1 2 3 4)
  (list head tail))
;; => (1 (2 3 4))

;; &key でキーワード対応
(destructuring-bind (&key x y) '(:y 2 :x 1)
  (list x y))
;; => (1 2)Code language: Lisp (lisp)

また、パターンが一致しない場合は error 型のコンディションがシグナルされます。

(destructuring-bind (a b) '(1 2 3)
  ...)
;; => ERROR: Invalid number of elements ...Code language: Lisp (lisp)

&whole を使うと、パターン全体にマッチしつつ元のリスト全体も別の変数で受け取れます。

(destructuring-bind (&whole all &key x y) '(:y 2 :x 1)
  (list x y all))
;; => (1 2 (:Y 2 :X 1))Code language: Lisp (lisp)

6.1. multiple-value-bind との違い

分配束縛と混同されるのが多値束縛 multiple-value-bind です。

  • destructuring-bind はリストを分解します。
  • multiple-value-bind は values で返された多値を受け取ります。

values で返した多値はリストではなく、普通の文脈では第1戻り値だけ使われ、残りは捨てられます11。

;; values で複数の値を返す関数
(defun divide (a b)
  (values (floor a b) (mod a b)))

;; multiple-value-bind で受け取る
(multiple-value-bind (quotient remainder) (divide 17 5)
  (list quotient remainder))
;; => (3 2)

;; destructuring-bind では受け取れない
(destructuring-bind (quotient remainder) (divide 17 5)
  ...)
;; => ERROR: 多値の最初の値 3 だけがリストとして扱われようとしてエラーCode language: Lisp (lisp)

6.2. multiple-value-listとvalues-list

多値とリストは multiple-value-list と values-list で相互変換できます。

;; 多値をリストに変換
(multiple-value-list (divide 17 5))
;; => (3 2)

;; リストを多値に展開
(multiple-value-bind (q r) (values-list '(3 2))
  (list q r))
;; => (3 2)Code language: Lisp (lisp)

関数が values で値を返しているなら multiple-value-bind、通常のリストを返しているなら destructuring-bind か loop の分配束縛を選びます。
標準ライブラリでは floor、ceiling、truncate、round、gethash、find、parse-integer などが多値を返します12。

;; gethash は値と見つかったかどうかを多値で返す
(multiple-value-bind (value found-p)
    (gethash :x (make-hash-table))
  (list value found-p))
;; => (NIL NIL)

;; parse-integer は整数値と消費した文字数を多値で返す
(multiple-value-bind (n end-pos)
    (parse-integer "42abc" :junk-allowed t)
  (list n end-pos))
;; => (42 2)Code language: Lisp (lisp)

multiple-value-bind は値が足りないとき nil を補い、余分な値は捨てます。
destructuring-bind がパターン不一致をエラーにするのとは対照的な挙動です。

  1. CLtL2（Common Lisp the Language 2nd Edition）のGuy Steeleによる注釈に「loopの分配束縛はdestructuring-bindより先に存在し、細部が異なる」と明記されています。 – CLtL2: 26.12.2 Destructuring
  2. in は各要素を順に変数へ渡します。on はコンスセル自体を渡すため、現在位置から末尾までのリストが取れます。この違いがplist走査で on を使う理由です。 – CLHS: Section 6.1.1.7 Destructuring
  3. by に渡す関数はデフォルトが #'cdr（1要素ずつ）です。#'cddr にすると2要素ずつ、#'cdddr にすると3要素ずつ進みます。plistはキーと値が交互に並ぶフラットなリストなので、#'cddr で1ペアずつ処理できます。 – RIPtutorial: Destructuring in FOR statements
  4. while (and x next) はリストの末尾2要素に差し掛かったとき（next が nil になる）にループを終了させます。on によるパターンでは最後の要素が prev に入る時点で x と next が nil になるため、この条件で正しく終了できます。 – RIPtutorial: Destructuring in FOR statements
  5. SBCLは optimize 宣言の safety レベルに応じて型チェックの厳密さを変えます。safety 0 では実行時の型チェックが省略される代わりに、誤った型宣言は未定義動作を引き起こす可能性があります。型宣言は正確であることが前提です。 – SBCL User Manual: Compiler
  6. with 句のみを使うと初期化は逐次（let* 相当）で行われます。and でつなぐと並列（let 相当）になり、各右辺が相互に参照せず同時に評価されます。前の束縛結果を次の初期値に使いたい場合は and を外して逐次にする必要があります。 – CLHS: 6.1.2.2 Local Variable Initializations
  7. nil によるスキップは loop の分配束縛固有の機能です。destructuring-bind では nil を変数名として使うことはできません。不要な位置を無視したい場合は _ などのダミー変数を宣言して (declare (ignore _)) で明示的に無視する必要があります。 – CLHS: Section 6.1.1.7 Destructuring
  8. この「黙って補う・捨てる」という挙動はCLHSで仕様として定められており、destructuring-bind がエラーをシグナルするのとは対照的です。ループの途中で要素数が変動するデータを安全に処理できる一方、意図しないミスを検知できないという側面もあります。 – CLHS: Section 6.1.1.7 Destructuring
  9. destructuring-bind は1989年3月にX3J13（ANSIのCommon Lisp標準化委員会）が独立したマクロとして追加することを決議しました（DESTRUCTURING-BIND:NEW-MACRO）。それ以前は defmacro のラムダリスト処理機構としてのみ存在していました。 – CLHS Issue: DESTRUCTURING-BIND
  10. defmacro で使えるキーワードのうち &environment だけは destructuring-bind では使えません。&environment はマクロ展開時のコンパイル環境を参照するもので、実行時のデータ分解とは目的が異なるためです。 – CLHS: Section 3.4.5 Destructuring Lambda Lists
  11. CLHSによると multiple-value-bind は multiple-value-call を使った lambda 呼び出しに展開されます。リストを経由しないため、destructuring-bind とは根本的にメカニズムが異なります。 – CLHS: Macro MULTIPLE-VALUE-BIND
  12. 多値を使うのは「第1戻り値だけ必要なことが多く、残りはオプション的に必要」な場合に向いています。逆に、複数の値を常にセットで使うなら構造体やリストで返す方が設計として自然です。 – Common Lisp Cookbook: Functions