Scheme のペアとリスト

1. Haskell の (:) コンスはリストを生成する

Haskell で、リストの先頭に要素を追加するには (:) 演算子を使う。

Prelude> 1:[2,3,4]
[1,2,3,4]

演算子 (:) は「コンス」と呼ばれる。この関数は、リストのデータコンストラクタとして定義されている。

The Haskell 98 Language Report > 6.1.3 リスト

data [a] = [] | a : [a] deriving (Eq, Ord)リストは、二つの構成子をもつ代数的データ型であるが、3.7 節で述べたように特別な構文をもつ。最初の構成子は空リストで、`[]' (「ニル」)と書く。二つ目の構成子は、`:' (「コンス」)と書く。

(:) の型を確認する。

Prelude> :t (:)
(:) :: a -> [a] -> [a]

リストの要素は、同じ型でなければならない。そのため、次のような計算ではエラーとなる。

"Hoge":[2,3,4]

2. Lisp の cons はペアを生成する

Lisp にも同じ名前の cons 関数がある。ただし、Haskell の (:) とは異なる。

cons により、２つの、値または値へのポインタを持つオブジェクトを生成する。
cons により生成されたオブジェクトは「ペア」と呼ばれる。
ペアの１番目の要素は car により、２番目の要素は cdr により参照する。

cons - Wikipedia, the free encyclopedia

… cons ( /ˈ k ɒ n z / or /ˈ k ɒ n s /) is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as (cons) cells, conses, non-atomic s-expressions ("NATSes"), or (cons) pairs.

Haskell のように、リスト型に対して定義されている関数ではない。

ペア

Lisp の cons によって生成される「ペア」とは、順序対のこと。

順序対は、２つの要素で構成される。

Ordered pair – Wikipedia

… an ordered pair (a, b) is a pair of mathematical objects. In the ordered pair (a, b), the object a is called the first entry, and the object b the second entry of the pair.

cons によって生成されるのは、リストではない。

3. タプルでペアを表現できる

Haskell には、Data.Tuple 型が定義されている。この型を順序対として用いることができる。データコンストラクタは、リストと同じように特別な表記がある。

(,)

タプルとは、要素が順に並んでいるリストのこと。要素の数 n に応じて、n-tuple と呼ばれる。特に 2-tuple は順序対と言う。

Tuple – Wikipedia

… a tuple is an ordered list of elements. In set theory, an (ordered) -tuple is a sequence (or ordered list) of elements, where is a positive integer.

The unique ‑tuple is called the null tuple. A ‑tuple is called a singleton, a ‑tuple is called an ordered pair and a ‑tuple is a triple or triplet.

タプルは、順序対をネストしたものと見なせる。

Tuples as nested ordered pairs

Another way of formalizing tuples is as nested ordered pairs:

The 0-tuple (i.e. the empty tuple) is represented by the empty set $\emptyset$ .

An -tuple, with , can be defined as an ordered pair of its first entry and an -tuple (which contains the remaining entries when ):
$(a_1, a_2, a_3, \ldots, a_n) = (a_1, (a_2, a_3, \ldots, a_n))$

This definition can be applied recursively to the -tuple:

$(a_1, a_2, a_3, \ldots, a_n) = (a_1, (a_2, (a_3, (\ldots, (a_n, \emptyset)\ldots))))$

4. Scheme と Haskell の比較

Data.Tuple に定義されている関数は、順序対に対して適用できる。

Lisp のペアに対する操作と名前を比較すると、

	Lisp	Haskell
ペアを生成	cons	(,)
1番目の要素を取得	car	fst
2番目の要素を取得	cdr	snd

Haskell でタプルを生成し、上記の関数を適用する。

  print (1, 2)              -- (1,2)   print (1, "hoge")         -- (1,"hoge")
  print $ fst $ (1, 2)      -- 1
  print $ snd $ (1, "hoge") -- "hoge"

リストと違い、タプルの要素は異なる型でも良い。

次に、同じ操作を Scheme で書いてみる。Scheme は Lisp の一方言なので、上記と同じ関数が用意されている。

11.9 Pairs and lists

A pair is a compound structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure cons. The car and cdr fields are accessed by the procedures car and cdr.

(display (cons 1 2))             ; {1 . 2}
(newline) 
(display (cons 1 "hoge"))        ; {1 . hoge}
(newline)  
(display (car (cons 1 2)))       ; 1
(newline)
(display (cdr (cons 1 "hoge"))) ; hoge
(newline)

5. Scheme のリストはペアからできている

リストの定義

Lisp 系の言語は、ペアで「リスト」を表現する。ペアという構造の上にリストが作られる。Haskell では、ペアを表現するためのタプルとリストは全く別の型。

Scheme において、リストは次のように定義されている。

空リスト
ペアの cdr フィールドがリストであるもの

A list can be defined recursively as either the empty listor a pair whose cdr is a list. More precisely, the set of lists is defined as the smallest set X such that

The empty list is in X.

If list is in X, then any pair whose cdr field contains list is also in X.

（11.9 Pairs and lists より）

要素のない空リストは、特別に用意されており、

()

と表現する。

(display (cons 1 '()))          ;(1)
(newline)
(display (cons 1 (cons 2 '()))) ; (1 2)
(newline)

最初の例は、ペアの cdr フィールドに空リストがあるので、リストである。

次の例は、(cons 2 ‘()) がリスト。そのため、全体では

(cons 1 リスト)

という構造になるのでリスト。

リストはペアであるが、空リストはペアでない

リストは、ペアの特殊な形として作成される。そのため、リストはペアでもある。

対象がペアの場合真を返す述語 pair? と、リストである場合真を返す述語 list? を使って確かめてみる。

(define ls (cons 1 (cons 2 (cons 3 '()))))
(display (pair? ls))    ; #t
(display (list? ls))    ; #t

ただし、空リストはペアではない。

The empty listis a special object of its own type. It is not a pair. It has no elements and its length is zero.

また、述語 null? に対して唯一真を返すオブジェクト。

(null? obj) procedure

Returns #t if obj is the empty list, #fotherwise.

(display (pair? '()))  ; #f
(display (list? '()))  ; #t
(display (null? '()))  ; #t

まとめると、

リストはペアである。
ただし、空リストはペアではない。
空リストは、null である特別なオブジェクト。

当初、この点に違和感を覚えた。なぜなら、ペアが保持している要素によって、可能な操作が異なる。そのため、要素の内容により、型が変化するように見えたから。

たとえば、リストの逆順を返す reverse 手続きはリストに適用できるが、ペアには適用できない。同じような手続きはライブラリにいくつか定義されている。

Haskell でたとえると、

(1, [])
(1, (2, [])

は、ペアであると同時にリストであり、この場合にのみ適用可能な関数がある、といった感じ。Scheme よりも Haskell を先に学んだので、Scheme のペアとリストの関係がしっくりこなかった。

ドット対

ところで、cons 関数で生成したペアを display 関数で表示すると、`.’（ドット）を用いて表される。要素が3つのときは、次のように表示される。

(display (cons 1 (cons 2 3)))    ; {1 2 . 3}

ネストされたペアは、ドットが省略された形。

11.9 Pairs and lists

A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:

(a b c . d)

is equivalent to

(a . (b . (c . d)))

ドットで表現されたペアを、ソースコードにそのままの形で書き、実行するとエラーとなる。

(display (1 2 . 3))

括弧で囲まれた最初の要素は手続き、それ以降の要素は引数として解釈されるため。

Procedure calls

(<operator> <operand₁> ...) syntax

A procedure call consists of expressions for the procedure to be called and the arguments to be passed to it, with enclosing parentheses.

これを回避するには、quote を用いる。

11.4.1 Quotation

Semantics: (quote <datum>) evaluates to the datum value represented by <datum> (see section 4.3).

quote の代わりに ‘ を使うこともできる。

(display (cons 1 (cons 2 3)))    ; {1 2 . 3}
(newline)
(display (quote (1 2 . 3)))
(newline)

6. Scheme の基本的な型

Scheme で操作する対象となるオブジェクト（値）は「型」を持つ。

1.1 Basic types

Scheme programs manipulate objects, which are also referred to as values. Scheme objects are organized into sets of values called types.

基本的な型に対応した述語が９つ定義されている。この手続きを用いて値の型を特定できる。

11.1 Base types

No object satisfies more than one of the following predicates:

boolean? pair? symbol? number? char? string? vector? procedure? null?

These predicates define the base types boolean, pair, symbol, number, char (or character), string, vector, and procedure. Moreover, the empty list is a special object of its own type.

Note that, although there is a separate boolean type, any Scheme value can be used as a boolean value for the purpose of a conditional test; see section 5.7.

上記には「ペア」と「空リスト」を特定する述語が挙げられている。しかし、リストに対応した述語は含まれていない。

述語 list? は、ペアとリストの解説で述べられている。

11.9 Pairs and lists

(list? obj) procedure

Returns #t if obj is a list, #f otherwise. By definition, all lists are chains of pairs that have finite length and are terminated by the empty list.

このことからも、リストはペアの特殊な形であることが分かる。

すぐに忘れる脳みそのためのメモ

2012年9月23日日曜日