リストの処理

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

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

一見して不自由そうに見えるが,実はリストは強力で,リスト だけでなんでもプログラミングできる. 例えば emacs は LISP と 呼ばれるリスト処理言語で記述されていて emacs での 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;         
   [1,2,3]
   

       

   先頭に要素を追加
   
   A は影響を受けない

   
   

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

   [3] C = cdr(A);
   [2,3]
   [4] A;        
   [1,2,3]
   

       

   cdr = クッダー; 先頭要素を取り外す
   
   A は影響を受けない

   
   

4. 空リスト

   [5] A = [];   
   []
   [6] cons(1,A);
   [1]
   

       

   [] は空のリストを表す

   
   

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

   [7] car(B);   
   0
   

       

   car = カー; 先頭要素を取り出す

   
   

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

   [8] B[2];     
   2
   

       

   配列と同様に書ける

   
   

7. 書き換え不可

   [9] B[2] ＝ 5;
   putarray : invalid assignment
   return to toplevel
   

       

   書き換えはダメ

   
   

例 12.1   例えば, 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

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

プログラム

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

    

Element が Set の要素なら 1, そうでなければ 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++;
  /* #(A cup B) = #B+#(A-B) */
  SC = SB + NotinB;
  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;
}

    

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

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

プログラム

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

    

Element が Set の要素なら 1, そうでなければ 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;
}

    

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

問題 12.1   配列 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

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

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