M.Hiroi's Home Page

Julia Language Programming

お気楽 Julia プログラミング超入門

[ Home | Light | Julia ]

Julia の基礎知識

●do block

julia> xs = [1, 2, 3, 4, 5]
5-element Vector{Int64}:
 1
 2
 3
 4
 5

julia> map(x -> x * x, xs)
5-element Vector{Int64}:
  1
  4
  9
 16
 25

julia> map(xs) do x
       x * x
       end
5-element Vector{Int64}:
  1
  4
  9
 16
 25
julia> foldr((x, y) -> x + y, xs, init=0)
15

julia> foldr(xs, init=0) do x, y
       x + y
       end
15
julia> function map2(f, xs, ys)
       zs = []
       for (x, y) = zip(xs, ys)
       push!(zs, f(x, y))
       end
       zs
       end
map2 (generic function with 1 method)

julia> map2([1, 2, 3], [4, 5, 6]) do x, y
       (x, y)
       end
3-element Vector{Any}:
 (1, 4)
 (2, 5)
 (3, 6)

●getindex() と setindex!()

julia> mutable struct Foo
       a
       b
       c
       end

julia> function Base.getindex(x::Foo, i::Int)
       if i == 1
       x.a
       elseif i == 2
       x.b
       elseif i == 3
       x.c
       else
       throw(BoundsError(x, i))
       end
       end

julia> x = Foo(1, 2, 3)
Foo(1, 2, 3)

julia> x[1]
1

julia> x[2]
2

julia> x[3]
3

julia> x[4]
ERROR: BoundsError: attempt to access Foo at index [4]

julia> function Base.setindex!(x::Foo, v, i::Int)
       if i == 1
       x.a = v
       elseif i == 2
       x.b = v
       elseif i == 3
       x.c = v
       else
       throw(BoundsError(x, i))
       end
       end

julia> x
Foo(1, 2, 3)

julia> x[1] = 10
10

julia> x
Foo(10, 2, 3)

julia> x[3] = 30
30

julia> x[3]
30

julia> x
Foo(10, 2, 30)

julia> Base.lastindex(x::Foo) = 3

julia> x[end]
30

julia> x[end - 1]
2

●タスク (Channel 編)

julia> function foo(c::Channel)
       put!(c, "foo start")
       for x = 1 : 4
       put!(c, x)
       end
       put!(c, "foo stop")
       end
foo (generic function with 1 method)

julia> c = Channel(foo)
Channel{Any}(0) (1 item available)

julia> isopen(c)
true

julia> take!(c)
"foo start"

julia> take!(c)
1

julia> take!(c)
2

julia> take!(c)
3

julia> take!(c)
4

julia> take!(c)
"foo stop"

julia> isopen(c)
false

julia> take!(c)
ERROR: InvalidStateException("Channel is closed.", :closed)

julia> for x = Channel(foo)
       println(x)
       end
foo start
1
2
3
4
foo stop
julia> a = rand(8)
8-element Vector{Float64}:
 0.9696171847103765
 0.5789186600045584
 0.13710042153456103
 0.920535882493211
 0.697528020292991
 0.25024663580419815
 0.9450074234009469
 0.35114804306391556

julia> c = Channel(ch -> foreach(x -> put!(ch, x), a))
Channel{Any}(0) (1 item available)

julia> take!(c)
0.9696171847103765

julia> take!(c)
0.5789186600045584

julia> take!(c)
0.13710042153456103

julia> take!(c)
0.920535882493211

julia> take!(c)
0.697528020292991

julia> take!(c)
0.25024663580419815

julia> take!(c)
0.9450074234009469

julia> take!(c)
0.35114804306391556

julia> include("list.jl")

julia> d = LinkedList()
()

julia> for x = a
       insert!(d, 0, x)
       end

julia> e = Channel(ch -> foreach(x -> put!(ch, x), d))
Channel{Any}(0) (1 item available)

julia> take!(e)
0.35114804306391556

julia> take!(e)
0.9450074234009469

julia> take!(e)
0.25024663580419815

julia> take!(e)
0.697528020292991

julia> take!(e)
0.920535882493211

julia> take!(e)
0.13710042153456103

julia> take!(e)
0.5789186600045584

julia> take!(e)
0.9696171847103765
リスト : コルーチンの簡単な使用例 (co1.jl)

function printcode(ch::Channel, code)
    while true
        print(code)
        put!(ch, true)
    end
end

function test_a(n)
    cs = map(x -> Channel(c -> printcode(c, x)), ["h", "e", "y", "!", " "])
    for _ = 1 : n, c = cs
        take!(c)
    end
end

# n から始まる整数列
function integers(c, n)
    while true
        put!(c, n)
        n += 1
    end
end

# フィルター
function sieve_filter(f, src)
    Channel(c ->
        while true
            n = take!(src)
            if f(n) put!(c, n) end
        end)
end

# エラトステネスの篩
function sieve(x)
    nums = Channel(c -> integers(c, 2))
    for _ = 1 : x
        n = take!(nums)
        print("$n ")
        nums = sieve_filter(x -> x % n != 0, nums)
    end
end
julia> include("col.jl")
sieve (generic function with 1 method)

julia> test_a(5)
hey! hey! hey! hey! hey! hey!
julia> test_a(10)
hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey!
julia> sieve(25)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
julia> sieve(100)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 
131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 
263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 
409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

●タスク (Task 編)

julia> function test(name, w)
       for _ = 1 : 10
       sleep(w)
       println(name)
       yield()
       end
       end
test (generic function with 1 method)

julia> a = @task test("foo", 0.3)
Task (runnable) @0x000000001051a850

julia> b = @task test("bar", 0.5)
Task (runnable) @0x000000001051ab30

julia> c = @task test("oops", 0.7)
Task (runnable) @0x000000001051b0f0

julia> istaskstarted(a)
false

julia> istaskstarted(b)
false

julia> istaskstarted(c)
false

julia> schedule(a); schedule(b); schedule(c)
Task (runnable) @0x000000001051b0f0

julia> foo
bar
foo
oops
foo
bar
foo
oops
foo
bar
foo
bar
oops
foo
foo
bar
foo
oops
bar
foo
oops
bar
bar
oops
bar
oops
bar
oops
oops
oops
julia> istaskdone(a)
true

julia> istaskdone(b)
true

julia> istaskdone(c)
true

julia> @async test("foo", 0.5)
Task (runnable) @0x000000001103e570

julia> foo
foo
foo
foo
foo
foo
foo
foo
foo
foo
julia> ch = Channel(0)
Channel{Any}(0) (empty)

julia> a = @async foreach(x -> put!(ch, x), 1 : 5)
Task (runnable) @0x0000000010aa2e10

julia> while !istaskdone(a)
       println(take!(ch))
       end
1
2
3
4
5

julia> isopen(ch)
true

julia> close(ch)

julia> ch = Channel(0)
Channel{Any}(0) (empty)

julia> a = @async foreach(x -> put!(ch, x), 1 : 5)
Task (runnable) @0x0000000011081fb0

julia> bind(ch, a)
Channel{Any}(0) (1 item available)

julia> for x = ch
       println(x)
       end
1
2
3
4
5

julia> istaskdone(a)
true

julia> isopen(ch)
false
julia> c = current_task()
Task (runnable) @0x000000000eac5150

julia> a = Task(() -> foreach(x -> println(yieldto(c, x)), 1 : 5))
Task (runnable) @0x000000000eac45d0

julia> yieldto(a, 10)
1

julia> yieldto(a, 11)
11
2

julia> yieldto(a, 12)
12
3

julia> yieldto(a, 13)
13
4

julia> yieldto(a, 14)
14
5

julia> yieldto(a, 15)
15
フリーズする (CTRL-C で中断する)
リスト : yieldto() の簡単な使用例 (co1.jl に追加)

function printcode1(next::Task, code)
    while true
        print(code)
        yieldto(next)
    end
end

function test_b(n)
    ch = current_task()
    a = @task printcode1(ch, " ")
    b = @task printcode1(a, "!")
    c = @task printcode1(b, "y")
    d = @task printcode1(c, "e")
    e = @task printcode1(d, "h")
    for _ = 1 : n
        yieldto(e)
    end
end
julia> test_b(5)
hey! hey! hey! hey! hey!
julia> test_b(20)
hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey! hey!

簡単なプログラム

●二分木 (mutable)

#
# tree.jl : 二分探索木 (mutable)
#
#           Copyright (C) 2016-2021 Makoto Hiroi
#

# 空の木 は Nothing (nothing) で表す

# 節
mutable struct Node
    item
    left::Union{Node, Nothing}
    right::Union{Node, Nothing}
end

# 型に別名を付ける
Tree = Union{Node, Nothing}

# 二分木
mutable struct Tree2
    root::Tree
    Tree2() = new(nothing)
end

#
# 作業用
#

# 挿入
function insert_node(node::Tree, x)
    if node === nothing
        return Node(x, nothing, nothing)
    elseif x < node.item
        node.left = insert_node(node.left, x)
    else
        node.right = insert_node(node.right, x)
    end
    node
end

# 探索
function search_node(node::Tree, x)
    while node !== nothing
        if node.item == x
            return true
        elseif x < node.item
            node = node.left
        else
            node = node.right
        end
    end
    false
end

# 最小値と最大値
function search_min_node(node::Tree)
    while node.left !== nothing
        node = node.left
    end
    node.item
end

function search_max_node(node::Tree)
    while node.right !== nothing
        node = node.right
    end
    node.item
end

# 最大値と最小値の削除
function delete_min_node(node::Tree)
    if node.left === nothing
        node.right
    else
        node.left = delete_min_node(node.left)
        node
    end
end

function delete_max_node(node::Tree)
    if node.right === nothing
        node.left
    else
        node.right = delete_max_node(node.right)
        node
    end
end

# 削除
function delete_node(node::Tree, x)
    if node === nothing
        return node
    end
    if node.item == x
        if node.left === nothing
            return node.right
        elseif node.right === nothing
            return node.left
        else
            node.item = search_min_node(node.right)
            node.right = delete_min_node(node.right)
        end
    elseif x < node.item
        node.left = delete_node(node.left, x)
    else
        node.right = delete_node(node.right, x)
    end
    node
end

# 巡回
function foreach_node(func::Function, node::Nothing)
end
function foreach_node(func::Function, node::Node)
    foreach_node(func, node.left)
    func(node.item)
    foreach_node(func, node.right)
end

# イテレータ用
function next_node(node::Node, buff::Vector{Node})
    while node !== nothing
        push!(buff, node)
        node = node.left
    end
end

#
# 公開用
#

# 挿入
function Base.insert!(tree::Tree2, x)
    tree.root = insert_node(tree.root, x)
end

# 探索
function search(tree::Tree2, x)
    search_node(tree.root, x)
end

# 最大値と最小値
function search_max(tree::Tree2)
    if tree.root === nothing
        error("search_max: empty tree")
    else
        search_max_node(tree.root)
    end
end

function search_min(tree::Tree2)
    if tree.root === nothing
        error("search_min: empty tree")
    else
        search_min_node(tree.root)
    end
end

# 削除
function Base.delete!(tree::Tree2, x)
    tree.root = delete_node(tree.root, x)
end

function delete_max!(tree::Tree2)
    if tree.root !== nothing
        tree.root = delete_max_node(tree.root)
    end
end

function delete_min!(tree::Tree2)
    if tree.root !== nothing
        tree.root = delete_min_node(tree.root)
    end
end

# 巡回
function Base.foreach(func::Function, tree::Tree2)
    foreach_node(func, tree.root)
end

# 空の木か?
Base.isempty(tree::Tree2)  = tree.root === nothing

# イテレータ
function Base.iterate(tree::Tree2)
    buff = Node[]
    if tree.root === nothing
        nothing
    else
        next_node(tree.root, buff)
        (buff[end].item, buff)
    end
end
function Base.iterate(tree::Tree2, state)
    if isempty(state)
        nothing
    else
        node = pop!(state)
        if node.right !== nothing
            next_node(node.right, state)
        end
        if isempty(state)
            nothing
        else
            (state[end].item, state)
        end
    end
end

# 表示
function Base.show(io::IO, xs::Tree2)
    print(io, "Tree2: ")
    for x = xs
        print("$x ")
    end
end

# 簡単なテスト
a = Tree2()
println(a)
println(isempty(a))

# 挿入
for x = [5, 3, 7, 1, 4, 2, 9, 6, 8]
    print("insert $x -> ")
    insert!(a, x)
    println(a)
end

# 巡回
foreach(println, a)

# 検索
for x = 0 : 10
    print("search $x -> ")
    println(search(a, x))
end
println("min: ", search_min(a))
println("max: ", search_max(a))

# 削除
print("delete max -> ")
delete_max!(a)
println(a)
print("delete min -> ")
delete_min!(a)
println(a)
for x = 1 : 9
    print("delete $x -> ")
    delete!(a, x)
    println(a)
end
println(a)
println(isempty(a))
$ julia tree.jl
Tree2:
true
insert 5 -> Tree2: 5
insert 3 -> Tree2: 3 5
insert 7 -> Tree2: 3 5 7
insert 1 -> Tree2: 1 3 5 7
insert 4 -> Tree2: 1 3 4 5 7
insert 2 -> Tree2: 1 2 3 4 5 7
insert 9 -> Tree2: 1 2 3 4 5 7 9
insert 6 -> Tree2: 1 2 3 4 5 6 7 9
insert 8 -> Tree2: 1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
search 0 -> false
search 1 -> true
search 2 -> true
search 3 -> true
search 4 -> true
search 5 -> true
search 6 -> true
search 7 -> true
search 8 -> true
search 9 -> true
search 10 -> false
min: 1
max: 9
delete max -> Tree2: 1 2 3 4 5 6 7 8
delete min -> Tree2: 2 3 4 5 6 7 8
delete 1 -> Tree2: 2 3 4 5 6 7 8
delete 2 -> Tree2: 3 4 5 6 7 8
delete 3 -> Tree2: 4 5 6 7 8
delete 4 -> Tree2: 5 6 7 8
delete 5 -> Tree2: 6 7 8
delete 6 -> Tree2: 7 8
delete 7 -> Tree2: 8
delete 8 -> Tree2:
delete 9 -> Tree2:
Tree2:
true

●二分木 (immutable)

#
# imtree.jl : immutable な二分木
#
#             Copyright (C) 2016-2021 Makoto Hiroi
#
abstract type Tree end

# 空の木
struct Nil <: Tree
end

# 節
struct Node <: Tree
    item
    left::Tree
    right::Tree
end

const nil = Nil()

# 空の木か?
Base.isempty(node::Tree) = node === nil

# 探索
function search_tree(node::Tree, x)
    while !isempty(node)
        if node.item == x
            return true
        elseif x < node.item
            node = node.left
        else
            node = node.right
        end
    end
    return false
end

# 最小値の探索
function search_min(node::Node)
    while !isempty(node.left)
        node = node.left
    end
    node.item
end

# 最大値の探索
function search_max(node::Node)
    while !isempty(node.right)
        node = node.right
    end
    node.item
end

# 挿入
function insert_tree(node::Tree, x)
    if isempty(node)
        Node(x, nil, nil)
    elseif x == node.item
        node
    elseif x < node.item 
        Node(node.item, insert_tree(node.left, x), node.right)
    else
        Node(node.item, node.left, insert_tree(node.right, x))
    end
end

# 最小値の削除
function delete_min(node::Node)
    if isempty(node.left)
        node.right
    else
        Node(node.item, delete_min(node.left), node.right)
    end
end

# 最大値の削除
function delete_max(node::Node)
    if isempty(node.right)
        node.left
    else
        Node(node.item, node.left, delete_max(node.right))
    end
end

# 削除
function delete_tree(node::Tree, x)
    if isempty(node)
        nil
    elseif node.item == x
        if node.left == nil; return node.right; end
        if node.right == nil; return node.left; end
        Node(search_min(node.right), node.left, delete_min(node.right))
    elseif x < node.item
        Node(node.item, delete_tree(node.left, x), node.right)
    else
        Node(node.item, node.left, delete_tree(node.right, x))
    end
end

# 木の巡回
function Base.foreach(f, node::Tree)
    if !isempty(node)
        foreach(f, node.left)
        f(node.item)
        foreach(f, node.right)
    end
end

# イテレータ
function next_node(node::Tree, buff::Vector{Tree})
    while !isempty(node)
        push!(buff, node)
        node = node.left
    end
end

function Base.iterate(node::Tree)
    buff = Tree[]
    if node == nil
        nothing
    else
        next_node(node, buff)
        (buff[end].item, buff)
    end
end
function Base.iterate(tree::Tree, state)
    if isempty(state)
        nothing
    else
        node = pop!(state)
        if !isempty(node.right)
            next_node(node.right, state)
        end
        if isempty(state)
            nothing
        else
            (state[end].item, state)
        end
    end
end

# 表示
function Base.show(io::IO, xs::Tree)
    print(io, "Tree: ")
    for x = xs
        print("$x ")
    end
end

#
# 簡単なテスト
#
a = nil
println(a)
println(isempty(a))

# 挿入
for x = [5, 3, 7, 1, 4, 2, 9, 6, 8]
    print("insert $x -> ")
    global a = insert_tree(a, x)
    println(a)
end

# 巡回
foreach(println, a)

# 検索
for x = 0 : 10
    print("search $x -> ")
    println(search_tree(a, x))
end
println("min: ", search_min(a))
println("max: ", search_max(a))

# 削除
print("delete max -> ")
a = delete_max(a)
println(a)
print("delete min -> ")
a = delete_min(a)
println(a)
for x = 1 : 9
    print("delete $x -> ")
    global a = delete_tree(a, x)
    println(a)
end
println(a)
println(isempty(a))
$ julia imtree.jl
Tree:
true
insert 5 -> Tree: 5
insert 3 -> Tree: 3 5
insert 7 -> Tree: 3 5 7
insert 1 -> Tree: 1 3 5 7
insert 4 -> Tree: 1 3 4 5 7
insert 2 -> Tree: 1 2 3 4 5 7
insert 9 -> Tree: 1 2 3 4 5 7 9
insert 6 -> Tree: 1 2 3 4 5 6 7 9
insert 8 -> Tree: 1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
7
8
9
search 0 -> false
search 1 -> true
search 2 -> true
search 3 -> true
search 4 -> true
search 5 -> true
search 6 -> true
search 7 -> true
search 8 -> true
search 9 -> true
search 10 -> false
min: 1
max: 9
delete max -> Tree: 1 2 3 4 5 6 7 8
delete min -> Tree: 2 3 4 5 6 7 8
delete 1 -> Tree: 2 3 4 5 6 7 8
delete 2 -> Tree: 3 4 5 6 7 8
delete 3 -> Tree: 4 5 6 7 8
delete 4 -> Tree: 5 6 7 8
delete 5 -> Tree: 6 7 8
delete 6 -> Tree: 7 8
delete 7 -> Tree: 8
delete 8 -> Tree:
delete 9 -> Tree:
Tree:
true

●カッコ列

カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。今回はカッコ列を生成する高階関数 kakko() を作ります。

リスト : カッコ列

function kakko(f, n)
    function iter(x, y, a)
        if x == y == n
            f(a)
        else
            if x < n
                iter(x + 1, y, a * "(")
            end
            if y < x
                iter(x, y + 1, a * ")")
            end
        end
    end
    iter(0, 0, "")
end

kakko(println, 3)
kakko(println, 4)

カッコ列の生成は簡単です。局所関数 iter() の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 a は累積変数でカッコ列を表す文字列です。

バランスの取れたカッコ列の場合、x, y, n には y <= x <= n の関係が成り立ちます。x == y == n の場合、カッコ列がひとつ完成しました。引数の関数 f を呼び出します。そうでなければ、iter() を再帰呼び出しします。x < n であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。

((()))
(()())
(())()
()(())
()()()
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

●カッコ列の総数

カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数 \(\mathrm{C}_n\)は次に示す公式で求めることができます。

\( \mathrm{C}_n = \dfrac{(2n)!}{(n+1)!n!} \)

これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。


              図 : 道順の総数の求め方

A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 C4 に相当し、その値は 14 となります。

プログラムは配列を使うと簡単です。次の図を見てください。

0 : [1, 1, 1, 1, 1]

1 : [1, 1, 1, 1, 1,]

2 : [1, 1, 1+1=2, 2+1=3, 3+1=4]
 => [1, 1, 2, 3, 4]

3 : [1, 1, 2, 3+2=5, 5+4=9]
 => [1, 1, 2, 5, 9]

4 : [1, 1, 2, 5, 5+9=14]
 => [1, 1, 2, 5, 14]

上図は Cn (n = 4) を求める場合です。大きさが n + 1, 要素の値が 1 のベクタを用意します。n = 0, 1 の場合は n 番目の要素をそのまま返します。n が 2 よりも大きい場合、変数 i を 2 に初期化して、i - 1 番目以降の要素の累積和を求めます。

たとえば i = 2 の場合、2 番目の要素は 1 番目の要素と自分自身を加算した値 2 になります。3 番目の要素は 2 番目の要素と自分自身を足した値 3 になり、4 番目の要素は 3 + 1 = 4 になります。次に i を +1 して同じことを繰り返します。3 番目の要素は 2 + 3 = 5 になり、4 番目の要素は 5 + 4 = 9 になります。i = 4 のとき、4 番目の要素は 5 + 9 = 14 となり、C4 の値を求めることができました。

リスト : カッコ列の総数

function kakko_num(n)
    table = fill(big(1), n)
    for i =  2 : n, j = i : n
        table[j] += table[j - 1]
    end
    table[n]
end

for i = 1 : 10
    println(kakko_num(i))
end
println(kakko_num(50))
println(kakko_num(100))
1
2
5
14
42
132
429
1430
4862
16796
1978261657756160653623774456
896519947090131496687170070074100632420837521538745909320

●カッコ列と二分木

バランスの取れたカッコ列と二分木は 1 対 1 に対応します。二分木を行きがけ順で巡回するとき、途中の節では左カッコ ( を出力して左右の枝をたどり、葉に到達したら右カッコ ) を出力すると、カッコ列を生成することができます。

リスト : カッコ列と二分木

# 二分木
abstract type Tree end

# 節
struct Node <: Tree
    left::Tree
    right::Tree
end

# 葉
struct Leaf <: Tree
end

# 二分木をカッコ列に変換
function tree_to_kakko(tree::Tree)
    function iter(tree::Tree)
        if typeof(tree) == Leaf
            ")"
        else
            "(" * iter(tree.left) * iter(tree.right)
        end
    end
    s = iter(tree)
    s[1 : end - 1]
end

# カッコ列を二分木に変換
function kakko_to_tree(s)
    function iter(i)
        if length(s) < i
            (Leaf(), i)
        elseif s[i] == ')'
            (Leaf(), i + 1)
        elseif s[i] == '('
            l, j = iter(i + 1)
            r, k = iter(j)
            (Node(l, r), k)
        else
            error("illegal char")
        end
    end
    iter(1)[1]
end

function test(s)
    println(s)
    t = kakko_to_tree(s)
    println(t)
    u = tree_to_kakko(t)
    println(u)
end

kakko(test, 3)

関数 tree_to_kakko() の実際の処理は局所関数 iter() で行います。引数が葉 (Leaf) の場合は右カッコを返します。引数が節 (Node) の場合は、iter() を再帰呼び出しして左部分木 left をたどり、それから右部分木 right をたどります。その結果と左カッコを演算子 * で連結すればいいわけです。ただし、最後に余分な右カッコが付いてくるので、最後の要素を削除します。

二分木の場合、葉 (Leaf) の個数を n とすると、節 (Node) の個数は n - 1 になります。カッコ列と違って Leaf の個数が一つ多くなることに注意してください。

関数 kakko_to_tree() も局所関数 iter() で変換処理を行います。文字列 s の i 番目の要素が右カッコの場合は (Leaf(), i + 1) を返します。左カッコの場合は、iter() を再帰呼び出しして左部分木 l を生成し、それから右部分木 r を生成します。あとは (Node(l, r), k) を返すだけです。ただし、葉に対応する右カッコがひとつ少ないので、引数 i が文字列の終端に到達した場合は Leaf() を返すようにします。

((()))
Node(Node(Node(Leaf(),Leaf()),Leaf()),Leaf())
((()))
(()())
Node(Node(Leaf(),Node(Leaf(),Leaf())),Leaf())
(()())
(())()
Node(Node(Leaf(),Leaf()),Node(Leaf(),Leaf()))
(())()
()(())
Node(Leaf(),Node(Node(Leaf(),Leaf()),Leaf()))
()(())
()()()
Node(Leaf(),Node(Leaf(),Node(Leaf(),Leaf())))
()()()

2021/11/27 改訂: Julia のバージョンを 1.6 に変更

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

[ Home | Light | Julia ]