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)
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
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.
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
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!
#
# 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
#
# 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\)は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 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]
上図は Ｃn (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 となり、Ｃ4 の値を求めることができました。
リスト : カッコ列の総数
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()))) ()()()