今回は構造体の簡単な例題として、Lisp / Scheme 風の mutable な連結リスト (モジュール list) を作成します。
Lisp / Scheme のリストは複数の「コンスセル (cons cell)」を連結したものです。ひとつのコンスセルには、データを格納する CAR (カー) という場所と、次のセルを連結する CDR (クダー) という場所からなっています。次の図を見てください。
CAR CDR CAR CDR CAR CDR
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼→ NIL
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
図 : リスト内部の構造
上図はコンスセルを箱で表しています。左側の CAR がデータを格納する場所で、CDR が次のコンスセルと連結しています。この例では、3 つのコンスセルが接続されています。それから、最後尾のコンスセルの CDR には終端を表す特別なデータ (NIL など [*1]) を格納します。このようなリストを Lisp / Scheme では (1 2 3) と表記します。
┌─┬─┐ ┌─┬─┐
│・│・┼─→ NIL │・│・┼─→ b
└┼┴─┘ └┼┴─┘
↓ ↓
ａ ａ
(a) ≡ (a . NIL) (a . b)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→NIL
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
(a b c) ≡ (a . (b . (c . NIL)))
図 : ドットリスト (1)
Lisp / Scheme の場合、リストの終端は CDR 部に格納されるデータがセル以外であれば、そこがリストの終端であることがわかります。つまり、NIL でなくてもかまわないのです。リストの終端が NIL 以外のデータである場合、そのリストを上図のように表します。
左右の括弧の中間にドット ( . ) を置き、左側に CAR 部のデータを、右側に CDR 部のデータを書きます。つまり、リスト (a) は (a . NIL) と表すことができます。このようなデータを「ドット対 (dotted pair)」と呼びます。たとえば、CAR 部がシンボル a で CDR 部がシンボル b であれば (a . b) となります。
それでは、リスト (a b c) の終端を d に変えてみましょう。ドット対を使った表記法では、(a . (b . (c . d))) となりますが、これは (a b c . d) と表すことができます。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│・┼─→ｄ
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
(a b c . d) ≡ (a . (b . (c . d)))
図 : ドットリスト (2)
このように、nil 以外のアトムで終端されたリストを「ドットリスト (dotted list)」と呼びます。
Lisp / Schmem のリストは CAR にリストを格納して、リストを入れ子にすることができます。次の図を見てください。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼→│・│・┼→│・│／│ ／ : nil
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ │ │
１ │ │
│ ↓
│ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・│・┼→│・│・┼→│・│／│
│ └┼┴─┘ └┼┴─┘ └┼┴─┘
│ ↓ ↓ ↓
│ ３ １２ １３
↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼→│・│・┼→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
２ １０ １１
図 : リストの階層構造
上図のリストを Lisp で記述すると (1 (2 10 11) (3 12 13)) になります。
それではプログラムを作りましょう。最初にコンスセルを定義します。
リスト : コンスセル
module List
# コンスセル (終端はシンボル :nil)
Cons = Struct.new(:car, :cdr) do
# 文字列
def to_s
xs = self
ys = "("
while Cons === xs
ys += xs.car.to_s
xs = xs.cdr
ys += " " if Cons === xs
end
if xs == :nil
ys + ")"
else
ys + " . " + xs.to_s + ")"
end
end
# Enumerable 用
def each(&fn)
xs = self
while Cons === xs
fn.call(xs.car)
xs = xs.cdr
end
self
end
end
# 関数定義 (省略)
end
今回はコンスセルを構造体 Cons で、リストの終端 (空リスト) をシンボル :nil で表すことにします。メンバ変数は Lisp / Scheme に合わせて car と cdr にしました。あとは、メソッド to_s() と each() をオーバーライドします。to_s() は Lisp / Scheme と同じ表記法でリストを文字列に変換します。each() はコンスセルをたどって car に格納された要素にブロック fn を適用します。これでコンスセル単体ではなく、リストに対して Enumerable のメソッドを適用することができます。
次はリストにアクセスするための基本関数を定義します。
リスト : 基本関数
def pair?(xs) = Cons === xs
def null?(xs) = xs == :nil
def cons(x, xs = :nil) = Cons.new(x, xs)
def rest(xs) = xs.cdr
def first(xs) = xs.car
def second(xs) = xs.cdr.car
def third(xs) = xs.cdr.cdr.car
def fourth(xs) = xs.cdr.cdr.cdr.car
def fifth(xs) = xs.cdr.cdr.cdr.cdr.car
# 参照
def list_ref(xs, n)
n.times { xs = xs.cdr }
xs.car
end
# 更新
def list_set!(xs, n, x)
n.times { xs = xs.cdr }
xs.car = x
end
述語 pair?() は引数がコンスセルならば真を返します。述語 null?() は引数が空リスト (:nil) ならば真を返します。これらの術語は Scheme の述語 pair?, null? と同じです。関数 cons() はコンスセルを生成します。Lisp / Scheme の関数 cons と同じです。first() と rest() は Lisp / Scheme の関数 car と cdr と同じです。second() - fifth() は 2 - 5 番目の要素を返します。list_ref() はリスト xs の n 番目の要素を返します。list_set!() は xs の n 番目の要素を x に書き換えます。
簡単な実行例を示します。
irb> load "list.rb"
=> true
irb> a = List.cons(1, List.cons(2, List.cons(3, List.cons(4, List.cons(5)))))
=>
#<struct List::Cons
...
irb> print a, "\n"
(1 2 3 4 5)
=> nil
irb> List.first(a)
=> 1
irb print List.rest(a), "\n"
(2 3 4 5)
=> nil
irb> List.pair?(a)
=> true
irb> List.null?(a)
=> false
irb> List.pair?(:nil)
=> false
irb> List.null?(:nil)
=> true
irb> List.second(a)
=> 2
irb> List.third(a)
=> 3
irb> List.fourth(a)
=> 4
irb> List.fifth(a)
=> 5
irb> 5.times {|n| print List.list_ref(a, n), "\n"}
1
2
3
4
5
=> 5
irb> 5.times {|n| List.list_set!(a, n, n + 10)}
=> 5
irb> print a, "\n"
(10 11 12 13 14)
=> nil
次はリストを生成する便利な関数を作りましょう。
リスト : リストの生成
def list(*args)
xs = :nil
args.reverse_each do |x|
xs = cons(x, xs)
end
xs
end
def to_list(xs) = list(*xs.to_a)
def make_list(n, x)
xs = :nil
n.times {
xs = cons(x, xs)
}
xs
end
def tabulate(rs, &fn)
xs = :nil
rs.reverse_each do |x|
xs = cons(fn.call(x), xs)
end
xs
end
def iterate(n, a, &gen)
if n == 0
:nil
else
cons(a, iterate(n - 1, gen.call(a), &gen))
end
end
list() は引数を格納したリストを生成します。Lisp / Scheme の関数 list と同じです。to_list() は引数 xs をリストに変換します。xs は配列に変換するメソッド to_a を実装しているオブジェクトであれば何でもかまいません。
make_list() は x を n 個格納したリストを返します。tabulate(xs, &fn) は map(to_list(xs), &fn) と同じです。iterate() は初項を a とし、ブロック gen で生成した項を n 個格納したリストを返します。
簡単な実行例を示します。
irb> print List.list(1,2,3,4,5), "\n"
(1 2 3 4 5)
=> nil
irb> print List.to_list(1..10), "\n"
(1 2 3 4 5 6 7 8 9 10)
=> nil
irb> print List.tabulate(1..10){|x| x * x}, "\n"
(1 4 9 16 25 36 49 64 81 100)
=> nil
irb> print List.make_list(10, 0), "\n"
(0 0 0 0 0 0 0 0 0 0)
=> nil
irb> print List.iterate(10, 0){|x| x + 2}, "\n"
(0 2 4 6 8 10 12 14 16 18)
=> nil
次は基本的なリスト操作関数を作ります。
リスト : リスト操作関数 (1)
# 末尾のコンスセル
def last_pair(xs)
while pair?(xs.cdr)
xs = xs.cdr
end
xs
end
# 末尾の要素
def last(xs)
last_pair(xs).car
end
# 連結
def append(xs, ys)
if pair?(xs)
cons(xs.car, append(xs.cdr, ys))
else
ys
end
end
# 反転
def reverse(xs, ys = :nil)
if pair?(xs)
reverse(xs.cdr, cons(xs.car, ys))
else
ys
end
end
# 長さ
def length(xs)
len = 0
xs.each { len += 1 } if pair?(xs)
len
end
# 先頭から n 個の要素を取り出す
def take(xs, n)
if n != 0 && pair?(xs)
cons(xs.car, take(xs.cdr, n - 1))
else
:nil
end
end
# 先頭から n 個の要素を取り除く
def drop(xs, n)
if n != 0 && pair?(xs)
drop(xs.cdr, n - 1)
else
xs
end
end
last_pair() は末尾のコンスセルを返します。last() は末尾の要素を返します。take() はリストの先頭から n 個の要素を取り出します。drop() は先頭から n 個の要素を取り除きます。これらの関数は Scheme のライブラリ SRFI-1 の関数と同じです。append() は 2 つのリストを連結します。reverse() はリストを反転します。length() はリストの長さ (要素数) を返します。これらの関数は Lisp / Scheme と同じです。
irb> a = List.list(1,2,3,4,5) => #<struct List::Cons ... irb> print List.last_pair(a), "\n" (5) => nil irb> print List.last(a), "\n" 5 => nil irb> b = List.list(6,7,8,9) => #<struct List::Cons ... irb> print List.append(a, b), "\n" (1 2 3 4 5 6 7 8 9) => nil irb> print a, "\n" (1 2 3 4 5) => nil irb> print List.reverse(a), "\n" (5 4 3 2 1) => nil irb> print a, "\n" (1 2 3 4 5) => nil irb> print List.length(a), "\n" 5 => nil irb> print List.take(a, 3), "\n" (1 2 3) => nil irb> print List.drop(a, 3), "\n" (4 5) => nil
リストを連結する関数 append は引数のリストを破壊しません。append の動作を図に示します。
引数 (a b) 引数 (c d)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│／│ ┌→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ │ └┼┴─┘ └┼┴─┘
↓ ↓ │ ↓ ↓
ａ ｂ │ ｃ ｄ
│ │ │
↓ ↓ │
┌┼┬─┐ ┌┼┬─┐ │
┌──│・│・┼─→│・│・┼─┘
│ └─┴─┘ └─┴─┘
│ 新しいセル 新しいセル
↓
append の返り値
(append '(a b) '(c d)) => (a b c d)
図 : append の動作
このように append は第 1 引数のリストをコピーしてから連結します。これに対し、引数のリストをコピーせずに、最後尾のセルの CDR 部を書き換えることで、リストを連結する関数を考えることができます。Common Lisp では nconc、Scheme では append! と呼ばれています。
リスト : リストの破壊的連結
def append!(xs, ys)
if null?(xs)
ys
elsif null?(ys)
xs
else
last_pair(xs).cdr = ys
xs
end
end
関数 append! は引数のリストをつなぎあわせたリストを返します。最後を除く引数の内容が破壊されます。次の図を見てください。
引数 (a b) 引数 (c d)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│／┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↑ ↓ ↓
ａ ｂ │ ｃ ｄ
│
CDR 部を直接書き換える
図 : (append! '(a b) '(c d)) の動作
上図に示すように、append! はリストの最終セルの CDR 部を直接書き換えることで、引数のリストを連結しています。
簡単な実行例を示しましょう。
irb> a = List.list(1,2,3,4) => #<struct List::Cons ... irb> b = List.list(5,6,7,8) => #<struct List::Cons ... irb> print List.append(a, b), "\n" (1 2 3 4 5 6 7 8) => nil irb> print a, "\n" (1 2 3 4) => nil irb> print List.append!(a, b), "\n" (1 2 3 4 5 6 7 8) => nil irb> print a, "\n" (1 2 3 4 5 6 7 8) => nil
関数 reverse はリストの要素を逆順にした新しいリストを生成して返します。ここで、リストを破壊的に修正する関数 reverse! を考えてみましょう。Scheme のライブラリ SRFI-1 には reverse! が、Common Lisp には関数 nreverse が用意されていますが、私たちでも簡単にプログラムすることができます。次の図を見てください。
A B C
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ls─→│ａ│・┼─→│ｂ│・┼─→│ｃ│・┼─→ ()
└─┴─┘ └─┴─┘ └─┴─┘
↑
変数r ─→ () ─┘書き換える
(1) セル A の CDR 部を書き換える
B C
┌─┬─┐ ┌─┬─┐
変数ls─→│ｂ│・┼─→│ｃ│・┼─→ ()
└─┴─┘ └─┴─┘
↑
A──┘書き換える
┌─┬─┐
変数r ─→│ａ│・┼─→ ()
└─┴─┘
(2) セル B の CDR 部を書き換える
C
┌─┬─┐
変数ls─→│ｃ│・┼─→ ()
└─┴─┘
↑
B──┘書き換える
┌─┬─┐ ┌─┬─┐
変数r ─→│ｂ│・┼─→│ａ│・┼─→ ()
└─┴─┘ └─┴─┘
(3) セル C の CDR 部を書き換える
変数ls ─→ ()
C B A
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数r ─→│ｃ│・┼─→│ｂ│・┼─→│ａ│・┼─→ ()
└─┴─┘ └─┴─┘ └─┴─┘
(4) 完成
図 : reverse! の動作
変数 ls に格納されたリストを逆順にします。このとき、変数 r に逆順のリストを保持します。考え方は簡単で、リストの先頭から要素を順番に取り出して、変数 r のリストに追加していくところは reverse と同じです。この操作をセルをつなぎかえることで行っているのが reverse! です。つまり、セルごと要素を移動しているのです。
これをプログラムすると次のようになります。
リスト : リストの破壊的反転
def reverse!(xs, ys = :nil)
if null?(xs)
ys
else
zs = xs.cdr
xs.cdr = ys
reverse!(zs, xs)
end
end
reverse!() は引数 xs のリストを破壊的な操作で要素を逆順にします。変数 ys に逆順のリストを保持します。xs が空リストの場合は ys を返します。そうでなければ、xs の先頭のセルを ys に追加します。
まず、2 番目のセルを変数 zs にセットします。それから、先頭セルの CDR 部を ys に書き換えます。これで、ys の先頭にセルを移動することができます。あとは、reverse!() を再帰呼び出しするとき、第 1 引数に zs を、第 2 引数に xs を渡します。xs の先頭のセルが逆順のリストの先頭になっていることに注意してください。
それでは簡単な例を示しましょう。
irb> print a, "\n" (1 2 3 4 5 6 7 8) => nil irb> print List.reverse(a), "\n" (8 7 6 5 4 3 2 1) => nil irb> print a, "\n" (1 2 3 4 5 6 7 8) => nil irb> b = List.reverse!(a) => #<struct List::Cons ... irb> print b, "\n" (8 7 6 5 4 3 2 1) => nil irb> print a, "\n" (1) => nil
reverse!() の返り値を代入した変数 b の値は逆順のリストになりますが、変数 a の値は逆順のリストになりません。reverse!() は変数 a のリストを破壊的に修正しますが、変数 a の値が逆順のリストになるわけではありません。Scheme (Gauche) の reverse! や Common Lisp (SBCL) の nreverse も同じ動作になります。ご注意くださいませ。
次はマップ関数を作ります。
リスト : マップ関数
def map(xs, &fn)
if pair?(xs)
cons(fn.call(xs.car), map(xs.cdr, &fn))
else
:nil
end
end
def append_map(xs, &fn)
if pair?(xs)
append(fn.call(xs.car), append_map(xs.cdr, &fn))
else
:nil
end
end
def append_map!(xs, &fn)
if pair?(xs)
append!(fn.call(xs.car), append_map!(xs.cdr, &fn))
else
:nil
end
end
関数 map() は普通のマップ関数、append_map() はブロック fn の返り値を append で連結したリストを、append_map!() は append! で連結したリストを返します。append_map() は、一般に flatmap と呼ばれている関数と同じ動作です。関数型言語の Haskell では concatMap といいます。append_map!() は Common Lisp の関数 mapcan と同じです。
簡単な例を示しましょう。
irb> a = List.to_list(1..8)
=>
#<struct List::Cons
...
irb> print List.map(a){|x| x * x}, "\n"
(1 4 9 16 25 36 49 64)
=> nil
irb> print List.map(a){|x| List.list(x,x) }, "\n"
((1 1) (2 2) (3 3) (4 4) (5 5) (6 6) (7 7) (8 8))
=> nil
irb> print List.append_map(a){|x| List.list(x,x) }, "\n"
(1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8)
=> nil
irb> print List.append_map!(a){|x| List.list(x,x) }, "\n"
(1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8)
=> nil
リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」といいます。次の図を見てください。
CDR 部を直接 CELL A に書き換える
└──────┐
CELL A ↓
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
┌───────────────┐
↓ │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数ｚ─→│・│・┼─→│・│・┼─→│・│・│
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
ａ ｂ ｃ
図 : 循環リスト
リスト (a b c) は空リストで終端されています。このリストで、最後尾のセルの CDR 部を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。それでは、実際に循環リストを作ってみましょう。
リスト : 循環リストの生成
def circular_list(*args)
xs = list(*args)
last_pair(xs).cdr = xs
xs
end
関数 circular_list() は list() でリスト xs を生成し、末尾セル last_pair(xs) の CDR 部を xs に書き換えます。これで循環リストを生成することができます。それでは実際に試してみましょう。
irb> a = List.circular_list(1,2,3,4,5)
=>
#<struct List::Cons
...
irb> 10.times {|n| print List.list_ref(a, n), "\n"}
1
2
3
4
5
1
2
3
4
5
=> 10
それから、循環リストを print などで表示しようとすると、メソッド to_a() が無限ループになるため、人が手動で中断しない限り止まらなくなります。ご注意くださいませ。
循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。「うさぎ」と「かめ」はリストをたどる変数として定義します。うさぎは cdr を 2 回適用して進みますが、かめは cdr を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。プログラムは次のようになります。
リスト : 循環リストのチェック
def circular_list?(xs)
return false if !pair?(xs) || null?(xs.cdr)
fast = xs.cdr.cdr
slow = xs.cdr
loop {
return false if null?(fast) || null?(fast.cdr)
return true if fast.equal? slow
fast = fast.cdr.cdr
slow = slow.cdr
}
end
変数 fast が「うさぎ」で slow が「かめ」を表します。fast は fast.cdr.cdr で、slow は slow.cdr で進みます。fast または fast.cdr が終端に到達すれば循環リストではありません。false を返します。うさぎがかめに追いつくと fast と slow の値は同じセルになるので、fast.equal? slow の評価結果は真になります。この場合は true を返します。あとは、リストをたどってチェックを続行します。
それでは実際に試してみましょう。
irb> List.circular_list?(List.circular_list(1)) => true irb> List.circular_list?(List.circular_list(1,2)) => true irb> List.circular_list?(List.circular_list(1,2,3)) => true irb> List.circular_list?(List.circular_list(1,2,3,4)) => true irb> List.circular_list?(List.list(1)) => false irb> List.circular_list?(List.list(1,2)) => false irb> List.circular_list?(List.list(1,2,3)) => false irb> List.circular_list?(List.list(1,2,3,4)) => false
正常に動作していますね。
マージ (併合) とは、複数のソート済み列をひとつのソート済みの列にまとめる操作です。次の図を見てください。
┌─ (1 3 5) ; リスト a
() ←┤
└─ (2 4 6) ; リスト b
小さい方をセットする
┌─ (3 5) ; リスト a
(1) ←┘
(2 4 6) ; リスト b
1 をセットする
(3 5) ; リスト a
(1 2) ←┐
└─ (4 6) ; リスト b
2 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
2 つのリスト a と b があります。これらのリストは昇順でソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
それでは実際にプログラムを作ってみましょう。次のリストを見てください。
リスト : リストのマージ
def merge(xs, ys)
if null?(xs)
ys
elsif null?(ys)
xs
elsif xs.car <= ys.car
cons(xs.car, merge(xs.cdr, ys))
else
cons(ys.car, merge(xs, ys.cdr))
end
end
関数 merge() の引数 xs と ys がマージするリストです。最初に、述語 null?() でリスト xs と ys が空リストかチェックします。そうであれば、もう一方のリストを返します。これが再帰呼び出しの停止条件になります。
xs と ys が空リストでなければ、先頭要素を演算子 <= で比較します。返り値が真であれば xs の先頭要素を、そうでなければ ys の先頭要素を merge() が返すリストに追加します。merge() を再帰呼び出しするときは、追加する先頭要素を引数のリストから取り除くことに注意してください。これでリストをマージすることができます。
簡単な実行例を示しましょう。
irb> a = List.list(1,3,5,7) => #<struct List::Cons ... irb> b = List.list(2,4,6,8) => #<struct List::Cons ... irb> print List.merge(a, b), "\n" (1 2 3 4 5 6 7 8) => nil irb> print a, "\n" (1 3 5 7) => nil irb> print b, "\n" (2 4 6 8) => nil
ところで、リストのマージはリストを直接書き換えながら行うことができます。次のリストを見てください。
リスト : 破壊的なマージ
def merge!(xs, ys)
head = cons(nil)
cp = head
while pair?(xs) && pair?(ys)
if xs.car <= ys.car
cp.cdr = xs
cp = xs
xs = xs.cdr
else
cp.cdr = ys
cp = ys
ys = ys.cdr
end
end
cp.cdr = pair?(xs) ? xs : ys
head.cdr
end
関数 merge!() はソート済みのリスト xs と ys を一つのリストにまとめます。この関数はリストを破壊的に修正してマージします。最初にリストのヘッダ head を用意します。head の後ろにリストをつないでいきます。変数 cp は最後尾のセルを示します。
マージ処理はとても簡単です。while ループで xs と ys がコンスセルであれば、2 つのデータ x.car, y.car を比較し、小さいほうのセルを cp の後ろ (cp.cdr) につなげます。そして、cp の値をつなげたセルに更新して、次のセルへ進めます。while ループが終了して、xs にリストが残っていれば、それを cp の後ろにつなげます。xs が空リストであれば ys に残っているリストをつなげます。最後に head.cdr を返します。
簡単な実行例を示しましょう。
irb> print a, "\n" (1 3 5 7) => nil irb> print b, "\n" (2 4 6 8) => nil irb> c = List.merge!(a, b) => #<struct List::Cons ... irb> print c, "\n" (1 2 3 4 5 6 7 8) => nil irb> print a, "\n" (1 2 3 4 5 6 7 8) => nil irb> print b, "\n" (2 3 4 5 6 7 8) => nil
マージソートは、このマージを使ってデータをソートします。次の図を見てください。
9 5 3 7 6 4 2 8 最初の状態
|5 9|3 7|4 6|2 8| 長さ２の列に併合
|3 5 7 9|2 4 6 8| 長さ４の列に併合
2 3 4 5 6 7 8 9 ソート終了
図 : マージソート
マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。
それではプログラムを作りましょう。マージソートの場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単にプログラムを作ることができます。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。
再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。
リスト : マージソート
def msort(xs, n)
if n == 1
cons(xs.car)
elsif n == 2
a = first(xs)
b = second(xs)
a <= b ? list(a, b) : list(b, a)
else
m = n / 2
merge(msort(xs, m), msort(drop(xs, m), n - m))
end
end
def merge_sort(xs) = msort(xs, length(xs))
関数 merge_sort() の引数 xs がソートするリストです。実際の処理は関数 msort() で行います。引数 n はリストの長さです。msort() はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。
引数 xs
｜
｜←── 長さn ──→｜
（１ ２ ３ ４ ５ ６ ７ ８）
｜←n/2→｜ ｜←n/2→｜
｜ ｜
引数 xs 引数 ys 再帰呼び出し
図 : リストの分割
msort() はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は xs と n / 2 で表し、後半部分を ys と n / 2 で表します。ys は cdr を n / 2 回繰り返せば求めることができます。これは drop() を使えば簡単ですね。あとは再帰呼び出しでリストを分割していき、リストの長さが 1 または 2 になったならば新しいリストを返します。そして、msort() の返り値を merge() でマージすればいいわけです。
それでは実行してみましょう。
irb> a = List.list(5,6,4,7,3,8,2,9,1,0) => #<struct List::Cons ... irb> print a, "\n" (5 6 4 7 3 8 2 9 1 0) => nil irb> print List.merge_sort(a), "\n" (0 1 2 3 4 5 6 7 8 9) => nil irb> print a, "\n" (5 6 4 7 3 8 2 9 1 0) => nil irb> print List.merge_sort(List.list(9,8,7,6,5,4,3,2,1,0)), "\n" (0 1 2 3 4 5 6 7 8 9) => nil irb> print List.merge_sort(List.list(0,1,2,3,4,5,6,7,8,9)), "\n" (0 1 2 3 4 5 6 7 8 9) => nil
次は破壊的なマージ merge!() を使ってソートを行う merge_sort!() を作りましょう。
リスト : 破壊的なマージソート
def msort!(xs, n)
if n == 1
xs.cdr = :nil
xs
else
m = n / 2
ys = drop(xs, m)
merge!(msort!(xs, m), msort!(ys, n - m))
end
end
def merge_sort!(xs) = msort!(xs, length(xs))
実際の処理は関数 msort!() で行います。引数 xs がソートする連結リスト、n が連結リストの長さを表します。n が 1 になったら xs.cdr を :nil に書き換えます。これが再帰の停止条件で、要素数が一つの連結リスト、つまりソート済みの連結リストを返すことになります。n が 1 よりも大きい場合は、連結リストを二分割して msort!() を再帰呼び出しし、その結果を merge!() でマージすればいいわけです。
簡単な実行例を示します。
irb> print a, "\n" (5 6 4 7 3 8 2 9 1 0) => nil irb> print List.merge_sort!(a), "\n" (0 1 2 3 4 5 6 7 8 9) => nil irb> print a, "\n" (5 6 7 8 9) => nil irb> print List.merge_sort!(List.list(9,8,7,6,5,4,3,2,1,0)), "\n" (0 1 2 3 4 5 6 7 8 9) => nil irb> print List.merge_sort!(List.list(0,1,2,3,4,5,6,7,8,9)), "\n" (0 1 2 3 4 5 6 7 8 9) => nil
このほかにも、モジュール list には基本的なリスト操作関数や高階関数が定義されています。興味のある方はプログラムリストをお読みくださいませ。
# coding: utf-8
#
# list.rb : mutable な連結リスト (名前は Scheme に寄せる)
#
# Copyright (C) 2023 Makoto Hiroi
#
module List
# コンスセル (終端はシンボル :nil)
Cons = Struct.new(:car, :cdr) do
def to_s
xs = self
ys = "("
while Cons === xs
ys += xs.car.to_s
xs = xs.cdr
ys += " " if Cons === xs
end
if xs == :nil
ys + ")"
else
ys + " . " + xs.to_s + ")"
end
end
# Enumerable 用
def each(&fn)
xs = self
while Cons === xs
fn.call(xs.car)
xs = xs.cdr
end
self
end
end
# 基本関数
def pair?(xs) = Cons === xs
def null?(xs) = xs == :nil
def cons(x, xs = :nil) = Cons.new(x, xs)
def rest(xs) = xs.cdr
def first(xs) = xs.car
def second(xs) = xs.cdr.car
def third(xs) = xs.cdr.cdr.car
def fourth(xs) = xs.cdr.cdr.cdr.car
def fifth(xs) = xs.cdr.cdr.cdr.cdr.car
# 参照
def list_ref(xs, n)
n.times { xs = xs.cdr }
xs.car
end
# 更新
def list_set!(xs, n, x)
n.times { xs = xs.cdr }
xs.car = x
end
# リストの生成
def list(*args)
xs = :nil
args.reverse_each do |x|
xs = cons(x, xs)
end
xs
end
def to_list(xs) = list(*xs.to_a)
def tabulate(rs, &fn)
xs = :nil
rs.reverse_each do |x|
xs = cons(fn.call(x), xs)
end
xs
end
def make_list(n, x)
xs = :nil
n.times {
xs = cons(x, xs)
}
xs
end
def iterate(n, a, &gen)
if n == 0
:nil
else
cons(a, iterate(n - 1, gen.call(a), &gen))
end
end
# 循環リスト
def circular_list(*args)
xs = list(*args)
last_pair(xs).cdr = xs
xs
end
def circular_list?(xs)
return false if !pair?(xs) || null?(xs.cdr)
fast = xs.cdr.cdr
slow = xs.cdr
loop {
return false if null?(fast) || null?(fast.cdr)
return true if fast.equal? slow
fast = fast.cdr.cdr
slow = slow.cdr
}
end
# 末尾のコンスセル
def last_pair(xs)
while pair?(xs.cdr)
xs = xs.cdr
end
xs
end
# 末尾の要素
def last(xs)
last_pair(xs).car
end
# 連結
def append(xs, ys)
if pair?(xs)
cons(xs.car, append(xs.cdr, ys))
else
ys
end
end
def append!(xs, ys)
if null?(xs)
ys
elsif null?(ys)
xs
else
last_pair(xs).cdr = ys
xs
end
end
# 反転
def reverse(xs, ys = :nil)
if pair?(xs)
reverse(xs.cdr, cons(xs.car, ys))
else
ys
end
end
def reverse!(xs, ys = :nil)
if null?(xs)
ys
else
zs = xs.cdr
xs.cdr = ys
reverse!(zs, xs)
end
end
# 長さ
def length(xs)
len = 0
xs.each { len += 1 } if pair?(xs)
len
end
# 先頭から n 個の要素を取り出す
def take(xs, n)
if n != 0 && pair?(xs)
cons(xs.car, take(xs.cdr, n - 1))
else
:nil
end
end
# 先頭から pred が真を返す要素を取り出す
def take_while(xs, &pred)
if pair?(xs) && pred.call(xs.car)
cons(xs.car, take_while(xs.cdr, &pred))
else
:nil
end
end
# 先頭から n 個の要素を取り除く
def drop(xs, n)
if n != 0 && pair?(xs)
drop(xs.cdr, n - 1)
else
xs
end
end
# 先頭から pred が真を返す要素を取り除く
def drop_while(xs, &pred)
if pair?(xs) && pred.call(xs.car)
drop_while(xs.cdr, &pred)
else
xs
end
end
# 二つのリストを一つにまとめる
def zip(xs, ys)
if pair?(xs) && pair?(ys)
cons(list(xs.car, ys.car), zip(xs.cdr, ys.cdr))
else
:nil
end
end
def unzip(xs)
if null?(xs)
[:nil, :nil]
else
ys, zs = unzip(xs.cdr)
return cons(first(xs.car), ys), cons(second(xs.car), zs)
end
end
# 高階関数
def map(xs, &fn)
if pair?(xs)
cons(fn.call(xs.car), map(xs.cdr, &fn))
else
:nil
end
end
def append_map(xs, &fn)
if pair?(xs)
append(fn.call(xs.car), append_map(xs.cdr, &fn))
else
:nil
end
end
def append_map!(xs, &fn)
if pair?(xs)
append!(fn.call(xs.car), append_map!(xs.cdr, &fn))
else
:nil
end
end
def for_each(xs, &fn)
xs.each {|x| fn.call(x)}
xs
end
def filter(xs, &pred)
if pair?(xs)
if pred.call(xs.car)
cons(xs.car, filter(xs.cdr, &pred))
else
filter(xs.cdr, &pred)
end
else
:nil
end
end
def remove(xs, &pred)
if pair?(xs)
if !pred.call(xs.car)
cons(xs.car, remove(xs.cdr, &pred))
else
remove(xs.cdr, &pred)
end
else
:nil
end
end
def partition(xs, &pred)
if null?(xs)
[:nil, :nil]
else
ys, zs = partition(xs.cdr, &pred)
if pred.call(xs.car)
return cons(xs.car, ys), zs
else
return ys, cons(xs.car, zs)
end
end
end
# 畳み込み
def fold(xs, a, &fn)
if pair?(xs)
fold(xs.cdr, fn.call(a, xs.car), &fn)
else
a
end
end
def foldr(xs, a, &fn)
if pair?(xs)
fn.call(xs.car, foldr(xs.cdr, a, &fn))
else
a
end
end
# 線形探索 (あとは Enumerable のメソッドで代用)
def member(xs, &pred)
while pair?(xs)
return xs if pred.call(xs.car)
xs = xs.cdr
end
:nil
end
# マージ
def merge(xs, ys)
if null?(xs)
ys
elsif null?(ys)
xs
elsif xs.car <= ys.car
cons(xs.car, merge(xs.cdr, ys))
else
cons(ys.car, merge(xs, ys.cdr))
end
end
# 破壊的
def merge!(xs, ys)
head = cons(nil)
cp = head
while pair?(xs) && pair?(ys)
if xs.car <= ys.car
cp.cdr = xs
cp = xs
xs = xs.cdr
else
cp.cdr = ys
cp = ys
ys = ys.cdr
end
end
cp.cdr = pair?(xs) ? xs : ys
head.cdr
end
# マージソート
def msort(xs, n)
if n == 1
cons(xs.car)
elsif n == 2
a = first(xs)
b = second(xs)
a <= b ? list(a, b) : list(b, a)
else
m = n / 2
merge(msort(xs, m), msort(drop(xs, m), n - m))
end
end
def merge_sort(xs) = msort(xs, length(xs))
def msort!(xs, n)
if n == 1
xs.cdr = :nil
xs
else
m = n / 2
ys = drop(xs, m)
merge!(msort!(xs, m), msort!(ys, n - m))
end
end
def merge_sort!(xs) = msort!(xs, length(xs))
module_function :pair?
module_function :null?
module_function :cons
module_function :rest
module_function :first
module_function :second
module_function :third
module_function :fourth
module_function :fifth
module_function :list_ref
module_function :list_set!
module_function :list
module_function :iota
module_function :tabulate
module_function :make_list
module_function :iterate
module_function :circular_list
module_function :circular_list?
module_function :last_pair
module_function :last
module_function :append
module_function :append!
module_function :reverse
module_function :reverse!
module_function :length
module_function :take
module_function :drop
module_function :take_while
module_function :drop_while
module_function :zip
module_function :unzip
module_function :map
module_function :append_map
module_function :append_map!
module_function :for_each
module_function :filter
module_function :remove
module_function :partition
module_function :fold
module_function :foldr
module_function :member
module_function :merge
module_function :merge!
module_function :msort
module_function :msort!
module_function :merge_sort
module_function :merge_sort!
end
リスト : 簡単なテスト
require "./list"
a = List.cons(1)
printf "a: cons(1) = %s\n", a
b = List.cons(2, a)
printf "b: cons(2, a) = %s\n", b
c = List.cons(3, b)
printf "c: cons(3, b) = %s\n", c
d = List.cons(1, 2)
printf "d: cons(1, 2) = %s\n", d
printf "first(d) = %s\n", List.first(d)
printf "rest(d) = %s\n", List.rest(d)
printf "pair?(a) = %s\n", List.pair?(a)
printf "pair?(nil) = %s\n", List.pair?(:nil)
printf "pair?(1) = %s\n", List.pair?(1)
printf "null?(a) = %s\n", List.null?(a)
printf "null?(nil) = %s\n", List.null?(:nil)
printf "null?(1) = %s\n", List.null?(1)
e = List.list(4,5,6,7,8,9)
printf "e: list(4,5,6,7,8,9) = %s\n", e
printf "second(e) = %s\n", List.second(e)
printf "third(e) = %s\n", List.third(e)
printf "fourth(e) = %s\n", List.fourth(e)
printf "fifth(e) = %s\n", List.fifth(e)
printf "to_list(1..8) = %s\n", List.to_list(1..8)
printf "tabulate(1..8) {|x| x * x} = %s\n", List.tabulate(1..8) {|x| x * x}
printf "make_list(10, 0) = %s\n", List.make_list(10, 0)
printf "iterate(10, 1) {|x| x + 2} = %s\n", List.iterate(10, 1) {|x| x + 2}
printf "last(a) = %s\n", List.last(a)
printf "last(b) = %s\n", List.last(b)
printf "last(c) = %s\n", List.last(c)
printf "append(c, e) = %s\n", List.append(c, e)
printf "c = %s\n", c
printf "append!(c, e) = %s\n", List.append!(c, e)
printf "c = %s\n", c
printf "reverse(c) = %s\n", List.reverse(c)
printf "c = %s\n", c
printf "reverse!(c) = %s\n", List.reverse!(c)
printf "c = %s\n", c
printf "e = %s\n", e
printf "length(e) = %d\n", List.length(e)
List.length(e).times {|x|
printf "list_ref(e, %d) = %d\n", x, List.list_ref(e, x)
}
List.length(e).times {|x|
List.list_set!(e, x, x)
}
c = List.to_list(1..6)
printf "c = %s\n", c
printf "take(c, 0) = %s\n", List.take(c, 0)
printf "take(c, 3) = %s\n", List.take(c, 3)
printf "take(c, 6) = %s\n", List.take(c, 6)
printf "drop(c, 0) = %s\n", List.drop(c, 0)
printf "drop(c, 3) = %s\n", List.drop(c, 3)
printf "drop(c, 6) = %s\n", List.drop(c, 6)
printf "take_while(c){|x| x < 3} = %s\n", List.take_while(c){|x| x < 3}
printf "drop_while(c){|x| x < 3} = %s\n", List.drop_while(c){|x| x < 3}
f = List.zip(List.list(1,2,3), List.list(4,5,6))
g, h = List.unzip(f)
printf "f: zip((1 2 3), (4 5 6)) = %s\n", f
printf "unzip(f) = [%s, %s]\n", g, h
printf "map(c){|x| x * x} = %s\n", List.map(c){|x| x * x}
printf "append_map(c){|x| List.list(x, x)} = %s\n", List.append_map(c){|x| List.list(x, x)}
printf "append_map!(c){|x| List.list(x, x)} = %s\n", List.append_map!(c){|x| List.list(x, x)}
List.for_each(c){|x| print x, "\n"}
printf "filter(c){|x| x mod 2 == 0} = %s\n", List.filter(c){|x| x % 2 == 0}
printf "remove(c){|x| x mod 2 == 0} = %s\n", List.remove(c){|x| x % 2 == 0}
g, h = List.partition(c){|x| x % 2 == 0}
printf "partition(c){|x| x mod 2 == 0} = [%s, %s]\n", g, h
printf "fold(c, :nil) {|a, x| cons(x, a)} = %s\n", List.fold(c, :nil) {|a, x| List.cons(x, a)}
printf "foldr(c, :nil) {|x, a| cons(x, a)} = %s\n", List.foldr(c, :nil) {|x, a| List.cons(x, a)}
printf "member(c){|x| x == 1} = %s\n", List.member(c){|x| x == 1}
printf "member(c){|x| x == 6} = %s\n", List.member(c){|x| x == 6}
printf "member(c){|x| x == 9} = %s\n", List.member(c){|x| x == 9}
g = List.circular_list(1,2,3,4)
h = List.list(1,2,3,4)
8.times {|n| print List.list_ref(g, n), "\n"}
printf "circular_list?(g) = %s\n", List.circular_list?(g)
printf "circular_list?(h) = %s\n", List.circular_list?(h)
a = List.list(1,3,5,7)
printf "a = %s\n", a
b = List.list(2,4,6,8)
printf "b = %s\n", b
printf "merge(a, b) = %s\n", List.merge(a, b)
printf "a = %s\n", a
printf "b = %s\n", b
printf "merge!(a, b) = %s\n", List.merge!(a, b)
printf "a = %s\n", a
printf "b = %s\n", b
a = List.list(5,6,4,7,3,8,2,9,1,0)
printf "a = %s\n", a
printf "merge_sort(a) = %s\n", List.merge_sort(a)
printf "a = %s\n", a
printf "merge_sort!(a) = %s\n", List.merge_sort!(a)
printf "a = %s\n", a
$ ruby testlist.rb
a: cons(1) = (1)
b: cons(2, a) = (2 1)
c: cons(3, b) = (3 2 1)
d: cons(1, 2) = (1 . 2)
first(d) = 1
rest(d) = 2
pair?(a) = true
pair?(nil) = false
pair?(1) = false
null?(a) = false
null?(nil) = true
null?(1) = false
e: list(4,5,6,7,8,9) = (4 5 6 7 8 9)
second(e) = 5
third(e) = 6
fourth(e) = 7
fifth(e) = 8
to_list(1..8) = (1 2 3 4 5 6 7 8)
tabulate(1..8) {|x| x * x} = (1 4 9 16 25 36 49 64)
make_list(10, 0) = (0 0 0 0 0 0 0 0 0 0)
iterate(10, 1) {|x| x + 2} = (1 3 5 7 9 11 13 15 17 19)
last(a) = 1
last(b) = 1
last(c) = 1
append(c, e) = (3 2 1 4 5 6 7 8 9)
c = (3 2 1)
append!(c, e) = (3 2 1 4 5 6 7 8 9)
c = (3 2 1 4 5 6 7 8 9)
reverse(c) = (9 8 7 6 5 4 1 2 3)
c = (3 2 1 4 5 6 7 8 9)
reverse!(c) = (9 8 7 6 5 4 1 2 3)
c = (3)
e = (4 1 2 3)
length(e) = 4
list_ref(e, 0) = 4
list_ref(e, 1) = 1
list_ref(e, 2) = 2
list_ref(e, 3) = 3
c = (1 2 3 4 5 6)
take(c, 0) = nil
take(c, 3) = (1 2 3)
take(c, 6) = (1 2 3 4 5 6)
drop(c, 0) = (1 2 3 4 5 6)
drop(c, 3) = (4 5 6)
drop(c, 6) = nil
take_while(c){|x| x < 3} = (1 2)
drop_while(c){|x| x < 3} = (3 4 5 6)
f: zip((1 2 3), (4 5 6)) = ((1 4) (2 5) (3 6))
unzip(f) = [(1 2 3), (4 5 6)]
map(c){|x| x * x} = (1 4 9 16 25 36)
append_map(c){|x| List.list(x, x)} = (1 1 2 2 3 3 4 4 5 5 6 6)
append_map!(c){|x| List.list(x, x)} = (1 1 2 2 3 3 4 4 5 5 6 6)
1
2
3
4
5
6
filter(c){|x| x mod 2 == 0} = (2 4 6)
remove(c){|x| x mod 2 == 0} = (1 3 5)
partition(c){|x| x mod 2 == 0} = [(2 4 6), (1 3 5)]
fold(c, :nil) {|a, x| cons(x, a)} = (6 5 4 3 2 1)
foldr(c, :nil) {|x, a| cons(x, a)} = (1 2 3 4 5 6)
member(c){|x| x == 1} = (1 2 3 4 5 6)
member(c){|x| x == 6} = (6)
member(c){|x| x == 9} = nil
1
2
3
4
1
2
3
4
circular_list?(g) = true
circular_list?(h) = false
a = (1 3 5 7)
b = (2 4 6 8)
merge(a, b) = (1 2 3 4 5 6 7 8)
a = (1 3 5 7)
b = (2 4 6 8)
merge!(a, b) = (1 2 3 4 5 6 7 8)
a = (1 2 3 4 5 6 7 8)
b = (2 3 4 5 6 7 8)
a = (5 6 4 7 3 8 2 9 1 0)
merge_sort(a) = (0 1 2 3 4 5 6 7 8 9)
a = (5 6 4 7 3 8 2 9 1 0)
merge_sort!(a) = (0 1 2 3 4 5 6 7 8 9)
a = (5 6 7 8 9)