タプルとリスト
ラムダ計算では 1 つの引数を取って 1 つの値を返す関数しか扱いません。そのため基本的に 1 つの値のみを次々に加工して計算を進めることになります。
タプル
2 つの値をタプルにして 1 つの値として扱うことで複数の値を同時に扱うことが可能になります。
Tuber においては Lisp の伝統に則り、タプルを作る関数 CONS とタプルの各要素にアクセスする関数 CAR, CDR を用意しています。
タプルを作る CONS
CONS は 2 つの引数から 1 つのタプルを作って返します。
CONS(x, y) # x, y を内包したタプルを返すこのようにして作ったタプルはあくまでも 1 つの値であるため、関数適用したりラムダ抽象の返り値にすることが可能です。
i(CONS(x, y)) # 関数 i に1つのタプル CONS(x, y) を渡す
(x, y) => CONS(x, y) # 引数 x, y を受け取って1つのタプル CONS(x, y) を返すタプルの各要素にアクセスする CAR, CDR
CAR, CDR を使ってタプルの各要素を取り出せます。
CAR はタプルを受け取って 1 つめの要素を返します。
t = CONS(:a, :b)
CAR(t) # => :aCDR はタプルを受け取って 2 つめの要素を返します。
t = CONS(:a, :b)
CDR(t) # => :bリスト
タプルを応用すると 2 つ組だけでなく 3 値以上の値の組を扱うことが可能になります。
複数の値を扱うリスト構造について解説します。
値の無いリスト NIL
Tuber には NIL という値が定義済みです。
NIL は単体でリストとみなされます。値の無いリスト、要素数が 0 のリストを表現します。
CONS でリストに値を追加する
リストに値を追加するには CONS を使います。
例えば 1 つの値 :a のみを内包したリストは次のように書けます。
CONS(:a, NIL) # 1つの値 `:a` のみを内包したリスト1 要素のタプルは、とある値と NIL のタプルのことです。
CONS によって次々に値を追加することで 2 要素, 3 要素のリストを次々に作ることが可能です。
CONS(:b, CONS(:a, NIL)) # 2要素のリストCONS(:c, CONS(:b, CONS(:a, NIL))) # 3要素のリストとある値とリストを CONS によって連結したものもまたリストになります。
リストから値を取り出す
リストから値を取り出すにはどうすればいいでしょうか？
タプルによって値を繰り返し連結したものがリストであることを思い出せば、タプルから値を取り出す関数 CAR, CDR が使えることがわかります。
l = CONS(:c, CONS(:b, CONS(:a, NIL))) # 3要素のリスト
CAR(l) # 最初の要素 :c を取り出す
CDR(l) # 最初の要素を除いた残りのリストを取り出す # CONS(:b, CONS(:a, NIL)) と同等
CAR(CDR(l)) # :b を取り出す
CDR(CDR(l)) # CONS(:a, NIL) と同等空リスト判定 IS_NIL
リストに対する演算が 1 つだけ用意されています。
IS_NIL は引数として受け取ったリストが空リストかどうか判定し TRUE または FALSE を返します。
IS_NIL(NIL) # => TRUEIS_NIL(CONS(:a, NIL)) # => FALSEIS_NIL(CONS(:b, CONS(:a, NIL))) # => FALSE