M.Hiroi's Home Page

Julia Language Programming

お気楽 Julia プログラミング超入門 : 番外編


Copyright (C) 2018-2021 Makoto Hiroi
All rights reserved.

連結リスト (Mulist) の使用例

今回は 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 問題の解法

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 倍高速化することができました。

●リストで遊ぼう (Part 2)

  1. リスト xs の i 番目に x を挿入する関数 insert!(xs, i, x) を定義してください。
    この関数は xs を破壊的に修正し、x を挿入したリストを返します。
  2. リスト xs の i 番目の要素を削除する関数 deleteat!(xs, i, x) を定義してください。
    この関数は xs を破壊的に修正し、要素を削除したリストを返します。
  3. getindex() と setindex!() を定義して、角カッコで要素にアクセスできるようにしてください。
  4. リスト xs と ys の要素を交互に並べたリストを生成する関数 interleave() を定義してください。
  5. interleave() の破壊的操作版 interleave!() を定義してください。
  6. リスト xs の要素の間に x を挿入する関数 intersperse(xs, x) を定義してください。
  7. intersperse() の破壊的操作版 intersperse!() を定義してください。
  8. map(func, xs) の結果を平坦化する関数 flatmap(func, xs) を定義してください。
  9. 引数のリスト rs に計算結果を格納するマップ関数 map!(func, rs [,args...]) を定義してください。
  10. 関数 pred() が偽を返す要素でリストを分ける関数 span(pred, xs) を定義してください。
  11. リスト xs の中で連続した等しい値を部分リストにまとめる関数 pack(xs) を定義してください。
  12. 連続している同じ値を (val . num) に変換する関数 encode を定義してください。val は値、num は個数を表します。
    なお、このような変換を「ランレングス符号化」といいます。
  13. encode() の逆変換を行う関数 decode() を定義してください。
  14. リスト xs から要素を一つ選んで、選んだ要素と残りの要素を返す関数 select(xs) を定義してください。
    この関数は選んだ要素と残りの要素をタプルに格納し、それをリストに格納して返します。
  15. select() を使って順列を生成するプログラムを作ってください。

解答1

リスト : データの挿入

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)

解答2

リスト : データの削除

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)

解答3

リスト : 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)

解答4

リスト : 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)

解答5

リスト : 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)

解答6

リスト : リストの要素の間にデータを挿入する

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)

解答7

リスト : 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)

解答8

リスト : 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)

解答9

リスト : 引数のリストに評価結果を格納するマップ関数

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))

初版 2018 年月日
改訂 2021 年 12 月 5 日