リスト

配列は応用が広く, 頻繁に用いられる便利なデータ構造だが, 長さ固定 という制限がある. リストもいくつかのデータをまとめたもので次のような特徴がある.

• 先頭に要素を追加できる.
• 先頭の要素を外せる.
• 要素の書き換えはできない.
• 空リストがある.

一見して不自由そうに見えるが,実はリストは強力で,リスト だけでなんでもプログラミングできる. 例えば emacs は LISP と 呼ばれるリスト処理言語で記述されている. 1 文字入力も実は LISP コマンドに対応している.

上の例で出てきた関数, 表現の説明は以下の通り.

1. リストの作り方(その 1)

   
   [0] A = [1,2,3];      /* 見ての通り */
   [1,2,3]               /* 表示が配列と微妙に違う */
   

2. リストの作り方(その 2)

   
   [1] B = cons(0,A);    /* 先頭に要素を追加 */
   [0,1,2,3]
   [2] A;                /* A は影響を受けない */
   [1,2,3]
   

3. リストの作り方(その 3)

   
   [3] C = cdr(A);           /* cdr = クッダー; 先頭要素を取り外す */
   [2,3]
   [4] A;                 /* A は影響を受けない */
   [1,2,3]
   

4. 空リスト

   
   [5] A = [];           /* [] は空のリストを表す */
   []
   [6] cons(1,A);
   [1]
   

5. 要素取り出し (その 1)

   
   [7] car(B);         /* car = カー; 先頭要素を取り出す */
   0
   

6. 要素取り出し (その 2)

   
   [8] B[2];         /* 配列と同様に書ける */
   2
   

7. 書き換え不可

   
   [9] B[2] ＝ 5;         /* 書き換えはダメ */
   putarray : invalid assignment
   return to toplevel
   

例 11.5   例えば, A を B で割った商と剰余を返す関数は次のように 書ける.

def quo_rem(A,B) {
    Q = idiv(A,B);
    R = A - Q*B;
    return [Q,R];
}

[1] QR = quo_rem(123,45);
[2,33]
[2] Q = QR[0];
2
[3] R = QR[1];
33

例 11.6   集合を配列で表そうとすると, 要素の追加 のたびに配列を作り直す必要が出てくる.

/* Element が Set の要素なら 1, そうでなければ 0 */

def memberof(Element,Set)
{
    Size = size(Set)[0];
    for ( I = 0; I < Size; I++ )
        if ( Set[I] == Element )
            return 1;
    return 0;
}

/* 配列で表された集合の和集合. 配列内には重複はないとする */

def union(A,B)
{
    SA = size(A)[0];
    SB = size(B)[0];
    NotinB = 0;             /* #(A-B) */
    for ( I = 0; I < SA; I++ )
        if ( !memberof(A[I],B) )
            NotinB++;
    SC = SB + NotinB;      /* #(A cup B) = #B+#(A-B) */
    C = newvect(SC);
    for ( K = 0; K < SB; K++ )
        C[K] = B[K];
    for ( I = 0; I < SA; I++ )
        if ( !memberof(A[I],B) ) {
            C[K] = A[I];
            K++;
        }
    return C;
}

/* 配列で表された集合の共通集合. 配列内には重複はないとする */

def intersection(A,B)
{
    SA = size(A)[0];
    SB = size(B)[0];
    AandB = 0;             /* #(A cap B) */
    for ( I = 0; I < SA; I++ )
        if ( memberof(A[I],B) )
            AandB++;
    C = newvect(AandB);
    for ( I = 0, K = 0; I < SA; I++ )
        if ( memberof(A[I],B) ) {
            C[K] = A[I];
            K++;
        }
    return C;
}

このような場合には, データ構造としてリストを用いるのが便利である.

/* Element が Set の要素なら 1, そうでなければ 0 (リスト版) */

def memberof(Element,Set)
{
	for ( T = Set; T != []; T = cdr(T) )
		if ( car(T) == Element )
			return 1;
	return 0;
}

/* 和集合. 配列内には重複はないとする (リスト版) */

def union(A,B)
{
	C = B;
	for ( T = A; T != []; T = cdr(T) )
		if ( !memberof(car(T),B) )
			C = cons(car(T),C);
	return C;
}

演習 11.4   配列 A の要素の平均, 分散, 標準偏差をリストで返す関数を書け. 結果は浮動小数で返すこと. 有理数の浮動小数による近似値を返す関数は deval(M), 平方根は M^(1/2).

[0] A = 12345/6789;
4115/2263
[1] deval(A);
1.81838
[2] B = A^(1/2);
(4115/2263)^(1/2)
[3] deval(B);
1.34847

演習 11.5   リストを逆順にしたリストを返す関数を書け. もちろん, 組み込み関数 reverse() を呼ぶのは反則.

(先頭を取り外す, という操作と, その要素を他のリストの先頭に付け加える, という 操作を繰り返せばできる. 「他のリスト」の初期値として何を設定すればよいか.)

演習 11.6   リストで表した 2 集合の共通集合を求める関数を書け.

(和集合の場合, 一方の集合を初期値として, その集合に含まれない要素を付け加えて いった. 共通集合の場合, 何を初期値とし, どういう条件の場合にその初期値に 要素を付け加えればよいか考える.)

演習 11.7   今日の集合に関する例では, 入力の中に重複がないことが前提 であった. リストから重複を除いたリストを返す関数を書け.

(これも, 途中まで出来上がっている重複を除いたリストに, 要素を付け加えて いけばよい. 和集合関数を使ってもできる. )