今回は mutable な連結リスト (モジュール Mulist) を使って、リスト操作の簡単なサンプルプログラムを作ってみましょう。
連結リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」 といいます。次の図を見てください。
セルの cdr 部を直接 A に書き換える └─────┐ セル A ↓ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ 変数─→│・│・┼─→│・│・┼─→│・│/│ └┼┴─┘ └┼┴─┘ └┼┴─┘ ↓ ↓ ↓ 1 2 3 ┌───────────────┐ ↓ │ ┌─┬─┐ ┌─┬─┐ ┌─┬┼┐ 変数─→│・│・┼─→│・│・┼─→│・│・│ └┼┴─┘ └┼┴─┘ └┼┴─┘ ↓ ↓ ↓ 1 2 3 図 : 循環リスト
上図の連結リスト (1 2 3) は Nil で終端されています。この連結リストで、最後尾のセルの cdr 部を先頭のセル A に書き換えると、循環リストを作ることができます。循環リストは環状に並んだデータを表すのに便利なデータ構造です。Mulist の関数 circularlist() は引数を格納した循環リストを返します。これは list(), lastpair(), setcdr!() を使って実現することもできます。
簡単な例を示しましょう。
julia> a = circularlist(1, 2, 3); nil () julia> foreach(x -> print("$x "), take(a, 20)) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 julia> function clist(args...) xs = list(args...) setcdr!(lastpair(xs), xs) xs end clist (generic function with 1 method) julia> b = clist(1, 2, 3); nil () julia> foreach(x -> print("$x "), take(b, 20)) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
循環リストを表示すると無限ループになるので注意してください。
循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。うさぎとかめはリストをたどる変数として定義します。うさぎは cdr() を 2 回適用して進みますが、かめは cdr() を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。Mulist の関数 iscircle() のプログラムを示します。
リスト : 循環リストのチェック function iscircle(xs::List) fast = xs slow = xs while true fast = cdr(fast) if atom(fast) return false end fast = cdr(fast) slow = cdr(slow) if atom(fast) return false elseif fast === slow return true end end end
変数 fast が「うさぎ」で slow が「かめ」を表します。最初に fast を cdr() で進めて atom(fast) でチェックします。結果が true ならば終端に到達しました。return で false を返します。次は fast と slow を cdr() で進めます。fast が終端に到達すれば false を返します。うさぎがかめに追いつくと fast と slow の値は同じセルになるので、fast === slow の評価結果は真になります。この場合は true を返します。あとは、リストをたどってチェックを続行します。
それでは実際に試してみましょう。
julia> a = circularlist(1, 2, 3); nil () julia> iscircle(a) true julia> iscircle(list(1, 2, 3)) false julia> iscircle(cons(1, 2)) false julia> iscircle(nil) false
正常に動作していますね。
FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。FizzBuzz 問題は拙作のページ「簡単なプログラム: FizzBuzz」で取り上げました。答えをリストに格納して返すことにすると、プログラムは次のようになるでしょう。
リスト : FizzBuzz 問題 fizzbuzz() = map(iota(1 : 100)) do n if n % 15 == 0 "FizzBuzz" elseif n % 3 == 0 "Fizz" elseif n % 5 == 0 "Buzz" else string(n) end end
julia> fizzbuzz() (1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz)
ここで「剰余演算子を使わない」という制約をつけて、FizzBuzz 問題を解くことを考えてみてください。いろいろな方法があると思いますが、今回は循環リストを使ってみましょう。プログラムは次のようになります。
リスト : FizzBuzz 問題 (循環リストバージョン) function fizzbuzz1() xs = circularlist(0,0,1) ys = circularlist(0,0,0,0,2) map(iota(1 : 100), xs, ys) do n, x, y m = x + y if m == 1 "Fizz" elseif m == 2 "Buzz" elseif m == 3 "FizzBuzz" else string(n) end end end
実行結果は fizzbuzz() と同じです。xs と ys が循環リストです。n が 3 の倍数のとき xs の要素 x は 1 になり、n が 5 の倍数のとき ys の要素 y は 2 になります。それ以外の要素は 0 なので、x + y (= m) が 0 であれば n を文字列に、1 であれば "Fizz" に、2 であれば "Buzz" に、3 であれば "FizzBuzz" に変換します。map() は短いリストに合わせるので、循環リストが含まれていても正常に動作します。
次は「キュー (queue)」という基本的なデータ構造を作ってみましょう。たとえばチケットを買う場合、カウンタの前に並んで順番を待たなくてはいけません。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。これを表したのが下図です。
out in ────────────── <= A B C D E . . . Z <= ────────────── 図 : キューの動作
このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「待ち行列」とか「先入れ先出し (FIFO : first-in, first-out)」と呼ばれます。
キューは連結リストを使って簡単に実装することができますが、大きな欠点もあります。連結リストをキューとして使う場合、データを追加するときに最後尾までセルをたどっていく操作が必要になるため、要素数が多くなるとデータの追加に時間がかかってしまうのです。
そこで、先頭のセルを参照する変数のほかに、最後尾のセルを参照する変数を用意します。こうすると、先頭からセルをたどらなくても、最後尾にデータを追加することができます。次の図を見てください。
rear ─→ nil front ─→ nil (1) キューが空の状態 rear ─────────────────────┐ ↓ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ front ─→│・│・┼→│・│・┼→│・│・┼→│・│・┼→ nil └┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘ ↓ ↓ ↓ ↓ data1 data2 data3 data4 (2) キューにデータがある場合 図 : 連結リストによるキューの構造
先頭のセルを参照する変数 front のほかに、最後尾のセルを参照する変数 rear を用意します。キューにデータがない場合は、(1) のように front と rear は nil になっています。データがある場合は、(2) のように front は先頭のセルを参照し、rear は最後尾のセルを参照しています。これで、データの追加を効率的に行うことができます。
それでは、プログラムを作りましょう。最初に作成する関数を表に示します。
関数 | 機能 |
---|---|
Que() | 空のキューを生成する |
isempty(q) | キューが空ならば true を返す |
enqueue(q, x) | キューにデータを追加する |
dequeue(q) | キューからデータを取り出す |
peek(q) | キューの先頭にあるデータを求める |
作成するのは基本的な操作関数だけです。プログラムは次のようになります。
リスト : キュー (連結リスト版) # データ型 mutable struct Que front rear Que() = new(nil, nil) end # キューは空か? isempty(q::Que) = null(q.front) # 追加 function enqueue(q::Que, x) xs = cons(x, nil) if isempty(q) q.front = q.rear = xs else setcdr!(q.rear, xs) q.rear = xs end end # 取得 function dequeue(q::Que) if isempty(q) error("Que.dequeue: empty queue") end x = car(q.front) q.front = cdr(q.front) if null(q.front) q.rear = nil end x end # 参照 function peek(q::Que) if isempty(q) error("Que.peek: empty queue") end car(q.front) end # 表示 Base.show(io::IO, q::Que) = print(io, "Que", q.front)
コンストラクタ Que() は front と rear を nil に初期化します。関数 enqueue() はキュー q にデータ x を追加します。最初に、新しいセルを cons(x, nil) で生成して変数 xs にセットします。キューが空であれば q.fornt と q.rear に xs をセットします。キューが空でない場合、setcdr!() で q.rear の cdr 部に xs をセットしてから q.rear を xs に書き換えます。
関数 dequeue() はキュー q の先頭データを取り出します。キューが空の場合はエラーを送出します。そうでなければ、先頭要素 car(q.front) を変数 x にセットしてから、 q.front を cdr(q.front) に書き換えます。q.front が nil になったらキューは空になったので、q.rear も nil に書き換えます。最後に取り出した要素 x を返します。
それでは実行してみましょう。
julia> q = Que() Que() julia> for i = 1 : 5 enqueue(q, i) println(q) end Que(1) Que(1 2) Que(1 2 3) Que(1 2 3 4) Que(1 2 3 4 5) julia> while !isempty(q) println(dequeue(q), " ", q) end 1 Que(2 3 4 5) 2 Que(3 4 5) 3 Que(4 5) 4 Que(5) 5 Que()
キューに 1 から 5 まで enqueue() で格納して、dequeue() でデータを取り出すと 1, 2, 3, 4, 5 になります。このように、キューはデータを入れた順番にデータが取り出されます。
循環リストの場合、最後尾のセルを参照する変数 rear を用意するだけでキューを実現することができます。下図を見てください。
循環リストの場合、最後尾のセルの次のセルが先頭になります。(3) を見てください。rear が参照する最後尾のセルの next は nil ではなく、next が参照するセルがキューの先頭になるのです。データが一つしかない場合、(2) のように rear が参照するセルの next は自分自身になります。つまり、このセルが先頭であり最後尾でもあるわけです。キューにデータがない場合、rear の値は (1) のように nil になります。
rear ─→ 終端 rear ───┐ ↓ (1) キューが空の状態 ┌─┬─┐ ┌─→│・│・┼─┐ │ └┼┴─┘ │ │ ↓ │ │ data1 │ │ │ └────────┘ (2) キューにデータが一つある場合 rear ─────────────────────┐ ↓ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─→│・│・┼→│・│・┼→│・│・┼→│・│・┼─┐ │ └┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘ │ │ ↓ ↓ ↓ ↓ │ │ data1 data2 data3 data4 │ │ │ └──────────────────────────┘ (3) キューに複数のデータがある場合 図 : 循環リストによるキューの構造
それでは、プログラムを作りましょう。最初に作成する関数を表に示します。
関数 | 機能 |
---|---|
Cque() | 空のキューを生成する |
isempty(q) | キューが空ならば True を返す |
enqueue(q, x) | キューにデータを追加する |
dequeue(q) | キューからデータを取り出す |
peek(q) | キューの先頭にあるデータを求める |
rotate(q, n = 1) | キューを回転する |
データ型は Cque としました。rotate() はキューを回転する操作で、先頭のデータを最後尾へ移動します。これを n 回繰り返します。この操作は dequeue() でデータを取り出し、それを enqueue() で追加することと同じですが、循環リストの場合は rear の値を次のセルに書き換えるだけで実現できます。
プログラムは次のようになります。
リスト : キュー (循環リスト版) # データ型 mutable struct Cque rear Cque() = new(nil) end # キューは空か isempty(q::Cque) = null(q.rear) # 表示 function Base.show(io::IO, q::Cque) print(io, "Cque(") if !isempty(q) xs = cdr(q.rear) while true print(io, car(xs)) if xs === q.rear break else print(io, " ") end xs = cdr(xs) end end print(io, ")") end
コンストラクタ Cque() は rear を nil に初期化するだけです。isempty() は rear が nil ならば true を返します。Cque の rear は循環リストになるので、そのまま表示すると無限ループになってしまいます。そこで、関数 show() を多重定義することにします。先頭のセル cdr(q.rear) から末尾のセル q.rear まで、順番に要素を print() で出力するだけです。
リスト : Cque の操作関数 # 追加 function enqueue(q::Cque, x) if isempty(q) q.rear = circularlist(x) else xs = cons(x, cdr(q.rear)) setcdr!(q.rear, xs) q.rear = xs end nil end # 取得 function dequeue(q::Cque) if isempty(q) error("Cque.dequeue: empty queue") end xs = cdr(q.rear) if xs === q.rear q.rear = nil else setcdr!(q.rear, cdr(xs)) end car(xs) end # 参照 function peek(q::Cque) if isempty(q) error("Cque.peek: empty queue") end second(que.rear) end # キューを回転する function rotate(q::Cque, n = 1) if null(q.rear) error("Cque.rotate: empty queue") elseif n < 1 error("Cque.rotate: invalid argument") end q.rear = drop(q.rear, n) end
enqueue() は、キューが空であれば curcularlist() で巡回リストを生成して q.rear にセットします。そうでなければ、キューの先頭 cdr(q.rear) とキューの末尾 q.rear の間に新しいセル xs を挿入します。cons() で xs を生成するとき、第 2 引数に先頭セルを指定します。そして、q.rear の cdr 部を xs に書き換えます。これで xs を循環リストに挿入することができました。あとは、q.rear の値を xs に書き換えれば、xs が最後尾のセルになります。
dequeue() は、最初にキューが空がチェックします。空でなければ、先頭のセル cdr(q.rear) を変数 xs にセットし、このセルを循環リストから削除します。データが一つしかない場合、xs と q.rear は同じセルになります。この場合は q.rear を nil に書き換えます。そうでなければ、setcdr!() で q.rear の cdr 部を cdr(xs) に書き換えます。これで xs を循環リストから外すことができます。最後に car(xs) の値を返します。
rotate() は、キューにデータがない場合や引数 n が 1 未満であればエラーを送出します。あとは、drop() で先頭の要素を n 個取り除くだけです。循環リストには終端がないので、n の値がキューの要素数より大きくても、ぐるぐる回るだけで正常に動作します。
それでは実際に実行してみましょう。
julia> q = Cque() Cque() julia> for i = 1 : 5 enqueue(q, i) println(q) end Cque(1) Cque(1 2) Cque(1 2 3) Cque(1 2 3 4) Cque(1 2 3 4 5) julia> for _ = 1 : 5 rotate(q, 1) println(q) end Cque(2 3 4 5 1) Cque(3 4 5 1 2) Cque(4 5 1 2 3) Cque(5 1 2 3 4) Cque(1 2 3 4 5) julia> while !isempty(q) println(dequeue(q), " ", q) end 1 Cque(2 3 4 5) 2 Cque(3 4 5) 3 Cque(4 5) 4 Cque(5) 5 Cque()
正常に動作していますね。
拙作のページ「リストで遊ぼう」の問題 13 では、素数をリストに格納して返す関数 primelist() を作りました。プログラムを再掲します。
リスト : 素数を求める # xs を反転して ys と連結する function reverse_append(xs, ys) for x = xs ys = cons(x, ys) end ys end function primelist(n) ps = list(2) xs = iota(3 : 2 : n) while true x = car(xs) if x * x > n; break; end ps = cons(x, ps) xs = remove(y -> y % x == 0, cdr(xs)) end reverse_append(ps, xs) end
immutable な連結リスト Imlist を使って primelist() を実行すると、引数が 50,000 でスタックオーバーフローします。
julia> length(primelist(10000)) 1229 julia> length(primelist(40000)) 4203 julia> length(primelist(50000)) ERROR: StackOverflowError:
Mulist を使うと少々時間はかかりますが 1,000,000 でも実行することができます。
julia> length(primelist(50000)) 5133 julia> length(primelist(100000)) 9592 julia> @time length(primelist(1000000)) 5.326703 seconds (85.31 M allocations: 1.780 GiB, 11.85% gc time) 78498 実行環境 : Julia ver 1.6.4, Ubuntu 18.04 (WSL), Intel Core i5-6200U 2.30GHz
エラトステネスの篩は配列を使ったほうが高速になります。連結リストだと遅くなるのは仕方がないのですが、リストの破壊的な操作関数を使うともう少しだけ速くすることができます。次のリストを見てください。
リスト : 素数を求める (破壊的操作バージョン) function primelist1(n) xs = iota(3 : 2 : n) ps = cons(2, xs) while true x = car(xs) if x * x > n break end ys = remove!(y -> y % x == 0, cdr(xs)) setcdr!(xs, ys) xs = ys end ps end
素数リストは変数 ps に保持します。変数 xs は素数以外の数を含んだリストです。xs の先頭 x が素数になります。remove!() で x で割り切れる数をリストから取り除き、その結果を変数 ys にセットします。あとは、setcdr!() で xs の cdr 部に ys を連結して、xs を ys に書き換えます。
primelist() では、ps に素数を追加するとき、remove() で素数以外の数を取り除くとき、ps を反転するときに新しいリストを生成しています。primelist1() では、それらの新しいリストは生成しないので、その分だけ primelist() よりも速くなるはずです。実行結果は次のようになりました。
julia> @time length(primelist1(1000000)) 1.475116 seconds (18.04 M allocations: 283.466 MiB, 4.51% gc time, 2.97% compilation time) 78498
3.6 倍高速化することができました。
リスト : データの挿入 function Base.insert!(xs::List, i::Int, x) if i == 1 cons(x, xs) else ps = drop(xs, i - 2) if consp(ps) setcdr!(ps, cons(x, cdr(ps))) xs else error("insert!: out of range") end end end
先頭に挿入するときは cons(x, xs) を返します。この場合、変数の値はかわらないことに注意してください。それ以外の場合は、drop() でひとつ前のセルまでたどり、その後ろに新しいセルを挿入します。そして、先頭のセル xs を返します。この場合、変数の値は変化します。
julia> a = iota(1 : 5) (1 2 3 4 5) julia> insert!(a, 1, 0) (0 1 2 3 4 5) julia> a (1 2 3 4 5) julia> insert!(a, 5, 0) (1 2 3 4 0 5) julia> a (1 2 3 4 0 5) julia> insert!(a, 7, 0) (1 2 3 4 0 5 0) julia> a (1 2 3 4 0 5 0)
リスト : データの削除 function Base.deleteat!(xs::List, i::Int) if i == 1 cdr(xs) else ps = drop(xs, i - 2) if consp(ps) && consp(cdr(ps)) setcdr!(ps, cdr(cdr(ps))) xs else error("deleteat!: out of range") end end end
先頭要素を削除するときは cdr(xs) を返します。この場合、変数の値はかわらないことに注意してください。それ以外の場合は、drop() でひとつ前のセルまでたどり、その後ろのセルを削除します。そして、先頭のセル xs を返します。この場合、変数の値は変化します。
julia> a = iota(1 : 5) (1 2 3 4 5) julia> deleteat!(a, 1) (2 3 4 5) julia> a (1 2 3 4 5) julia> deleteat!(a, 2) (1 3 4 5) julia> a (1 3 4 5) julia> deleteat!(a, 4) (1 3 4) julia> a (1 3 4)
リスト : getindex() と setindex!() Base.getindex(xs::List, i::Int) = nth(xs, i) function Base.setindex!(xs::List, x, i::Int) ps = drop(xs, i - 1) if consp(ps) setcar!(ps, x) else throw(BoundsError(x, i)) end end
要素数を N とすると、連結リストは要素のアクセスに O(N) かかります。配列のアクセスは O(1) なので、角カッコで連結リストにアクセスするときは時間がかかることに注意してください。
julia> a = iota(11 : 20) (11 12 13 14 15 16 17 18 19 20) julia> a[1] 11 julia> a[10] 20 julia> a[1] = 100 100 julia> a (100 12 13 14 15 16 17 18 19 20) julia> a[10] = 200 200 julia> a (100 12 13 14 15 16 17 18 19 200)
リスト : 2 つのリストの要素を交互に並べる function interleave(xs::List, ys::List) if atom(xs) ys elseif atom(ys) xs else cons(car(xs), interleave(ys, cdr(xs))) end end
julia> a = iota(1 : 2 : 9) (1 3 5 7 9) julia> b = iota(2 : 2 : 10) (2 4 6 8 10) julia> interleave(a, b) (1 2 3 4 5 6 7 8 9 10) julia> interleave(b, a) (2 1 4 3 6 5 8 7 10 9)
リスト : interleave() の破壊的操作版 function interleave!(xs::List, ys::List) ps = xs xs1 = ys ys1 = cdr(xs) while consp(xs1) && consp(ys1) setcdr!(ps, xs1) ps = xs1 xs1 = ys1 ys1 = cdr(ps) end if atom(xs1) setcdr!(ps, ys1) else setcdr!(ps, xs1) end xs end
julia> a (1 3 5 7 9) julia> b (2 4 6 8 10) julia> interleave!(a, b) (1 2 3 4 5 6 7 8 9 10) julia> a (1 2 3 4 5 6 7 8 9 10) julia> b (2 3 4 5 6 7 8 9 10)
リスト : リストの要素の間にデータを挿入する function intersperse(xs::List, x) if atom(xs) || atom(cdr(xs)) xs else cons(car(xs), cons(x, intersperse(cdr(xs), x))) end end
julia> a = iota(1 : 10) (1 2 3 4 5 6 7 8 9 10) julia> intersperse(a, 0) (1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10) julia> intersperse(nil, 0) () julia> intersperse(list(1), 0) (1)
リスト : intersperse() の破壊的操作版 function intersperse!(xs::List, x) if atom(xs) return xs end ps = xs while consp(cdr(ps)) setcdr!(ps, cons(x, cdr(ps))) ps = cdr(cdr(ps)) end xs end
julia> a (1 2 3 4 5 6 7 8 9 10) julia> intersperse!(a, 0) (1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10) julia> a (1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10) julia> intersperse!(nil, 0) () julia> intersperse!(list(1), 0) (1)
リスト : map() の結果を平坦化する # append() で連結 flatmap(func::Function, xs::List) = append(map(func, xs)...) # append!() で連結 flatmap!(func::Function, xs::List) = append!(map(func, xs)...)
julia> map(x -> iota(1 : x), list(1, 2, 3, 4, 5)) ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5)) julia> flatmap(x -> iota(1 : x), list(1, 2, 3, 4, 5)) (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5) julia> flatmap!(x -> iota(1 : x), list(1, 2, 3, 4, 5)) (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5)
リスト : 引数のリストに評価結果を格納するマップ関数 function Base.map!(func::Function, rs::List, xs::List...) rs1 = rs while consp(rs1) && all(consp, xs) setcar!(rs1, func(map(car, xs)...)) rs1 = cdr(rs1) xs = map(cdr, xs) end rs end
julia> a = makelist(5, 0) (0 0 0 0 0) julia> map!(x -> x * x, a, iota(1 : 10)) (1 4 9 16 25) julia> a (1 4 9 16 25) julia> b = makelist(10, 0) (0 0 0 0 0 0 0 0 0 0) julia> map!(x -> x * x, b, iota(1 : 5)) (1 4 9 16 25 0 0 0 0 0) julia> b (1 4 9 16 25 0 0 0 0 0) julia> c = iota(1 : 10) (1 2 3 4 5 6 7 8 9 10) julia> map!(x -> x * x, c, c) (1 4 9 16 25 36 49 64 81 100) julia> c (1 4 9 16 25 36 49 64 81 100)
リスト : pred() が偽を返す要素でリストを分割する # 再帰版 function span(pred::Function, xs::List) if atom(xs) || !pred(car(xs)) (nil, xs) else ys, zs = span(pred, cdr(xs)) (cons(car(xs), ys), zs) end end # reverse!() を使う function span1(pred::Function, xs::List) zs = nil while consp(xs) && pred(car(xs)) zs = cons(car(xs), zs) xs = cdr(xs) end (reverse!(zs), xs) end
julia> span(x -> x < 6, iota(1 : 10)) ((1 2 3 4 5), (6 7 8 9 10)) julia> span(x -> x < 1, iota(1 : 10)) ((), (1 2 3 4 5 6 7 8 9 10)) julia> span(x -> x < 11, iota(1 : 10)) ((1 2 3 4 5 6 7 8 9 10), ()) julia> span1(x -> x < 6, iota(1 : 10)) ((1 2 3 4 5), (6 7 8 9 10)) julia> span1(x -> x < 1, iota(1 : 10)) ((), (1 2 3 4 5 6 7 8 9 10)) julia> span1(x -> x < 11, iota(1 : 10)) ((1 2 3 4 5 6 7 8 9 10), ())
リスト : リストの中で連続した等しい値を部分リストにまとめる function pack(xs::List) if atom(xs) nil else ys, zs = span(isequal(car(xs)), xs) cons(ys, pack(zs)) end end
julia> pack(list(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6)) ((1) (2 2) (3 3 3) (4 4 4 4) (5 5 5 5 5) (6))
リスト : ランレングス符号化 encode(xs::List) = map(ys -> cons(car((ys)), length(ys)), pack(xs))
julia> a = encode(list(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6)) ((1 . 1) (2 . 2) (3 . 3) (4 . 4) (5 . 5) (6 . 1))
リスト : 復号 decode(xs::List) = flatmap(xs -> makelist(cdr(xs), car(xs)), xs)
julia> a ((1 . 1) (2 . 2) (3 . 3) (4 . 4) (5 . 5) (6 . 1)) julia> decode(a) (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6)
リスト : 要素の選択 function select(xs::List) if atom(xs) nil elseif atom(cdr(xs)) list((car(xs), nil)) else cons((car(xs), cdr(xs)), map(ys -> (ys[1], cons(car(xs), ys[2])), select(cdr(xs)))) end end
引数 xs がリストでなければ nil を返します。次の elseif 節で、リストの要素が一つしかない場合は (car(xs), nil) をリストに格納して返します。これが再帰呼び出しの停止条件になります。次の else 節で先頭要素を選びます。これは (car(xs), cdr(xs)) をリストに格納するだけです。それ以外の要素を選ぶ場合、cdr(xs) に対して select() を再帰呼び出しし、返り値のタプルの第 2 要素 ys[2] (残りの要素を格納したリスト) に car(xs) を追加します。この処理は map を使うと簡単に実現できます。
julia> select(nil) () julia> select(list(1)) ((1, ())) julia> select(iota(1 : 5)) ((1, (2 3 4 5)) (2, (1 3 4 5)) (3, (1 2 4 5)) (4, (1 2 3 5)) (5, (1 2 3 4)))
リスト : 順列の生成 function permutations(xs::List) if atom(xs) cons(nil, nil) else flatmap(ys -> map(zs -> cons(ys[1], zs), permutations(ys[2])), select(xs)) end end
引数が空リストになるときが再帰の停止条件で、空リストを格納したリストを返します。このリストに対して要素を追加していきます。この処理は map() を二重に使うと簡単にできますが、リストの階層が一段深くなってしまいます。そこで flatmap() を使います。
ラムダ式の中で permutations() を再帰呼び出しをして、リスト ys[2] の順列を生成します。そして、その返り値に選択した要素 ys[1] を追加すれば順列を生成することができます。
julia> permutations(iota(1 : 4)) ((1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) (2 1 3 4) (2 1 4 3) (2 3 1 4) (2 3 4 1) (2 4 1 3) (2 4 3 1) (3 1 2 4) (3 1 4 2) (3 2 1 4) (3 2 4 1) (3 4 1 2) (3 4 2 1) (4 1 2 3) (4 1 3 2) (4 2 1 3) (4 2 3 1) (4 3 1 2) (4 3 2 1))