データ構造

スカラー（scalar）

• 整数、実数、ビット（真（true）または偽（false））

リスト（list）

• リスト（list） q = [ x₁, x₂, ..., x_n ] は任意の要素の一連であり、
  その内の幾つかは繰り返されているかもしれない
• 要素 x₁ はリストの頭（head）、x_n は尾（tail）である
• x₁ と x_n は端（ends）である
• リストの要素数、サイズ n を |q | で表す
• [ ] は、要素を持たない空のリスト（empty list）を表す
• ２つの要素のリスト [ x₁, x₂ ] は、順序対（ordered pair）と呼ばれる

　リストの操作

基本的な操作

• Access（アクセス） 　リスト q = [ x₁, x₂, ..., x_n ] と整数 i が与えられて、 リストの i 番目の要素 q (i ) = x_i を返す
• Sublist（サブリスト） 　リスト q = [ x₁, x₂, ..., x_n ] と整数 i と i が与えられて、 q [i ..j ] = [ x_i , x_i+1, ..., x_j ] を返す
• Concatenation（連結） 　２つのリスト q = [ x₁, x₂, ..., x_n ] と r = [ y₁, y₂, ..., y_m ] が与えられて、 q &r = [ x₁, x₂, ..., x_n , y₁, y₂, ..., y_m ] を返す

  端を処理する操作

• Access head（頭のアクセス） 　リスト q が与えられて、q (1) を返す
• Push（プッシュ） 　リスト q と要素 x が与えられて、q を x &q = [ x , x₁, x₂, ..., x_n ] で置き換える
• Pop（ポップ） 　リスト q が与えられて、q を q [2..n ] = [ x₂, x₃, ..., x_n ] で置き換える
• Access tail（尾のアクセス） 　リスト q が与えられて、q (|q |) = q (n ) = x_n を返す
• Inject（後入れ） 　リスト q と要素 x が与えられて、q を q &x = [ x₁, x₂, ..., x_n , x ] で置き換える
• Eject（後出し） 　リスト q が与えられて、q を q [1..n -1] = [ x₁, x₂, ..., x_{n -1} ] で置き換える

　スタック（stack）

• 頭のアクセスとプッシュとポップの操作が可能なリスト
• 挿入と削除に関して、後入れ先出し（last-in first-out）方式によって機能する
  

　キュー（queue）

• 頭のアクセスと後入れとポップの操作が可能なリスト
• 挿入と削除に関して、先入れ先出し（first-in first-out）方式によって機能する
  

　出力制限キュー（output-restricted queue）

• 後出し以外の全ての操作が可能なリスト
  

　デキュー（deque, double-ended queue）

• 端に関する６つの操作が全て可能なリスト
  

集合（set）

• 集合（set） s = { x₁, x₂, ..., x_n } は異なる要素の集まりであり
  暗黙の順序付けはない
• リストの要素数、サイズ n を |s | で表す
• { } は、要素を持たない空集合（empty set）を表す

　集合の操作

• 併合、結び（union）　∪
• 交わり（intersection）　∩
• 差（difference）　−

写像（map）

• 写像（map） f = { [ x₁, y₁ ], [ x₂, y₂ ], ..., [ x_n, y_n ] } は、順序対の集合で、
  どの２つも同じ第１座標（頭）を持たない
• f の定義域（domain）は、第１座標の集合 domain(f ) = { x₁, x₂, ..., x_n }
• f の値域（range）は、第２座標の集合 range(f ) = { y₁, y₂, ..., y_n }
• f をその定義域から値域への関数とみなし、定義域の要素 x_i におけるf の値（value）f (x_i ) は、第２座標 y_i に対応する