「CARとCDR」の版間の差分
→応用: 節追加 |
|||
| 27行目: | 27行目: | ||
たとえば、リストの最後の要素を得るlast関数は、 |
たとえば、リストの最後の要素を得るlast関数は、 |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun last (L) (if (cdr L) (last (cdr L)) (car L))) |
(defun last (L) (if (cdr L) (last (cdr L)) (car L))) |
||
</syntaxhighlight> |
|||
</source> |
|||
リストの長さを得る関数lengthは、 |
リストの長さを得る関数lengthは、 |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun length (L) (if L (+ 1 (length (cdr L))) 0)) |
(defun length (L) (if L (+ 1 (length (cdr L))) 0)) |
||
</syntaxhighlight> |
|||
</source> |
|||
のように定義できる（なお、上記の例はいずれも空リストが真偽値として偽になることを利用している）。 |
のように定義できる（なお、上記の例はいずれも空リストが真偽値として偽になることを利用している）。 |
||
2020年7月5日 (日) 23:10時点における版
CARとCDR（カーとクダー）は、LISP言語の基本的なデータ型であるリストを操作するためのもっとも基本的な2つの関数である。CARはリストの先頭要素を返し、CDRは先頭要素以外を返す。
LISPではリストはコンス（ペアまたはドット対とも呼ばれる）の鎖によって実現されており、CARとCDRという名前はコンスを構成する2つの部分を指すのにも用いられる。
名前と語源
英語でCARは自動車を意味するcar /kɑɹ/ と同音に発音し、CDRはcould-er /ˈkʊdəɹ/ のように発音される[1]。
この不可解な名称は、最初にLISPが開発されたIBM 704の命令形式に由来する。IBM 704は36ビット・ワードの機械で、タイプAの命令形式ではこれを3ビットのプレフィックス（オペコード）、15ビットのデクリメント、3ビットのタグ、15ビットのアドレスの4つの部分に分けて用いた[2]。CARとはこのうちアドレス部の中身(Contents of the Address part of the Register)を、CDRとはデクリメント部の中身(Contents of the Decrement part of the Register)を意味する略語だった。現在ではこの名称は意味のないものになっている[1]。
Common Lispでは、より意味のある first および rest という関数も用意されているが、古い名称もひき続き使われている。
概要
LISPにおいて、コンス（またはペア、またはドット対）は2つの要素を持つ順序対である。1番目の要素をCAR、2番目の要素をCDRと呼ぶ。リストは「CDRがリストであるコンス、または空リスト」であると再帰的に定義される[3]。
具体的にいうと、要素aとbから構成されるコンスは (a . b) と表され、リスト (a b c) は、各要素がcarであるコンスをcdrの鎖でつないだ片方向リスト、すなわち (a . (b . (c . ()))) として実現されている。したがって、リストの先頭の要素を得るのは、最後の要素を得るのに比べて効率がよい。
リストLの2番目の要素は (car (cdr L))、3番目の要素は (car (cdr (cdr L))) のようにして得られる。Common Lispなどの多くのLISP方言では、簡略化するために、(car (cdr L)) と同じことをする (cadr L) という関数が定義されている。同様に caddr, cadddr なども存在する。
関数car/cdrの引数が空リストである場合、Common Lispでは空リストを返す[4]。Schemeではエラーになる[5]。
car/cdrは、consと逆のことをする関数である。すなわち(car (cons X Y))は X に、(cdr (cons X Y)) は Y に等しい。また、(cons (car L) (cdr L)) は L と構造的には等しい（同じオブジェクトを指すとは限らない）。
car/cdrは副作用を持たず、またconsセルも消費しない。
応用
car/cdrを再帰や条件分岐と組み合わせることで、リスト関係のさまざまな関数を作ることができる。
たとえば、リストの最後の要素を得るlast関数は、
(defun last (L) (if (cdr L) (last (cdr L)) (car L)))
リストの長さを得る関数lengthは、
(defun length (L) (if L (+ 1 (length (cdr L))) 0))
のように定義できる（なお、上記の例はいずれも空リストが真偽値として偽になることを利用している）。
LISP以外の言語
LOGOでは、最初の要素をFIRST、それ以外の要素をBUTFIRSTで取得する。
Prologでは、リストを[X|Y]とパターンマッチ（単一化）させることで、Xに先頭要素が、Yに先頭要素以外が得られる。空リストにはマッチしない。
Haskellでも同様に、リストを(x:y)とパターンマッチさせることで、xに先頭要素が、yに先頭要素以外が得られる。空リストにはマッチしない。
脚注
- ^ a b “Strange Names”, An Introduction to Programming in Emacs Lisp
- ^ From the IBM 704 to the IBM 7094, How Does A Computer Work?
- ^ COMMON LISP 第2版 p.25。なおCommon Lispでは最後の要素のCDRが空リストでないものは「ドットリスト」と呼ばれてリストとは別扱いされる。
- ^ COMMON LISP 第2版 p.361
- ^ R. Kent Dybvig (2009). “Operations on Objects”. The Scheme Programming Language (4th ed.). The MIT Press. ISBN 978-0-262-51298-5
参考文献
- Guy L. Steele Jr.『COMMON LISP 第2版』共立出版、1992年。ISBN 4320025881。（英語オンライン版：Guy L. Steele Jr., Common Lisp the Language, 2nd Edition）