配列は応用が広く, 頻繁に用いられる便利なデータ構造だが, 長さ固定 という制限がある. リストもいくつかのデータをまとめたもので次のような特徴がある.
上の例で出てきた関数, 表現の説明は以下の通り.
[0] A = [1,2,3]; [1,2,3] |
見ての通り
表示が配列と微妙に違う |
[1] B = cons(0,A); [0,1,2,3] [2] A; [1,2,3] |
先頭に要素を追加
A は影響を受けない |
[3] C = cdr(A); [2,3] [4] A; [1,2,3] |
cdr = クッダー; 先頭要素を取り外す
A は影響を受けない |
[5] A = []; [] [6] cons(1,A); [1] |
[] は空のリストを表す |
[7] car(B); 0 |
car = カー; 先頭要素を取り出す |
[8] B[2]; 2 |
配列と同様に書ける |
[9] B[2] = 5; putarray : invalid assignment return to toplevel |
書き換えはダメ |
プログラム
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 |
プログラム
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; }
|
和集合を返す. 配列内には重複はないとする (リスト版) |
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
(先頭を取り外す, という操作と, その要素を他のリストの先頭に付け加える, という 操作を繰り返せばできる. 「他のリスト」の初期値として何を設定すればよいか.)