お気楽 Go 言語プログラミング入門

はじめに

今回はクロージャを使って Lisp 風の「連結リスト (linked list)」を作ってみましょう。最初に、Lisp のリストについて簡単に説明します。

●Lisp のリスト

Lisp のリストは複数の「コンスセル (cons cell)」を連結したものです。ひとつのコンスセルには、データを格納する CAR (カー) という場所と、次のセルを連結する CDR (クダー) という場所からなっています。次の図を見てください。

 CAR CDR       CAR CDR  
┌─┬─┐    ┌─┬─┐
│・│・┼─→│・│・┼→終端 (NIL)
└┼┴─┘    └┼┴─┘
  ↓            ↓
  １            ２

            図 : リストの構造

上図では、コンスセルを箱で表しています。左側の CAR がデータを格納する場所で、CDR が次のコンスセルと連結しています。上図の例では、先頭のコンスセルの CAR には 1 が格納され、CDR は次のコンスセルと連結しています。2 番目のコンスセルには CAR に 2 というデータが格納されています。このあとに接続されるコンスセルはもうないので、CDR にはリストの終わりを示す特別なデータ (NIL) が格納されます。このようなリストを Lisp では (1 2) と表記します。

また、Lisp のリストは CAR にリストを格納して、リストを入れ子にすることができます。次の図を見てください。

 ┌─┬─┐  ┌─┬─┐  ┌─┬─┐
 │・│・┼→│・│・┼→│・│／│  ／ : NIL
 └┼┴─┘  └┼┴─┘  └┼┴─┘
   ↓          │          │
   １          │          │
               │          ↓
               │        ┌─┬─┐  ┌─┬─┐  ┌─┬─┐
               │        │・│・┼→│・│・┼→│・│／│
               │        └┼┴─┘  └┼┴─┘  └┼┴─┘
               │          ↓          ↓          ↓
               │          ３         １２        １３
               ↓
             ┌─┬─┐  ┌─┬─┐  ┌─┬─┐
             │・│・┼→│・│・┼→│・│／│
             └┼┴─┘  └┼┴─┘  └┼┴─┘
               ↓          ↓          ↓
               ２         １０        １１

                  図 : リストの階層構造

上図のリストを Lisp で記述すると (1 (2 10 11) (3 12 13)) になります。それから、Lisp のリストは異なるデータ型でもいっしょに格納することができます。

●リストの表記法

ここで Lisp でのリストの表記法について簡単に説明しておきましょう。コンスセルの CDR は NIL だけではなく他のデータを格納することもできます。Lisp ではリストの終端が NIL 以外のデータの場合、そのリストを次のように表します。

 ┌─┬─┐            ┌─┬─┐
 │・│・┼─→ NIL    │・│・┼─→２
 └┼┴─┘            └┼┴─┘
   ↓                    ↓
   １                    １

 (1) ≡ (1 . NIL)      (1 . 2)

 ┌─┬─┐    ┌─┬─┐    ┌─┬─┐
 │・│・┼─→│・│・┼─→│・│・┼─→ NIL 
 └┼┴─┘    └┼┴─┘    └┼┴─┘
   ↓            ↓            ↓
   １            ２            ３

     (1 2 3) ≡ (1 . (2 . (3 . NIL)))

    図 : リストの終端 (その１)

左右のカッコの中間にドット ( . ) を置き、左側に CAR のデータを、右側に CDR のデータを書きます。つまり、リスト (1) は (1 . NIL) と表すことができます。このようなデータを Lisp では「ドット対 (dotted pair)」と呼びます。たとえば、CAR が 1 で CDR が 2 であれば (1 . 2) となります。普通のリストも次のようにドット対を使って表現できます。

(1)           ≡ (1 . NIL)
(1 2 3)       ≡ (1 . (2 . (3 . NIL)))
((1 2) (3 4)) ≡ ((1 . (2 . NIL)) . ((3 . (4 . NIL)) . NIL))
((1 2) 3 4)   ≡ ((1 . (2 . NIL)) . (3 . (4 . NIL)))

それでは、リスト (1 2 3) の終端を 4 に変えてみましょう。ドット対を使った表記法では、(1 . (2 . (3 . 4))) となりますが、これは (1 2 3 . 4) と表すことができます。

 ┌─┬─┐    ┌─┬─┐    ┌─┬─┐
 │・│・┼─→│・│・┼─→│・│・┼─→４ 
 └┼┴─┘    └┼┴─┘    └┼┴─┘
   ↓            ↓            ↓
   １            ２            ３

     (1 2 3 . 4) ≡ (1 . (2 . (3 . 4)))

    図 : リストの終端（その２）

このように、NIL 以外のアトムで終端されたリストを Lisp では「ドットリスト (dotted list)」と呼びます。

ドットの後ろは CDR にセットするデータを指定するのですから、複数のデータを書いたり省略してはいけません。次の場合、Lisp ではエラーになります。

( . 1)       ; CAR がない
(1 . )       ; CDR がない
(1 . 2 3)    ; CDR にデータが複数ある
(1 . . 2)    ; ドットが複数ある
(1 . 2 . 3)

●クロージャによる連結リストの実装

Lisp / Scheme の場合、関数 cons でコンスセルを生成し、関数 car でリストの先頭要素を取り出し、関数 cdr でリストから先頭要素を取り除きます。したがって、Lisp / Scheme の cons, car, cdr には次の関係が成り立ちます。

x == car(cons(x, y)) => 1 (true)
y == cdr(cons(x, y)) => 1 (true)

演算子 == は今回作成した電卓プログラムの等値演算子と考えてください。Scheme で表すと次のようになります。

(eq? x (car (cons x y))) => #t
(eq? y (cdr (cons x y))) => #t

Scheme の場合、#t は true を、#f は false を表します。実際に Gauche (Scheme) での実行例を示します。

gosh> (define a 10)
a
gosh> (define b 20)
b
gosh> (eq? a (car (cons a b)))
#t
gosh> (eq? b (cdr (cons a b)))
#t

ここで (cons x y) で生成したオブジェクトがセルではない場合を考えてみましょう。もし、そのオブジェクトに car を適用すれば cons の第 1 引数 x を返し、cdr を適用すれば第 2 引数を返すことができれば、セルと同じことが実現できます。

そこで、cons はセルではなくクロージャを返すことにしましょう。クロージャは引数 x, y の値を保持することができます。そして、このクロージャは引数に関数を受け取ることにします。あとは、この関数に引数 x, y を渡して評価すれば car と cdr を実現することができます。

Gauche でプログラムすると次のようになります。

gosh> (define (cons2 x y) (lambda (z) (z x y)))
cons2
gosh> (define (car2 x) (x (lambda (a b) a)))
car2
gosh> (define (cdr2 x) (x (lambda (a b) b)))
cdr2
gosh> (car2 (cons2 'a 'b))
a
gosh> (cdr2 (cons2 'a 'b))
b
gosh> (define a (cons2 1 (cons2 2 (cons2 3 4))))
a
gosh> (car2 a)
1
gosh> (car2 (cdr2 a))
2
gosh> (car2 (cdr2 (cdr2 a)))
3
gosh> (cdr2 (cdr2 (cdr2 a)))
4

lambda はラムダ式 (匿名関数) を表します。関数 cons2 はクロージャを返します。このクロージャは引数 z に関数を受け取り、その関数に x, y を渡して評価します。car2 は引数 x にクロージャを渡して評価し、第 1 引数 a を返します。これで car と同じ動作になります。同様に、cdr2 は引数 x にクロージャを渡して評価し、第 2 引数 b を返します。これで cdr と同じ動作になります。

クロージャをサポートしているプログラミング言語であれば、Lisp / Scheme と同じように cons, car, cdr を作ることができます。電卓プログラムで cons, car, cdr をプログラムすると次のようになります。

リスト : 連結リストの基本関数

def cons(x, y)
  fn(z) z(x, y) end
end

def car(z)
  z(fn(x, y) x end)
end

def cdr(z)
  z(fn(x, y) y end)
end

それでは実際に試してみましょう。

Calc> def cons(x, y) fn(z) z(x, y) end end
cons
Calc> def car(z) z(fn(x, y) x end) end
car
Calc> def cdr(z) z(fn(x, y) y end) end
cdr
Calc> a = cons(1, 0);
<Closure>
Calc> car(a);
1
Calc> cdr(a);
0
Calc> b = cons(2, a);
<Closure>
Calc> car(b);
2
Calc> cdr(b);
<Closure>
Calc> car(cdr(b));
1

このように、クロージャを使って連結リストを作成することができます。

●リストの表示

それでは、連結リストを操作する関数を作っていきましょう。最初に、連結リストを表示する関数 printlist を作ります。

リスト : 連結リストの表示

nil = "NIL";

def pair(xs) isFunc(xs) end

def null(xs) isStr(xs) and xs == nil end

def printlist(xs)
  print("("),
  while pair(xs) do
    if pair(car(xs)) or null(car(xs)) then
      printlist(car(xs))
    else
      print(car(xs))
    end,
    if pair(cdr(xs)) then print(" ") end,
    xs = cdr(xs)
  end,
  if !null(xs) then
    begin print(" . "), print(xs) end
  end,
  print(")"),
  nil
end

連結リストの表示は Lisp / Scheme の表示に合わせます。リストはカッコで囲って、要素は空白で区切ります。セルの CDR 部がリストでない場合、ドット ( . ) で区切ります。CDR 部が空リストの場合、NIL は表示しません。この仕様をそのままプログラムしたものが printlist です。

空リストは文字列 "NIL" で表すことにします。これを変数 nil にセットします。次に、リストを判定する述語 pair と空リストを判定する述語 null を定義します。pair は isFunc を呼び出すだけです。null は引数 xs が文字列で、nil と等しければ true を返します。

printlist は最初に '(' を表示して、while ループで要素を順番に出力します。このとき、要素 car(xs) がリストまたは空リストであれば、printlist を再帰呼び出しします。これで入れ子のリストも表示することができます。

次に、cdr(xs) がリストであれば、要素を空白で区切るため putc で空白 ' ' を出力します。そして、xs を cdr(xs) に書き換えて処理を繰り返します。ループを終了したら、xs が空リストでなければ、要素をドットで区切って print で xs を表示します。最後に print で ")" を表示します。

簡単な実行例を示します。

Calc> a = cons(1, nil);
<Closure>
Calc> printlist(a);
(1)NIL
Calc> b = cons(2, a);
<Closure>
Calc> printlist(b);
(2 1)NIL
Calc> c = cons(3, b);
<Closure>
Calc> printlist(c);
(3 2 1)NIL
Calc> printlist(cons(c, b));
((3 2 1) 2 1)NIL
Calc> printlist(cons(c, cons(b, a)));
((3 2 1) (2 1) 1)NIL
Calc> printlist(cons(1, 2));
(1 . 2)NIL
Calc> printlist(cons(nil, nil));
(())NIL

●リストの生成

次はリストを生成する関数 makelist, iota, tabulate を作ります。

リスト : リストの生成

def makelist(n, x)
  let
    xs = nil
  in
    while n > 0 do
      xs = cons(x, xs),
      n = n - 1
    end,
    xs
  end
end

def iota(n, m)
  let
    xs = nil
  in
    while m >= n do
      xs = cons(m, xs),
      m = m - 1
    end,
    xs
  end
end

def tabulate(f, n, m)
  let
    xs = nil
  in
    while m >= n do
      xs = cons(f(m), xs),
      m = m - 1
    end,
    xs
  end
end

makelist(n, x) は、x を n 個格納したリストを生成します。iota(n, m) は n から m までの整数列を返します。tabulate(f, n, m) は高階関数で、n から m までの整数列を生成し、その要素に関数 f を適用した結果をリストに格納して返します。つまり、map(f, iota(n, m)) と同じ動作になります。

簡単な実行例を示します。

Calc> printlist(makelist(10, 0));
(0 0 0 0 0 0 0 0 0 0)NIL
Calc> printlist(makelist(10, nil));
(() () () () () () () () () ())NIL
Calc> printlist(iota(1, 10));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(tabulate(fn(x) x * 2 end, 1, 10));
(2 4 6 8 10 12 14 16 18 20)NIL

●リストの基本的な操作

次は、リストの基本的な操作関数を定義しましょう。次のリストを見てください。

リスト : リストの基本操作関数

def nth(xs, n)
  if null(xs) then
    nil
  else
    if n == 0 then
      car(xs)
    else
      nth(cdr(xs), n - 1)
    end
  end
end

def length(xs)
  let
    c = 0
  in
    while !null(xs) do
      c = c + 1,
      xs = cdr(xs)
    end,
    c
  end
end

def reverse(xs)
  let
    ys = nil
  in
    while !null(xs) do
      ys = cons(car(xs), ys),
      xs = cdr(xs)
    end,
    ys
  end
end

def eql(xs, ys)
  if (isInt(xs) and isInt(ys)) or
     (isFlt(xs) and isFlt(ys)) or
     (isStr(xs) and isStr(xs)) then
    xs == ys
  end
end

def member(x, ls)
  while !null(ls) and !eql(car(ls), x) do
    ls = cdr(ls)
  end,
  ls
end

def append(xs, ys)
  if null(xs) then
    ys
  else
    cons(car(xs), append(cdr(xs), ys))
  end
end

def remove(x, ls)
  if null(ls) then
    nil
  else
    if eql(x, car(ls)) then
      remove(x, cdr(ls))
    else
      cons(car(ls), remove(x, cdr(ls)))
    end
  end
end

def take(xs, n)
  if n == 0 or null(xs) then
    nil
  else
    cons(car(xs), take(cdr(xs), n - 1))
  end
end

def drop(xs, n)
  if n == 0 or null(xs) then
    xs
  else
    drop(cdr(xs), n - 1)
  end
end

nth はリストの n 番目の要素を取り出します。リストは 0 から数えるものとします。範囲外は nil を返します。length はリストの長さを返します。reverse はリストを反転します。member はリストから x を探します。見つけた場合はリストを返し、見つからない場合は nil を返します。eql はデータの等値を判定する述語です。Lisp の eql はデータ型が同じで、値が同じ場合に真を返します。たとえば、整数 1 と実数 1.0 を比較すると eql は偽を返します。

append は 2 つのリストを連結します。引数 xs のリストはコピーされることに注意してください。remove は x と等しい要素を削除したリストを返します。take はリスト xs の先頭から n 個の要素を取り出します。drop はリスト xs の先頭から n 個の要素を取り除きます。

それでは簡単な実行例を示します。

Calc> a = iota(1, 10);
<Closure>
Calc> printlist(a);
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> nth(a, 0);
1
Calc> nth(a, 9);
10
Calc> nth(a, 10);
NIL
Calc> length(a);
10
Calc> printlist(reverse(a));
(10 9 8 7 6 5 4 3 2 1)NIL
Calc> printlist(member(1, a));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(member(5, a));
(5 6 7 8 9 10)NIL
Calc> printlist(member(10, a));
(10)NIL
Calc> printlist(member(11, a));
()NIL
Calc> b = iota(11, 20);
<Closure>
Calc> printlist(append(a, b));
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)NIL
Calc> printlist(remove(1, a));
(2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(remove(5, a));
(1 2 3 4 6 7 8 9 10)NIL
Calc> printlist(remove(10, a));
(1 2 3 4 5 6 7 8 9)NIL
Calc> printlist(remove(11, a));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(take(a, 5));
(1 2 3 4 5)NIL
Calc> printlist(take(a, 0));
()NIL
Calc> printlist(take(a, 10));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(take(a, 11));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(drop(a, 5));
(6 7 8 9 10)NIL
Calc> printlist(drop(a, 0));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> printlist(drop(a, 10));
()NIL
Calc> printlist(drop(a, 11));
()NIL

●高階関数

高階関数も簡単に作ることができます。

リスト : 高階関数

def map(f, xs)
  if null(xs) then
    nil
  else 
    cons(f(car(xs)), map(f, cdr(xs)))
  end
end

def filter(f, xs)
  if null(xs) then
    nil
  else
    if f(car(xs)) then
      cons(car(xs), filter(f, cdr(xs)))
    else
      filter(f, cdr(xs))
    end
  end
end

def foldl(f, a, xs)
  while !null(xs) do
    a = f(car(xs), a),
    xs = cdr(xs)
  end,
  a
end

def foldr(f, a, xs)
  if null(xs) then
    a
  else
    f(car(xs), foldr(f, a, cdr(xs)))
  end
end

def foreach(f, ls)
  while !null(ls) do
    f(car(ls)),
    ls = cdr(ls)
  end
end

map はマッピングを、filter はフィルターを、foldl, foldr は畳み込みを行います。foreach はリストの要素に関数 f を適用しますが、その副作用が目的となります。

簡単な実行例を示します。

Calc> printlist(map(fn(x) x * x end, a));
(1 4 9 16 25 36 49 64 81 100)NIL
Calc> printlist(filter(fn(x) x % 2 == 0 end, a));
(2 4 6 8 10)NIL
Calc> foldl(fn(x, a) x + a end, 0, a);
55
Calc> printlist(foldl(fn(x, a) cons(x, a) end, nil, a));
(10 9 8 7 6 5 4 3 2 1)NIL
Calc> foldr(fn(x, a) x + a end, 0, a);
55
Calc> printlist(foldr(fn(x, a) cons(x, a) end, nil, a));
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> foreach(println, a);
1
2
3
4
5
6
7
8
9
10
0

foreach の返り値は if の else 節がないため 0 になります。

●等値の判定

電卓プログラムの場合、等値演算子 ==, != で判定できるのは整数, 実数, 文字列だけです。Lisp / Scheme と同様に、リストとリストの等値を判定する述語 equal があると便利です。次のリストを見てください。

リスト : 等値の判定

def equal(xs, ys)
  if pair(xs) and pair(ys) then
    if equal(car(xs), car(ys)) then
      equal(cdr(xs), cdr(ys))
    else
      0
    end
  else
    if !pair(xs) and !pair(ys) then
      eql(xs, ys)
    end
  end
end

等値の判定は簡単です。引数 xs, ys がリストの場合、その要素 car(xs) を equal で比較し、等しい場合は cdr(xs) と cdr(ys) を equal で比較します。xs と ys がどちらもリストではない場合は eql で判定します。そうでなければ、他方がリストになるので偽 (0) を返します。これで入れ子になったリストでも等値を判定することができます。

簡単な実行例を示します。

Calc> equal(cons(1, 2), cons(1, 2));
1
Calc> equal(cons(1, 2), cons(1, 0));
0
Calc> equal(cons(1, 2), cons(1, 2.0));
0
Calc> a = iota(1, 10);
<Closure>
Calc> equal(a, a);
1
Calc> b = iota(1, 5);
<Closure>
Calc> equal(a, b);
0

●簡単な例題

最後に、リスト操作関数を使った簡単なプログラムを作りましょう。

リスト : 簡単な例題

def zip(xs, ys)
  if null(xs) or null(ys) then
    nil
  else
    cons(cons(car(xs), car(ys)), zip(cdr(xs), cdr(ys)))
  end
end

def flatten(ls)
  if null(ls) then
    nil
  else
    if pair(ls) then
      append(flatten(car(ls)), flatten(cdr(ls)))
    else
      cons(ls, nil)
    end
  end
end

def permSub(f, n, xs, a)
  if n == 0 then
    f(reverse(a))
  else
    foreach(fn(x) permSub(f, n - 1, remove(x, xs), cons(x, a)) end, xs)
  end
end

def permutation(f, n, xs)
  permSub(f, n, xs, nil)
end

zip は 2 つのリスト xs, ys を受け取り、それぞれの要素をセルに格納したリストを返します。flatten はリストを平坦化する関数です。permutation はリスト xs から n 個の要素を選ぶ順列をすべて表示します。

簡単な実行例を示します。

Calc> a = iota(1, 8);
<Closure>
Calc> b = iota(11, 18);
<Closure>
Calc> printlist(zip(a, b));
((1 . 11) (2 . 12) (3 . 13) (4 . 14) (5 . 15) (6 . 16) (7 . 17) (8 . 18))NIL
Calc> printlist(flatten(zip(a, b)));
(1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18)NIL
Calc> permutation(printlist, 3, iota(1, 3));
(1 2 3)(1 3 2)(2 1 3)(2 3 1)(3 1 2)(3 2 1)0

リストのマージソートも簡単にプログラムできます。

リスト : マージソート

def merge(xs, ys, pred)
  if null(xs) or null(ys) then
    if null(xs) then ys else xs end
  else
    if pred(car(xs), car(ys)) then
      cons(car(xs), merge(cdr(xs), ys, pred))
    else
      cons(car(ys), merge(xs, cdr(ys), pred))
    end
  end
end

def mergeSort(xs, n, pred)
  if n == 1 then
    cons(car(xs), nil)
  else
    let
      m = n / 2
    in
      merge(mergeSort(xs, m, pred),
            mergeSort(drop(xs, m), n - m, pred),
            pred)
    end
  end
end

merge は 2 つのリストをマージ (併合) し、mergeSort は merge を使ってリストをソートします。

簡単な実行例を示します。

Calc> a = cons(1, cons(3, cons(5, cons(7, nil))));
<Closure>
Calc> b = cons(2, cons(4, cons(6, cons(8, nil))));
<Closure>
Calc> printlist(a);
(1 3 5 7)NIL
Calc> printlist(b);
(2 4 6 8)NIL
Calc> printlist(merge(a, b, fn(x, y) x < y end));
(1 2 3 4 5 6 7 8)NIL
Calc> a = cons(4, cons(5, cons(7, cons(6, cons(8, cons(3, cons(1, cons(9, cons(2, nil)))))))));
<Closure>
Calc> printlist(a);
(4 5 7 6 8 3 1 9 2)NIL
Calc> printlist(mergeSort(a, 9, fn(x, y) x < y end));
(1 2 3 4 5 6 7 8 9)NIL
Calc> printlist(mergeSort(a, 9, fn(x, y) x > y end));
(9 8 7 6 5 4 3 2 1)NIL

●リストの破壊的な修正

ところで、このままではコンスセルの CAR 部と CDR 部を破壊的に修正することはできません。Scheme の関数 set-car!, set-cdr! と同じ動作を実現する場合、cons が返すクロージャに値を書き換える処理を追加します。プログラムは次のようになります。

リスト : リストの破壊的な修正

def cons(x, y)
  fn(n, v)
    if n < 2 then
      if n == 0 then
        x
      else
        y
      end
    else
      if n == 2 then
        x = v
      else
        y = v
      end
    end
  end
end

def car(z) z(0, 0) end

def cdr(z) z(1, 0) end

def setCar(z, v) z(2, v) end

def setCdr(z, v) z(3, v) end

クロージャの第 1 引数 n で実行する処理を指定します。0 が car, 1 が cdr です。2 が setCar で x の値を引数 v に書き換えます。3 が setCdr で y の値を v に書き換えます。あとは、関数 car, cdr, setCar, setCdr で適切な値を指定してクロージャを呼び出すだけです。あとのプログラムは修正しなくても大丈夫です。

簡単な実行例を示しましょう。

Calc> a = cons(1, 2);
<Closure>
Calc> printlist(a);
(1 . 2)NIL
Calc> setCar(a, 10);
10
Calc> printlist(a);
(10 . 2)NIL
Calc> setCdr(a, 20);
20
Calc> printlist(a);
(10 . 20)NIL

リストの破壊的操作の例題として、リストの要素を書き換える書き換える listSet とリストを破壊的に反転する関数 nreverse を作ります。

リスト : リストの破壊的な操作

def listSet(xs, n, v)
  if null(xs) then
    nil
  else
    if n == 0 then
      setCar(xs, v)
    else
      listSet(cdr(xs), n - 1, v)
    end
  end
end

def nrevSub(xs, a)
  if null(xs) then
    a
  else
    let ys = cdr(xs) in
      setCdr(xs, a),
      nrevSub(ys, xs)
    end
  end
end

def nreverse(xs)
  nrevSub(xs, nil)
end

listSet は setCar で指定した位置の要素を書き換えます。nreverse は setCdr でセルの CDR 部を書き換えることでリストを反転しています。

簡単な実行例を示します。

Calc> b = iota(1, 10);
<Closure>
Calc> printlist(b);
(1 2 3 4 5 6 7 8 9 10)NIL
Calc> listSet(b, 0, 100);
100
Calc> printlist(b);
(100 2 3 4 5 6 7 8 9 10)NIL
Calc> listSet(b, 5, 200);
200
Calc> printlist(b);
(100 2 3 4 5 200 7 8 9 10)NIL
Calc> listSet(b, 9, 300);
300
Calc> printlist(b);
(100 2 3 4 5 200 7 8 9 300)NIL
Calc> a = iota(1, 10);
<Closure>
Calc> b = nreverse(a);
<Closure>
Calc> printlist(b);
(10 9 8 7 6 5 4 3 2 1)NIL
Calc> printlist(a);
(1)NIL

今回はここまでです。次回は電卓プログラムにデータ構造として「連結リスト」を追加してみましょう。

●プログラムリスト

//
// list.cal : クロージャによる連結リストの実装
//
//            Copyright (C) 2014-2021 Makoto Hiroi
//

// 空リスト
nil = "NIL";

// リストの基本操作
def cons(x, y)
  fn(n, v)
    if n < 2 then
      if n == 0 then
        x
      else
        y
      end
    else
      if n == 2 then
        x = v
      else
        y = v
      end
    end
  end
end

def car(z) z(0, 0) end

def cdr(z) z(1, 0) end

def setCar(z, v) z(2, v) end

def setCdr(z, v) z(3, v) end

// 述語
def pair(xs) isFunc(xs) end

def null(xs) isStr(xs) and xs == nil end

def eql(xs, ys)
  if (isInt(xs) and isInt(ys)) or
     (isFlt(xs) and isFlt(ys)) or
     (isStr(xs) and isStr(xs)) then
    xs == ys
  end
end

def equal(xs, ys)
  if pair(xs) and pair(ys) then
    if equal(car(xs), car(ys)) then
      equal(cdr(xs), cdr(ys))
    else
      0
    end
  else
    if !pair(xs) and !pair(ys) then
      eql(xs, ys)
    end
  end
end

// リストの参照
def nth(xs, n)
  if null(xs) then
    nil
  else
    if n == 0 then
      car(xs)
    else
      nth(cdr(xs), n - 1)
    end
  end
end

// 長さ
def length(xs)
  let
    c = 0
  in
    while !null(xs) do
      c = c + 1,
      xs = cdr(xs)
    end,
    c
  end
end

// 反転
def reverse(xs)
  let
    ys = nil
  in
    while !null(xs) do
      ys = cons(car(xs), ys),
      xs = cdr(xs)
    end,
    ys
  end
end

// リストに x が含まれているか
def member(x, ls)
  while !null(ls) and !eql(car(ls), x) do
    ls = cdr(ls)
  end,
  ls
end

// 連結
def append(xs, ys)
  if null(xs) then
    ys
  else
    cons(car(xs), append(cdr(xs), ys))
  end
end

// x と等しい要素を削除
def remove(x, ls)
  if null(ls) then
    nil
  else
    if eql(x, car(ls)) then
      remove(x, cdr(ls))
    else
      cons(car(ls), remove(x, cdr(ls)))
    end
  end
end

// マッピング
def map(f, xs)
  if null(xs) then
    nil
  else 
    cons(f(car(xs)), map(f, cdr(xs)))
  end
end

// フィルター
def filter(f, xs)
  if null(xs) then
    nil
  else
    if f(car(xs)) then
      cons(car(xs), filter(f, cdr(xs)))
    else
      filter(f, cdr(xs))
    end
  end
end

// 畳み込み
def foldl(f, a, xs)
  while !null(xs) do
    a = f(car(xs), a),
    xs = cdr(xs)
  end,
  a
end

def foldr(f, a, xs)
  if null(xs) then
    a
  else
    f(car(xs), foldr(f, a, cdr(xs)))
  end
end

// 巡回
def foreach(f, ls)
  while !null(ls) do
    f(car(ls)),
    ls = cdr(ls)
  end
end

// 2 つのリストをまとめる
def zip(xs, ys)
  if null(xs) or null(ys) then
    nil
  else
    cons(cons(car(xs), car(ys)), zip(cdr(xs), cdr(ys)))
  end
end

// 平坦化
def flatten(ls)
  if null(ls) then
    nil
  else
    if pair(ls) then
      append(flatten(car(ls)), flatten(cdr(ls)))
    else
      cons(ls, nil)
    end
  end
end

// リストの先頭から n 個の要素を取り出す
def take(xs, n)
  if n == 0 or null(xs) then
    nil
  else
    cons(car(xs), take(cdr(xs), n - 1))
  end
end

// リストの先頭から n 個の要素を取り除く
def drop(xs, n)
  if n == 0 or null(xs) then
    xs
  else
    drop(cdr(xs), n - 1)
  end
end

// リストの生成
def makelist(n, x)
  let
    xs = nil
  in
    while n > 0 do
      xs = cons(x, xs),
      n = n - 1
    end,
    xs
  end
end

def iota(n, m)
  let
    xs = nil
  in
    while m >= n do
      xs = cons(m, xs),
      m = m - 1
    end,
    xs
  end
end

def tabulate(f, n, m)
  let
    xs = nil
  in
    while m >= n do
      xs = cons(f(m), xs),
      m = m - 1
    end,
    xs
  end
end

// リストの表示
def printlist(xs)
  print("("),
  while pair(xs) do
    if pair(car(xs)) or null(car(xs)) then
      printlist(car(xs))
    else
      print(car(xs))
    end,
    if pair(cdr(xs)) then print(" ") end,
    xs = cdr(xs)
  end,
  if !null(xs) then
    begin print(" . "), print(xs) end
  end,
  print(")"),
  nil
end

// ベクタをリストに変換する
def fromVector(xs)
  let
    i = len(xs) - 1,
    a = nil
  in
    while i >= 0 do
      a = cons(xs[i], a),
      i = i - 1
    end,
    a
  end
end

// 順列
def permSub(f, n, xs, a)
  if n == 0 then
    f(reverse(a))
  else
    foreach(fn(x) permSub(f, n - 1, remove(x, xs), cons(x, a)) end, xs)
  end
end

def permutation(f, n, xs)
  permSub(f, n, xs, nil)
end

// 組み合わせ
def combSub(f, n, xs, a)
  if n == 0 then
    f(reverse(a))
  else
    if length(xs) == n then
      f(append(reverse(a), xs))
    else
      begin
        combSub(f, n - 1, cdr(xs), cons(car(xs), a)),
        combSub(f, n, cdr(xs), a)
      end
    end
  end
end

def combination(f, n, xs)
  combSub(f, n, xs, nil)
end

// マージ
def merge(xs, ys, pred)
  if null(xs) or null(ys) then
    if null(xs) then ys else xs end
  else
    if pred(car(xs), car(ys)) then
      cons(car(xs), merge(cdr(xs), ys, pred))
    else
      cons(car(ys), merge(xs, cdr(ys), pred))
    end
  end
end

// マージソート
def mergeSort(xs, n, pred)
  if n == 1 then
    cons(car(xs), nil)
  else
    let
      m = n / 2
    in
      merge(mergeSort(xs, m, pred),
            mergeSort(drop(xs, m), n - m, pred),
            pred)
    end
  end
end

// リストの破壊的な修正
def listSet(xs, n, v)
  if null(xs) then
    nil
  else
    if n == 0 then
      setCar(xs, v)
    else
      listSet(cdr(xs), n - 1, v)
    end
  end
end

// リストを破壊的に反転する
def nrevSub(xs, a)
  if null(xs) then
    a
  else
    let ys = cdr(xs) in
      setCdr(xs, a),
      nrevSub(ys, xs)
    end
  end
end

def nreverse(xs)
  nrevSub(xs, nil)
end