【Common Lisp】
なぜ member は tail の
コンスセルを返すのか
（所属述語関数）

by

関連記事

1. リストから要素を探す（find・position・member）

Common Lisp でリストから要素を探す関数は3つあります。

(find     70 '(80 90 70 85 95)) ;=> 70
(position 70 '(80 90 70 85 95)) ;=> 2
(member   70 '(80 90 70 85 95)) ;=> (70 85 95)Code language: Lisp (lisp)

find は見つけた要素を返し、position はその位置のインデックスを返します。
どちらも名前と返り値が一致していて、直感的です。

member は少し違います。
まず名前が「リスト探索」なのに “member”（構成員）というのが不思議です。
そして返り値が 70 ではなく (70 85 95) というリストになっています。
これは cons セルへの参照、つまり car や cdr を扱う世界の発想で、慣れないうちは違和感があります。

なぜこうなっているのか。
実は member は find や position より古く、もともと真偽値を返す述語でした。
それが Lisp の進化の中で変わっていった。
その経緯を辿ります。

1.1. member という名前が残った理由

探索する関数なのに、なぜ search や find ではなく member なのか。

設計の発想が「探索」ではなかったからです。
member は「x を探す」関数ではなく、「x はこのリストの構成要素か」を調べる関数として LISP 1.5 から存在していました。
返り値が変わっても、その発想は引き継がれ、名前も変わりませんでした。

Common Lisp HyperSpec でも、member の説明は「探す」ではなく「所属しているかを調べ、見つかったサブリストを返す」という表現になっています。1

1.2. もともと member は集合演算だった（LISP 1.5）

1962年の LISP 1.5 Programmer’s Manual には、MEMBER の定義がこう書かれています。2

(DEFUN MEMBER (X Y)
  (COND ((NULL Y)       NIL)
        ((EQ A (CAR X)) T)
        (T               (MEMBER X (CDR Y)))))Code language: Lisp (lisp)

一致したとき、返しているのは T です。
見つからなければ NIL。
これは集合論的な所属判定をそのまま関数にしたもので、「x は集合 Y のメンバーか」という問いに答えるものです。
member という名前の語源もここにあります。
英語の “member” は「会員」だけでなく「集合の構成要素」という意味を持ちます。

この MEMBER は、UNION や INTERSECTION を定義するための補助関数として登場していました。3 マニュアルには UNION と INTERSECTION の定義も載っており、どちらも MEMBER を呼び出しています。

(DEFUN UNION (X Y)
  (COND ((NULL X) Y)
        ((MEMBER (CAR X) Y) (UNION (CDR X) Y))
        (T (CONS (CAR X) (UNION (CDR X) Y)))))

(DEFUN INTERSECTION (X Y)
  (COND ((NULL X) NIL)
        ((MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION (CDR X) Y)))
        (T (INTERSECTION (CDR X) Y))))Code language: Lisp (lisp)

UNION の2番目の節を見ると、(MEMBER (CAR X) Y) の返り値を条件として使っています。
T か NIL かだけが問題で、見つかった位置は必要ない。
リストを集合として扱う演算の一部として設計されていたため、真偽値で十分だったわけです。

1.3. 返り値が Generalized Booleanになる（Maclisp）

Maclisp の Pitmanual では、MEMBER の定義が変わっています。4

(DEFUN MEMBER (X Y)
  (COND ((NULL Y)        NIL)
        ((EQUAL X (CAR Y)) Y)   ; ← T ではなく Y を返す
        (T               (MEMBER X (CDR Y)))))Code language: Lisp (lisp)

一致したとき、返しているのは T ではなく Y です。
Y はそのとき走査していた cons セルから始まるリストです。
一文字の変更ですが、意味は大きく変わりました。

Pitmanual はさらにこう付け加えています。
「返り値は元のリストのその部分と EQ である」と。
コピーではなく、元のリスト構造への参照がそのまま返ってきます。

(defvar xs (list 80 90 70 85 95))
(defvar tail (member 70 xs))

tail        ;=> (70 85 95)
(eq tail (cddr xs))  ;=> T   ; 同じ cons セルを指しているCode language: Lisp (lisp)

tail と (cddr xs) が EQ であることが確認できます。
member は新しいリストを作っているのではなく、元のチェーンの途中を指しているだけです。

1.4. Common Lisp で find と position が整備された

member は「所属判定」に近い発想の関数で、「探索」に特化した関数は別途に用意されました。

Common Lisp ではそれが find と position です。

; 要素そのものが欲しい
(find 70 '(80 90 70 85 95))
;=> 70

; インデックスが欲しい
(position 70 '(80 90 70 85 95))
;=> 2

; 見つかった位置以降のリストが欲しい
(member 70 '(80 90 70 85 95))
;=> (70 85 95)Code language: Lisp (lisp)

find と position は Common Lisp の sequence 関数群として体系化されたもので、member より後に整備されています。5 歴史的には member が先にあり、必要な操作が増えるにつれて関数が分かれていきました。

3つとも :test や :key を受け取れます。

; 文字列の比較には :test #'equal を指定する
(member "bob" '("alice" "bob" "carol") :test #'equal)
;=> ("bob" "carol")

(find "bob" '("alice" "bob" "carol") :test #'equal)
;=> "bob"

(position "bob" '("alice" "bob" "carol") :test #'equal)
;=> 1

; :key で比較前に各要素に適用する関数を指定できる
(find 'bob '((alice 80) (bob 90) (carol 70)) :key #'car)
;=> (BOB 90)

(member 'bob '((alice 80) (bob 90) (carol 70)) :key #'car)
;=> ((BOB 90) (CAROL 70))Code language: Lisp (lisp)

3つとも O(n) の走査ですが、返すものが違います。

関数返すものnil 要素で曖昧にならないか
member見つかった位置以降のリストならない
find見つかった要素そのものなる
positionゼロ始まりのインデックスならない

find は nil を探すと返り値が「見つからなかった」と区別できなくなります。
member が tail を返す仕様を選んだことで、この問題を避けていたわけです。

2. なぜ要素ではなく tail なのか

最も直接的な理由は、実装の自然さです。

Maclisp の MEMBER の定義では、(EQUAL X (CAR Y)) が真になった瞬間、ループの中で手元にあるのは Y です。

要素を返すなら (CAR Y) と一手間かかりますが、Y をそのまま返すだけなら追加の操作は何もいりません。
「走査中にすでに持っているものをそのまま返した」というのが、tail になった最も直接的な理由と考えられます。

そこから副次的な利点がついてきます。

  • ひとつは nil 問題の回避です。
    もし要素を返す仕様だったとすると、nil を探したときに「見つかった nil」と「見つからなかった NIL」が区別できません。
    tail は非 nil なので、この曖昧さが生じません。
  • もうひとつは情報量の差です。
    tail を返せば真偽判定にも使えますし、見つかった位置以降のリスト操作にもそのまま使えます。
    返り値が元のリストと同じ cons セルを指しているため、破壊的な書き換えにも使えます。

これらの具体的なパターンは後の章でまとめて扱います。

2.1. orやandと同じように（Gabriel & Steele の証言）

この変更は、個別の関数の話ではありませんでした。

Richard Gabriel と Guy Steele の “The Evolution of Lisp” には、Maclisp が Lisp 1.5 から改良した点として「MEMBER のような単純述語を、有用な値を返す関数に変更した」という記述があります。6

同じ流れで変わったのは member だけではありません。
この変更を支えた発想が、Lisp の generalized boolean です。

関数LISP 1.5 の返り値Maclisp の返り値
member見つかれば T、なければ NIL見つかれば tail、なければ NIL
and全部真なら T、途中で偽なら NIL全部真なら最後の式の値、途中で偽なら NIL
orどれか真なら T、全部偽なら NIL最初の非 NIL 値、全部偽なら NIL

Lisp では nil だけが偽で、それ以外の値はすべて真として扱えます。
条件式に T を返す必要はなく、任意の非 nil 値を返せばよい。
であれば、どうせ真を返すなら、T より有用な値を返した方がいい。

or と and の返り値は、この発想をよく表しています。
or が最初の非 NIL 値を返すのも、この設計思想の表れです。

(or nil nil 42 99)   ;=> 42
(or nil nil nil)     ;=> NIL

; デフォルト値のイディオム
(defvar config nil)
(or config "default.cfg")  ;=> "default.cfg"Code language: Lisp (lisp)

or でデフォルト値を返す (or config "default.cfg") という書き方は今でもよく使われます。
Maclisp での変更がなければ、このイディオムは成立しませんでした。

; and：全部真なら最後の値を返す
(and 1 2 3)    ;=> 3
(and 1 nil 3)  ;=> NIL

; ガード的な使い方
(and (plusp x) (* x 2))  ; x が正のときだけ計算するCode language: Lisp (lisp)

3. tail を活かすパターン

member が tail を返すことで使えるイディオムと定石を整理します。

3.1. 真偽判定・先頭要素の取り出し

最もシンプルな使い方は、if や when の条件に渡すことです。

find との違いは、nil を探しても結果が曖昧にならない点です。

(when (member :verbose options)
  (print "verbose mode"))

; nil を探しても区別できる
(find nil '(1 nil 2))    ;=> NIL  ← 見つかったのか分からない
(member nil '(1 nil 2))  ;=> (NIL 2)  ← 見つかったと分かる
(member nil '(1 2 3))    ;=> NIL      ← 見つからなかったCode language: Lisp (lisp)

tail の先頭が目的の要素なので、car と組み合わせれば find と同じ結果が得られます。

(car (member 70 '(80 90 70 85 95)))
;=> 70Code language: Lisp (lisp)

3.2. loop for ... on との組み合わせ

loop for ... on は for ... in と違い、各ステップで cons セルそのものを受け取ります。
member と同じ発想で、tail を手元に持ちながら走査できます。

; member の代わりに loop で位置を探してから操作する
(defvar xs (list 'a 'b 'c 'd 'e))

(loop for tail on xs
      when (eq (car tail) 'c)
        do (setf (car tail) :found)
           (return))

xs  ;=> (A B :FOUND D E)Code language: Lisp (lisp)

member で見つけて rplaca する書き方と等価ですが、ループ内で複数の操作をまとめたいときは loop for ... on の方が見通しがよくなります。

  • for ... in が要素を返すのは find と同じ発想
  • for ... from がインデックスを扱うのは position と同じ発想
  • for ... on が cons セルを返すのは member と同じ発想

3.3. member を連鎖させて絞り込む

member の返り値をそのまま次の member に渡せます。

リストの特定区間を対象に探索したいときに使えます。

(defvar xs '(a b c d e f g))

; :start のような引数なしに、c 以降から e を探す
(member 'e (member 'c xs))
;=> (E F G)Code language: Lisp (lisp)

複数キーワードが特定の順序で現れるかどうかを確認する場面でも使えます。

(defun ordered-p (x y list)
  "x が y より前に現れるか"
  (member y (member x list)))

(ordered-p 'b 'd '(a b c d e))  ;=> (D E)  ← 真
(ordered-p 'd 'b '(a b c d e))  ;=> NIL    ← 偽Code language: Lisp (lisp)

3.4. ldiff でリストを前後に分割する

member の返り値と元のリストを ldiff に渡すと、その要素の前後を一度に得られます。

(defun split-at (item list &key (test #'eql))
  (let ((tail (member item list :test test)))
    (when tail
      (values (ldiff list tail) tail))))

(split-at 70 '(80 90 70 85 95))
;=> (80 90)
;=> (70 85 95)Code language: Lisp (lisp)

要素を含む前半が欲しいときは tail の cdr と組み合わせます。

(defun split-after (item list &key (test #'eql))
  (let ((tail (member item list :test test)))
    (when tail
      (values (ldiff list (cdr tail)) (cdr tail)))))

(split-after 70 '(80 90 70 85 95))
;=> (80 90 70)
;=> (85 95)Code language: Lisp (lisp)

3.5. ふたつの member でサブリストを切り出す（ldiff）

始点と終点をそれぞれ member で取り、ldiff を組み合わせると、リストの部分列を切り出せます。

(defvar xs '(a b c d e f g))

(let* ((from (member 'c xs))
       (to   (member 'f xs)))
  (ldiff from to))
;=> (C D E)Code language: Lisp (lisp)

ldiff は第1引数のリストから、第2引数のリストが始まる直前までを返します。
member が元のリストと同じ cons セルを指しているので、この組み合わせが成立します。

3.6. rplaca / rplacd で要素を書き換える

member の返り値が元のリストと同じ cons セルを指しているため、rplaca で書き換えると元のリストに直接反映されます7。

(defvar xs (list 80 90 70 85 95))

(let ((tail (member 70 xs)))
  (when tail
    (rplaca tail 999)))

xs  ;=> (80 90 999 85 95)Code language: Lisp (lisp)

rplacd を使えば、見つかった要素以降をまとめて差し替えられます。

(defvar xs (list 80 90 70 85 95))

(let ((tail (member 70 xs)))
  (when tail
    (rplacd tail '(0 0 0))))

xs  ;=> (80 90 70 0 0 0)Code language: Lisp (lisp)

コピーを作らずにリスト構造を変更できるので、大きなリストを破壊的に編集する場面で使えます。
ただし、リストを共有している他の変数にも影響が及ぶため、自分が所有しているリストにだけ使うのが安全です。

4. まとめ

member が tail を返す理由を整理すると、次のようになります。

  • LISP 1.5 では member は真偽値を返す所属判定の述語だった
  • Maclisp で「述語を有用な値を返す関数に変える」という設計変更が行われた
  • tail を返すことで、nil 要素の探索でも結果が曖昧にならない
  • 走査中にすでに得ている cons セルをそのまま返すので、追加コストがない
  • 同じ流れで and と or の返り値も変わった
  • Common Lisp では find、position、member がそれぞれ要素、インデックス、tail を返す形で役割を分担している

member の返り値は、Maclisp 時代に「より多くの情報を返す」方向への意識的な変更の結果として、今の Common Lisp に引き継がれています。

  1. Common Lisp HyperSpec は Kent Pitman が1996年に作成した ANSI Common Lisp 標準の HTML 版で、LispWorks 社が公開しています。ANSI 標準そのものではありませんが、実質的な公式リファレンスとして広く参照されています。 – CLHS: Function MEMBER, MEMBER-IF, MEMBER-IF-NOT
  2. LISP 1.5 Programmer’s Manual は John McCarthy ら MIT の研究者が執筆し、MIT Press から1962年8月に刊行されました。著者は McCarthy、Abrahams、Edwards、Hart、Levin の5名です。 – LISP 1.5 Programmer’s Manual (MIT Press)
  3. LISP 1.5 の MEMBER は比較に EQ を使っており、アトム（シンボル）同士の同一性判定に限られていました。Common Lisp の member がデフォルトで eql を使い、数値の値比較にも対応しているのとは異なります。 – LISP 1.5 Programmers Manual (Scribd)
  4. “The Pitmanual” は Kent M. Pitman による “The Revised Maclisp Manual” の通称です。MIT Laboratory for Computer Science の Technical Report 295 として1983年に刊行されました。Pitman は後に Common Lisp HyperSpec の作成者としても知られています。 – The Revised Maclisp Manual (maclisp.info)
  5. Common Lisp は1994年12月8日に ANSI X3.226-1994 として標準化されました。find や position を含む sequence 関数群はこの標準の一部です。標準化委員会 X3J13 は1986年に発足し、Guy Steele の著書 “Common Lisp: The Language” を出発点として策定作業を進めました。 – X3J13 (Wikipedia)
  6. “The Evolution of Lisp” は1993年4月にケンブリッジで開催された ACM SIGPLAN の History of Programming Languages Conference（HOPL-II）で発表された論文です。著者の Richard P. Gabriel は Lucid, Inc.、Guy L. Steele Jr. は Thinking Machines Corporation に所属していました。 – The evolution of Lisp (ACM Digital Library)
  7. Common Lisp では rplaca と rplacd が cons セルの car・cdr を破壊的に変更する関数です。tail が元のリストと EQ であるという性質は、member の返り値を使って元のリスト構造を直接書き換えられることを意味します。 – CLHS: Function RPLACA, RPLACD