連結リスト (Mulist) の使用例
今回は mutable な連結リスト (モジュール Mulist) を使って、リスト操作の簡単なサンプルプログラムを作ってみましょう。
●循環リスト
連結リストは要素を一列に並べたデータ構造ですが、最後尾のセルと先頭のセルを連結することで要素をリング状に並べることができます。これを「循環リスト (circular list)」 といいます。次の図を見てください。
上図の連結リスト (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 問題の解法
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)」という基本的なデータ構造を作ってみましょう。たとえばチケットを買う場合、カウンタの前に並んで順番を待たなくてはいけません。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。これを表したのが下図です。
図 : キューの動作
このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「待ち行列」とか「先入れ先出し (FIFO : first-in, first-out)」と呼ばれます。
キューは連結リストを使って簡単に実装することができますが、大きな欠点もあります。連結リストをキューとして使う場合、データを追加するときに最後尾までセルをたどっていく操作が必要になるため、要素数が多くなるとデータの追加に時間がかかってしまうのです。
そこで、先頭のセルを参照する変数のほかに、最後尾のセルを参照する変数を用意します。こうすると、先頭からセルをたどらなくても、最後尾にデータを追加することができます。次の図を見てください。
図 : 連結リストによるキューの構造
先頭のセルを参照する変数 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 になります。
●プログラムの作成
それでは、プログラムを作りましょう。最初に作成する関数を表に示します。
| 関数 | 機能 |
|---|---|
| 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 倍高速化することができました。
●リストで遊ぼう (Part 2)
- リスト xs の i 番目に x を挿入する関数 insert!(xs, i, x) を定義してください。
この関数は xs を破壊的に修正し、x を挿入したリストを返します。 - リスト xs の i 番目の要素を削除する関数 deleteat!(xs, i, x) を定義してください。
この関数は xs を破壊的に修正し、要素を削除したリストを返します。 - getindex() と setindex!() を定義して、角カッコで要素にアクセスできるようにしてください。
- リスト xs と ys の要素を交互に並べたリストを生成する関数 interleave() を定義してください。
- interleave() の破壊的操作版 interleave!() を定義してください。
- リスト xs の要素の間に x を挿入する関数 intersperse(xs, x) を定義してください。
- intersperse() の破壊的操作版 intersperse!() を定義してください。
- map(func, xs) の結果を平坦化する関数 flatmap(func, xs) を定義してください。
- 引数のリスト rs に計算結果を格納するマップ関数 map!(func, rs [,args...]) を定義してください。
- 関数 pred() が偽を返す要素でリストを分ける関数 span(pred, xs) を定義してください。
- リスト xs の中で連続した等しい値を部分リストにまとめる関数 pack(xs) を定義してください。
- 連続している同じ値を (val . num) に変換する関数 encode を定義してください。val は値、num は個数を表します。
なお、このような変換を「ランレングス符号化」といいます。 - encode() の逆変換を行う関数 decode() を定義してください。
- リスト xs から要素を一つ選んで、選んだ要素と残りの要素を返す関数 select(xs) を定義してください。
この関数は選んだ要素と残りの要素をタプルに格納し、それをリストに格納して返します。 - select() を使って順列を生成するプログラムを作ってください。
解答１
リスト : データの挿入
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)
解答10
リスト : 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), ())
解答11
リスト : リストの中で連続した等しい値を部分リストにまとめる
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))
解答12
リスト : ランレングス符号化 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))
解答13
リスト : 復号 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)
解答14
リスト : 要素の選択
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)))
解答15
リスト : 順列の生成
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))