今回はクロージャを使って「連結リスト (linked list) 」を作ってみましょう。
Lisp / Scheme の場合、コンス演算子 (::) の役割を関数 cons で、関数 hd, tl の役割を関数 car, cdr で行います。ただし、SML/NJ のリストと相違点があり、Lisp / Scheme の cons は第 2 引数にリスト以外の値を与えてもかまいません。
したがって、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); <Function> Calc> car(a); 1 Calc> cdr(a); 0 Calc> b = cons(2, a); <Function> Calc> car(b); 2 Calc> cdr(b); <Function> Calc> car(cdr(b)); 1
このように、クロージャを使って連結リストを作成することができます。
ところで、car, cdr, cons は簡単に実装できますが、これだけで連結リストを操作する関数を作るのはちょっと苦しいので、データ型を判定する述語を電卓プログラムに追加します。次のリストを見てください。
リスト : データ型の判定 val True = Integer(1) val False = Integer(0) fun isNil(Nil) = True | isNil(_) = False fun isInteger(Integer(_)) = True | isInteger(_) = False fun isFloat(Float(_)) = True | isFloat(_) = False fun isFunction(Func(_)) = True | isFunction(_) = False (* 大域変数 *) val global_env = ref [("sqrt", ref (Func(F1(call_real_func1 Math.sqrt)))), ・・・ 省略 ・・・ ("print", ref (Func(F1 print_value))), ("putc", ref (Func(F1 put_char))), ("isNil", ref (Func(F1 isNil))), ("isInteger", ref (Func(F1 isInteger))), ("isFloat", ref (Func(F1 isFloat))), ("isFunction", ref (Func(F1 isFunction))), ("nil", ref Nil)]
空リストは Nil で表します。Nil は変数 nil に格納しておきます。データ型を判定する述語は isNil, isInteger, isFloat, isFunction の 4 つです。それぞれ、データが Nil, Integer, Float, Function であれば真 (1) を返し、そうでなければ偽 (0) を返します。
それから、print はデータを表示したあと改行しないで Nil を返すように修正します。putc は文字を出力する関数です。文字は整数値 (アスキーコード) で指定します。また、データを表示する関数 print_value で、Nil は表示しないように修正します。
それでは、連結リストを操作する関数を作っていきましょう。最初に、連結リストを表示する関数 printlist を作ります。
リスト : 連結リストの表示 def pair(xs) isFunction(xs) end def null(xs) isNil(xs) end def printlist(xs) putc(40), 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 putc(32) end, xs = cdr(xs) end, if not null(xs) then putc(32), putc(46), putc(32), print(xs) end, putc(41), nil end
連結リストの表示は Lisp / Scheme の表示に合わせます。リストはカッコで囲って、要素は空白で区切ります。セルの CDR 部がリストでない場合、ドット ( . ) で区切ります。CDR 部が空リストの場合、Nil は表示しません。この仕様をそのままプログラムしたものが printlist です。
最初に、リストを判定する述語 pair と空リストを判定する述語 null を定義します。これは isFunction と isNil を呼び出すだけです。printlist は最初に '(' を表示して、while ループで要素を順番に出力します。このとき、要素 car(xs) がリストまたは空リストであれば、printlist を再帰呼び出しします。これで入れ子のリストも表示することができます。
次に、cdr(xs) がリストであれば、要素を空白で区切るため putc で空白 ' ' を出力します。そして、xs を cdr(xs) に書き換えて処理を繰り返します。ループを終了したら、xs が空リスト Nil でなければ、要素をドットで区切って print で xs を表示します。最後に putc で ')' を表示します。
簡単な実行例を示します。
Calc> a = cons(1, nil); <Function> Calc> printlist(a); (1) Calc> b = cons(2, a); <Function> Calc> printlist(b); (2 1) Calc> c = cons(3, b); <Function> Calc> printlist(c); (3 2 1) Calc> printlist(cons(c, b)); ((3 2 1) 2 1) Calc> printlist(cons(c, cons(b, a))); ((3 2 1) (2 1) 1) Calc> printlist(cons(1, 2)); (1 . 2) Calc> printlist(cons(nil, nil)); (())
次はリストを生成する関数 makelist, iota, tabulate を作ります。
リスト : リストの生成 def makelist0(n, x) if n == 0 then nil else cons(x, makelist0(n - 1, x)) end end def makelist(n, x) let rec iter = fn(n, a) if n == 0 then a else iter(n - 1, cons(x, a)) end end in iter(n, nil) end end def iota0(n, m) if n > m then nil else cons(n, iota0(n + 1, m)) end end def iota(n, m) let rec iter = fn(m, a) if m < n then a else iter(m - 1, cons(m, a)) end end in iter(m, nil) end end def tabulate0(f, n, m) if n > m then nil else cons(f(n), tabulate0(f, n + 1, m)) end end def tabulate(f, n, m) let rec iter = fn(m, a) if m < n then a else iter(m - 1, cons(f(m), a)) end end in iter(m, nil) end end
makelist(n, x) は、x を n 個格納したリストを生成します。makelist は makelist0 を末尾再帰に書き直したものです。iota(n, m) は n から m までの整数列を返します。iota は iota0 を末尾再帰に書き直したものです。tabulate(f, n, m) は高階関数で、n から m までの整数列を生成し、その要素に関数 f を適用した結果をリストに格納して返します。つまり、map(f, iota(n, m)) と同じ動作になります。tabulate は tabulate0 を末尾再帰に書き直したものです。
簡単な実行例を示します。
Calc> printlist(makelist(10, 0)); (0 0 0 0 0 0 0 0 0 0) Calc> printlist(makelist(10, nil)); (() () () () () () () () () ()) Calc> printlist(iota(1, 10)); (1 2 3 4 5 6 7 8 9 10) Calc> printlist(tabulate(fn(x) x * 2 end, 1, 10)); (2 4 6 8 10 12 14 16 18 20)
次は、リストの基本的な操作関数を定義しましょう。次のリストを見てください。
リスト : リストの基本操作関数 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 length0(xs) if null(xs) then 0 else 1 + length0(cdr(xs)) end end def length(xs) let rec iter = fn(xs, n) if null(xs) then n else iter(cdr(xs), n + 1) end end in iter(xs, 0) end end def reverse(xs) let rec iter = fn(ys, a) if null(ys) then a else iter(cdr(ys), cons(car(ys), a)) end end in iter(xs, nil) end def member(x, ls) if null(ls) then nil else if car(ls) == x then ls else member(x, cdr(ls)) end end 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 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 はリストの長さを返します。lenght は length0 を末尾再帰に書き直したものです。reverse はリストを反転します。これも末尾再帰になります。member はリストから x を探します。見つけた場合はリストを返し、見つからない場合は nil を返します。append は 2 つのリストを連結します。引数 xs のリストはコピーされることに注意してください。remove は x と等しい要素を削除したリストを返します。take はリスト xs の先頭から n 個の要素を取り出します。drop はリスト xs の先頭から n 個の要素を取り除きます。
それでは簡単な実行例を示します。
Calc> a = iota(1, 10); <Function> Calc> printlist(a); (1 2 3 4 5 6 7 8 9 10) Calc> nth(a, 0); 1 Calc> nth(a, 9); 10 Calc> nth(a, 10); Calc> length(a); 10 Calc> printlist(reverse(a)); (10 9 8 7 6 5 4 3 2 1) Calc> printlist(member(1, a)); (1 2 3 4 5 6 7 8 9 10) Calc> printlist(member(5, a)); (5 6 7 8 9 10) Calc> printlist(member(10, a)); (10) Calc> printlist(member(11, a)); () Calc> b = iota(11, 20); <Function> 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) Calc> printlist(remove(1, a)); (2 3 4 5 6 7 8 9 10) Calc> printlist(remove(5, a)); (1 2 3 4 6 7 8 9 10) Calc> printlist(remove(10, a)); (1 2 3 4 5 6 7 8 9) Calc> printlist(remove(11, a)); (1 2 3 4 5 6 7 8 9 10) Calc> printlist(take(a, 5)); (1 2 3 4 5) Calc> printlist(take(a, 0)); () Calc> printlist(take(a, 10)); (1 2 3 4 5 6 7 8 9 10) Calc> printlist(take(a, 11)); (1 2 3 4 5 6 7 8 9 10) Calc> printlist(drop(a, 5)); (6 7 8 9 10) Calc> printlist(drop(a, 0)); (1 2 3 4 5 6 7 8 9 10) Calc> printlist(drop(a, 10)); () Calc> printlist(drop(a, 11)); ()
高階関数も簡単に作ることができます。
リスト : 高階関数 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) if null(xs) then a else foldl(f, f(car(xs), a), cdr(xs)) end 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) if pair(ls) then f(car(ls)), foreach(f, cdr(ls)) end end
map はマッピングを、filter はフィルターを、foldl, foldr は畳み込みを行います。foreach は SML/NJ の app と同じで、リストの要素に関数 f を適用しますが、その副作用が目的となります。
簡単な実行例を示します。
Calc> printlist(map(fn(x) x * x end, a)); (1 4 9 16 25 36 49 64 81 100) Calc> printlist(filter(fn(x) x % 2 == 0 end, a)); (2 4 6 8 10) 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) 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) Calc> foreach(fn(x) print(x), putc(10) end, a); 1 2 3 4 5 6 7 8 9 10 0
foreach の返り値は if の else 節がないため 0 になります。値を表示したくない場合は nil を返すとよいでしょう。
電卓プログラムの場合、等値演算子 ==, <> で判定できるのは整数と実数だけです。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 (isInteger(xs) and isInteger(ys)) or (isFloat(xs) and isFloat(ys)) then xs == ys else null(xs) and null(ys) end end end
等値の判定は簡単です。引数 xs, ys がリストの場合、その要素 car(xs) を equal で比較し、等しい場合は cdr(xs) と cdr(ys) を equal で比較します。要素がリストでない場合、整数と実数はデータ型が同じで、値が等しければ真 (1) を返します。整数、実数でない場合、どちらも空リストであれば真 (1) を返し、そうでなければ、他方がリストになるので偽 (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); <Function> Calc> equal(a, a); 1 Calc> b = iota(1, 5); <Function> 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 permutation(n, xs) let rec perm = fn(m, ys, a) if m == n then printlist(reverse(a)), putc(10) else foreach(fn(x) perm(m + 1, remove(x, ys), cons(x, a)) end, ys) end end in perm(0, xs, nil) end end
zip は 2 つのリスト xs, ys を受け取り、それぞれの要素をセルに格納したリストを返します。flatten はリストを平坦化する関数です。permutation はリスト xs から n 個の要素を選ぶ順列をすべて表示します。
簡単な実行例を示します。
Calc> a = iota(1, 8); <Function> Calc> b = iota(11, 18); <Function> Calc> printlist(zip(a, b)); ((1 . 11) (2 . 12) (3 . 13) (4 . 14) (5 . 15) (6 . 16) (7 . 17) (8 . 18)) Calc> printlist(flatten(zip(a, b))); (1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18) Calc> permutation(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)))); <Function> Calc> b = cons(2, cons(4, cons(6, cons(8, nil)))); <Function> Calc> printlist(a); (1 3 5 7) Calc> printlist(b); (2 4 6 8) Calc> printlist(merge(a, b, fn(x, y) x < y end)); (1 2 3 4 5 6 7 8) Calc> a = cons(4, cons(5, cons(7, cons(6, cons(8, cons(3, cons(1, cons(9, cons(2, nil))))))))); <Function> Calc> printlist(a); (4 5 7 6 8 3 1 9 2) Calc> printlist(mergeSort(a, 9, fn(x, y) x < y end)); (1 2 3 4 5 6 7 8 9) Calc> printlist(mergeSort(a, 9, fn(x, y) x > y end)); (9 8 7 6 5 4 3 2 1)
ところで、このままではコンスセルの 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); <Function> Calc> printlist(a); (1 . 2) Calc> setCar(a, 10); 10 Calc> printlist(a); (10 . 2) Calc> setCdr(a, 20); 20 Calc> printlist(a); (10 . 20)
リストの破壊的操作の例題として、リストの要素を書き換える書き換える 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 nreverse(xs) let rec iter = fn(xs, a) if null(xs) then a else let ys = cdr(xs) in setCdr(xs, a), iter(ys, xs) end end end in iter(xs, nil) end end
listSet は setCar で指定した位置の要素を書き換えます。nreverse は setCdr でセルの CDR 部を書き換えることでリストを反転しています。
簡単な実行例を示します。
Calc> b = iota(1, 10); <Function> Calc> printlist(b); (1 2 3 4 5 6 7 8 9 10) Calc> listSet(b, 0, 100); 100 Calc> printlist(b); (100 2 3 4 5 6 7 8 9 10) Calc> listSet(b, 5, 200); 200 Calc> printlist(b); (100 2 3 4 5 200 7 8 9 10) Calc> listSet(b, 9, 300); 300 Calc> printlist(b); (100 2 3 4 5 200 7 8 9 300) Calc> a = iota(1, 10); <Function> Calc> b = nreverse(a); <Function> Calc> printlist(b); (10 9 8 7 6 5 4 3 2 1) Calc> printlist(a); (1)
リスト : 連結リストライブラリ 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) isFunction(xs) end def null(xs) isNil(xs) 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 length0(xs) if null(xs) then 0 else 1 + length0(cdr(xs)) end end def length(xs) let rec iter = fn(xs, n) if null(xs) then n else iter(cdr(xs), n + 1) end end in iter(xs, 0) end end def reverse(xs) let rec iter = fn(ys, a) if null(ys) then a else iter(cdr(ys), cons(car(ys), a)) end end in iter(xs, nil) end end def member(x, ls) if null(ls) then nil else if car(ls) == x then ls else member(x, cdr(ls)) end end 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 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) if null(xs) then a else foldl(f, f(car(xs), a), cdr(xs)) end 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) if pair(ls) then f(car(ls)), foreach(f, cdr(ls)) end end 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 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 def makelist0(n, x) if n == 0 then nil else cons(x, makelist0(n - 1, x)) end end def makelist(n, x) let rec iter = fn(n, a) if n == 0 then a else iter(n - 1, cons(x, a)) end end in iter(n, nil) end end def iota0(n, m) if n > m then nil else cons(n, iota0(n + 1, m)) end end def iota(n, m) let rec iter = fn(m, a) if m < n then a else iter(m - 1, cons(m, a)) end end in iter(m, nil) end end def tabulate0(f, n, m) if n > m then nil else cons(f(n), tabulate0(f, n + 1, m)) end end def tabulate(f, n, m) let rec iter = fn(m, a) if m < n then a else iter(m - 1, cons(f(m), a)) end end in iter(m, nil) 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 (isInteger(xs) and isInteger(ys)) or (isFloat(xs) and isFloat(ys)) then xs == ys else null(xs) and null(ys) end end end def printlist(xs) putc(40), 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 putc(32) end, xs = cdr(xs) end, if not null(xs) then putc(32), putc(46), putc(32), print(xs) end, putc(41), nil end def permutation(n, xs) let rec perm = fn(m, ys, a) if m == n then printlist(reverse(a)), putc(10) else foreach(fn(x) perm(m + 1, remove(x, ys), cons(x, a)) end, ys) end end in perm(0, xs, nil) end 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 nreverse(xs) let rec iter = fn(xs, a) if null(xs) then a else let ys = cdr(xs) in setCdr(xs, a), iter(ys, xs) end end end in iter(xs, nil) end end