M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Julia Language Programming

簡単なプログラム

[ Home | Light | Julia ]

●FizzBuzz

リスト : FizzBuzz 問題

# コメント
#=
  コメント
=#
function fizzbuzz()
    for x in 1 : 100
        if x % 15 == 0
            print("FizzBuzz")
        elseif x % 3 == 0
            print("Fizz")
        elseif x % 5 == 0
            print("Buzz")
        else
            print(x)
        end
        print(" ")
    end
end

fizzbuzz()
C>julia fizzbuzz.jl
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

●数値積分

リスト : 中点則で円周率を求める

function midpoint(n)
    w = 1.0 / n
    s = 0.0
    for i in 1 : n
        x = (i - 0.5) * w;
        s += 4.0 / (1.0 + x * x);
    end
    s * w
end

print(midpoint(10000))
C>julia midpoint.jl
3.141592654423134

●平均値と標準偏差

リスト : 平均値と標準偏差

# 乱数で生成した身長のデータ
# データ型は Array{Float64, 1} になる
height = [
    148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
    138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
    152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
    153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
    153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
    152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
    150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
    164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
    151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
    158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3,
]

# 平均値と標準偏差
function meansd(xs)
    m = sum(xs) / length(xs)
    s = 0.0
    for x in xs
        s += (x - m) * (x - m)
    end
    m, sqrt(s / length(xs))
end

# 1 回の読み込みで求める
function meansd2(xs)
    m, s = 0.0, 0.0
    k = length(xs)
    for i in 1 : k
        x = xs[i] - m
        m += x / i
        s += (i - 1) * x * x / i
    end
    m, sqrt(s / k)
end

println(meansd(height))
println(meansd2(height))
C>julia mean.jl
(150.627,6.433472701426503)
(150.62699999999998,6.433472701426506)

●パスカルの三角形

リスト : パスカルの三角形

# 2 次元配列版
function pascal(n)
    table = Array(Int, n, n)
    table[1, 1] = table[2, 1] = table[2, 2] = 1
    for i in 3 : n
        table[i, 1] = 1
        for j in 2 : i - 1
            table[i, j] = table[i - 1, j - 1] + table[i - 1, j]
        end
        table[i, i] = 1
    end
    for i in 1 : n
        for j in 1 : i
            @printf "%d " table[i, j]
        end
        print("\n")
    end
end

# 1 次元配列版
function pascal1(n)
    table = Array(Int, n)
    fill!(table, 1)
    println(table[1])
    @printf "%d %d\n" table[1] table[2]
    for i in 3 : n
        for j in i - 1 : -1 : 2
            table[j] += table[j - 1]
        end
        # 表示
        for j in 1 : i
            @printf "%d " table[j]
        end
        print("\n")
    end
end

pascal(15)
# pascal1(15)
C>julia pascal.jl
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1

●素数

Julia には n 以下の素数を求める関数 primes(n) が用意されているので、私たちが素数を求める関数を自作する必要はありませんが、Julia のお勉強ということで、あえてプログラムを作ってみましょう。

リスト : 素数

# 単純版
function checkPrime(ps, x)
    for p in ps
        if p * p > x; break; end
        if x % p == 0; return false; end
    end
    true
end

function makePrimes(n)
    ps = [2]
    x = 1
    for x in 3 : 2 : n
        if checkPrime(ps, x); push!(ps, x); end
    end
    ps
end

# エラトステネスの篩 (1)
function sieve(n)
    ps = [2]
    xs = collect(3 : 2 : n)
    while xs[1] * xs[1] <= n
        p = xs[1]
        push!(ps, p)
        filter!(x -> x % p != 0, xs)
    end
    append!(ps, xs)
end

# エラトステネスの篩 (2)
function sieve1(n)
    ps = [2]
    k = div(n, 2)
    xs = Array(Bool, k)
    fill!(xs, true)
    x = 3
    while x * x <= n
        i = div(x, 2)
        if xs[i]
            push!(ps, x)
            for j in i + x : x : k; xs[j] = false; end
        end
        x += 2
    end
    while x <= n
        i = div(x, 2)
        if xs[i]; push!(ps, x); end
        x += 2
    end
    ps
end

println(makePrimes(1000))
# println(sieve(1000))
# println(sieve1(1000))
C>julia prime.jl
[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,547,557,563,569,571,577,587,
593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
997]

●再帰定義

リスト : 再帰定義

# 階乗
function fact(n)
    if n == 0
        BigInt(1)    # one(n) とすると引数 n のデータ型で値を求める
    else
       n * fact(n - 1)
    end
end

# 階乗 (繰り返し版)
function facti(n)
    a = BigInt(1)    # a::BigInt = 1 でもよい
    for x in 2 : n
      a *= x
    end
    a
end

# フィボナッチ数 (二重再帰)
function fibo(n)
    if n == 0
        0
    elseif n == 1
        1
    else
        fibo(n - 2) + fibo(n - 1)
    end
end

# フィボナッチ数 (繰り返し版)
function fiboi(n)
    a = BigInt(0)    # zero(n)
    b = BigInt(1)    # one(n) とすると引数のデータ型で値を求める
    for _ in 1 : n
        a, b = b, a + b
    end
    a
end

for x in 0:20
    println(fact(x))
end
println(facti(50))
for x in 0:20
    @printf "%d " fibo(x)
end
println("")
println(fiboi(50))
println(fiboi(100))
C>julia fact.jl
1
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
30414093201713378043612608166064768844377641568960512000000000000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
12586269025
354224848179261915075

●高階関数

リスト : 高階関数

# マッピング
function map1(fn, xs)
    a::typeof(xs) = []
    for x in xs
        push!(a, fn(x))
    end
    a
end

# フィルター
function filter1(fn, xs)
    a::typeof(xs) = []
    for x in xs
        if fn(x)
            push!(a, x)
        end
    end
    a
end

# 畳み込み
function foldleft(fn, a, xs)
    for x in xs
        a = fn(a, x)
    end
    a
end

xs = collect(1:10)
println(map1(x -> x * x, xs))
println(map(x -> x * x, xs))
println(filter1(x -> x % 2 == 0, xs))
println(filter(x -> x % 2 == 0, xs))
println(foldleft(+, 0, xs))
println(reduce(+, 0, xs))
C>julia higher.jl
[1,4,9,16,25,36,49,64,81,100]
[1,4,9,16,25,36,49,64,81,100]
[2,4,6,8,10]
[2,4,6,8,10]
55
55

●順列と組み合わせ

リスト : 順列と組み合わせ

# xs の中から n 個を選ぶ順列
function permutation(fn, n, xs)
    ys::typeof(xs) = []

    function perm()
        if length(ys) == n
            fn(ys)
        else
            for x in xs
                if x in ys; continue; end
                push!(ys, x)
                perm()
                pop!(ys)
            end
        end
    end

    perm()
end

# xs の中から n 個を選ぶ組み合わせ
function combination(fn, n, xs)
    ys::typeof(xs) = []

    function comb(m)
        if length(ys) == n
            fn(ys)
        elseif length(xs) - m + 1 >= n - length(ys)
            push!(ys, xs[m])
            comb(m + 1)
            pop!(ys)
            comb(m + 1)
        end
    end

    comb(1)
end

permutation(print, 3, [1,2,3])
println("")
for xs in permutations([1,2,3])
    print(xs)
end
println("")
combination(print, 3, [1,2,3,4,5])
println("")
for xs in combinations([1,2,3,4,5], 3)
    print(xs)
end
println("")
C>julia perm.jl
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
[1,2,3][1,2,4][1,2,5][1,3,4][1,3,5][1,4,5][2,3,4][2,3,5][2,4,5][3,4,5]
[1,2,3][1,2,4][1,2,5][1,3,4][1,3,5][1,4,5][2,3,4][2,3,5][2,4,5][3,4,5]

●経路の探索

リスト : 経路の探索

#=
     2───4───6 
   /│      │
 1  │      │
   \│      │
     3───5───7

        経路図
=#

# 隣接リスト (配列の配列)
adjacent = Array{Int,1}[
    [2, 3],
    [1, 3, 4],
    [1, 2, 5],
    [2, 5, 6],
    [3, 4, 7],
    [4],
    [5]
]

# 深さ優先探索
function dfs(goal, xs)
    if xs[end] == goal
        println(xs)
    else
        for p in adjacent[xs[end]]
            if p in xs; continue; end
            push!(xs, p)
            dfs(goal, xs)
            pop!(xs)
        end
    end
end

# 幅優先探索
function bfs(start, goal)
    que = Array{Int,1}[[1]]
    while length(que) > 0
        xs = shift!(que)
        if xs[end] == goal
            println(xs)
        else
            for p in adjacent[xs[end]]
                if p in xs; continue; end
                ys = copy(xs)
                push!(ys, p)
                push!(que, ys)
            end
        end
    end
end

# 反復深化
function ids(start, goal)
    function dfs(xs, limit)
        if length(xs) == limit
            if xs[end] == goal
                println(xs)
            end
        else
            for p in adjacent[xs[end]]
                if p in xs; continue; end
                push!(xs, p)
                dfs(xs, limit)
                pop!(xs)
            end
        end
    end

    for limit in 1 : length(adjacent)
      @printf "----- %d -----\n" limit
      dfs([1], limit)
    end
end

println("----- dfs -----")
dfs(6, [1])
println("----- bfs -----")
bfs(1, 6)
println("----- ids -----")
ids(1, 6)
C>julia keiro.jl
----- dfs -----
[1,2,3,5,4,6]
[1,2,4,6]
[1,3,2,4,6]
[1,3,5,4,6]
----- bfs -----
[1,2,4,6]
[1,3,2,4,6]
[1,3,5,4,6]
[1,2,3,5,4,6]
----- ids -----
----- 1 -----
----- 2 -----
----- 3 -----
----- 4 -----
[1,2,4,6]
----- 5 -----
[1,3,2,4,6]
[1,3,5,4,6]
----- 6 -----
[1,2,3,5,4,6]
----- 7 -----

●ナンバープレース

リスト : ナンバープレースの解法

function check(board, x, y, n)
    # 縦横のチェック
    for i in 1 : 9
        if board[x, i] == n || board[i, y] == n
            return false
        end
    end
    # 枠のチェック
    x1 = div(x - 1, 3) * 3 + 1
    y1 = div(y - 1, 3) * 3 + 1
    for i in 0 : 2
        for j in 0 : 2
            if board[x1 + i, y1 + j] == n
                return false
            end
        end
    end
    true
end

function solver(board, x, y)
    if y == 10
        println(board)
    elseif x == 10
        solver(board, 1, y + 1)
    elseif board[x, y] != 0
        solver(board, x + 1, y)
    else
        for n in 1 : 9
            if !check(board, x, y, n); continue; end
            board[x, y] = n
            solver(board, x + 1, y)
            board[x, y] = 0
        end
    end
end

# 問題 (出典: 数独 - Wikipedia の問題例)
q00 = [
    5 3 0  0 7 0  0 0 0;
    6 0 0  1 9 5  0 0 0;
    0 9 8  0 0 0  0 6 0;

    8 0 0  0 6 0  0 0 3;
    4 0 0  8 0 3  0 0 1;
    7 0 0  0 2 0  0 0 6;

    0 6 0  0 0 0  2 8 0;
    0 0 0  4 1 9  0 0 5;
    0 0 0  0 8 0  0 7 9
]

println(q00)
println("--------")
@time solver(copy(q00), 1, 1)
println("--------")
C>julia numplace.jl
[5 3 0 0 7 0 0 0 0
 6 0 0 1 9 5 0 0 0
 0 9 8 0 0 0 0 6 0
 8 0 0 0 6 0 0 0 3
 4 0 0 8 0 3 0 0 1
 7 0 0 0 2 0 0 0 6
 0 6 0 0 0 0 2 8 0
 0 0 0 4 1 9 0 0 5
 0 0 0 0 8 0 0 7 9]
--------
[5 3 4 6 7 8 9 1 2
 6 7 2 1 9 5 3 4 8
 1 9 8 3 4 2 5 6 7
 8 5 9 7 6 1 4 2 3
 4 2 6 8 5 3 7 9 1
 7 1 3 9 2 4 8 5 6
 9 6 1 5 3 7 2 8 4
 2 8 7 4 1 9 6 3 5
 3 4 5 2 8 6 1 7 9]
  0.030107 seconds (13.09 k allocations: 395.136 KB)
--------

●小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。ただし、1 の前に - 符号はつけないものとします。

例:1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
リスト : 小町算

# 計算
function calc_expr(nums, ops)
    a = nums[1]
    i = 2
    for op in ops
        a += op == '+' ? nums[i] : -nums[i]
        i += 1
    end
    a
end

# 表示
function print_expr(nums, ops)
    print(nums[1])
    i = 2
    for op in ops
        print(op == '+' ? " + " : " - ")
        print(nums[i])
        i += 1
    end
    println(" = 100")
end

# 小町算の解法
function komachi(n, nums, ops)
    if n == 10
        if calc_expr(nums, ops) == 100
            print_expr(nums, ops)
        end
    else
        for op in ['+', '-']
            push!(ops, op)
            push!(nums, n)
            komachi(n + 1, nums, ops)
            pop!(nums)
            pop!(ops)
        end
        m = nums[end]
        nums[end] = m * 10 + n
        komachi(n + 1, nums, ops)
        nums[end] = m
    end
end

komachi(2, [1], [])
C>julia komachi.jl
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
123 + 4 - 5 + 67 - 89 = 100
123 + 45 - 67 + 8 - 9 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
123 - 45 - 67 + 89= 100

●素因数分解

Julia には素因数分解を行う関数 factor() が用意されているので、私たちがプログラムを作る必要はありませんが、Julia のお勉強ということで、あえてプログラムを作ってみましょう。

リスト : 素因数分解 (試し割り)

function factorSub(n, m)
    c = zero(n)
    while n % m == 0
        c += 1
        n = div(n, m)
    end
    c, n
end

function factorization(n)
    x::typeof(n) = 2
    xs = Pair{typeof(n), typeof(n)}[]
    c, m = factorSub(n, x)
    if c > 0
        push!(xs, x => c)
    end
    x = 3
    while x * x <= m
        c, m = factorSub(m, x)
        if c > 0
            push!(xs, x => c)
        end
        x += 2
    end
    if m > 1
        push!(xs, m => one(n))
    end
    xs
end

println(factorization(24))
println(factorization(12345678))
println(factorization(123456789))
println(factorization(1234567890))
println(factorization(1111111111))
for x in 2 : 31
    println(factorization(Int64(2) ^ x - 1))
end
C>julia factor.jl
[2=>3,3=>1]
[2=>1,3=>2,47=>1,14593=>1]
[3=>2,3607=>1,3803=>1]
[2=>1,3=>2,5=>1,3607=>1,3803=>1]
[11=>1,41=>1,271=>1,9091=>1]
[3=>1]
[7=>1]
[3=>1,5=>1]
[31=>1]
[3=>2,7=>1]
[127=>1]
[3=>1,5=>1,17=>1]
[7=>1,73=>1]
[3=>1,11=>1,31=>1]
[23=>1,89=>1]
[3=>2,5=>1,7=>1,13=>1]
[8191=>1]
[3=>1,43=>1,127=>1]
[7=>1,31=>1,151=>1]
[3=>1,5=>1,17=>1,257=>1]
[131071=>1]
[3=>3,7=>1,19=>1,73=>1]
[524287=>1]
[3=>1,5=>2,11=>1,31=>1,41=>1]
[7=>2,127=>1,337=>1]
[3=>1,23=>1,89=>1,683=>1]
[47=>1,178481=>1]
[3=>2,5=>1,7=>1,13=>1,17=>1,241=>1]
[31=>1,601=>1,1801=>1]
[3=>1,2731=>1,8191=>1]
[7=>1,73=>1,262657=>1]
[3=>1,5=>1,29=>1,43=>1,113=>1,127=>1]
[233=>1,1103=>1,2089=>1]
[3=>2,7=>1,11=>1,31=>1,151=>1,331=>1]
[2147483647=>1]

●連結リスト (mutable)

リスト : mutable な連結リスト


# 多重定義用
import Base: null, insert!, length, show, start, next, done 

# 抽象型
abstract List

# セル
type Cell <: List
    item
    next :: List
end

# 終端 
# メンバ変数の無いデータ型を生成すると
# シングルトンオブジェクトを返す
type Nil <: List
end

nil = Nil()

# アクセス関数
car(xs::Cell) = xs.item
cdr(xs::Cell) = xs.next
set_car!(xs::Cell, x) = xs.item = x
set_cdr!(xs::Cell, cp::List) = xs.next = cp
null(xs::List) = xs == nil

# 連結リスト
type LinkedList
    top :: List
    LinkedList() = new(Cell(nil, nil))
end

# 作業用
function nth_cell(xs::List, n::Int)
    i = -1
    while !null(xs)
        if i == n; break; end
        i += 1
        xs = cdr(xs)
    end
    xs
end

# 参照
function nth(xs::LinkedList, n::Int)
    cp = nth_cell(xs.top, n)
    if null(cp) 
        error("nth: out of range")
    else
        car(cp)
    end
end

# 更新
function set!(xs::LinkedList, n::Int, x)
    cp = nth_cell(xs.top, n)
    if null(cp)
        error("set!: out of range")
    else
        set_car!(cp, x)
    end
end

# 挿入
function insert!(xs::LinkedList, n::Int, x)
    cp = nth_cell(xs.top, n - 1)
    if null(cp)
        error("insert!: out of range")
    else
        set_cdr!(cp, Cell(x, cdr(cp)))
    end
end

# 削除
function remove!(xs::LinkedList, n::Int)
    cp = nth_cell(xs.top, n - 1)
    if null(cp) || null(cdr(cp))
        error("remove!: out of range")
    else
        set_cdr!(cp, cdr(cdr(cp)))
    end
end

# 長さ
function length(xs::LinkedList)
    n = 0
    cp = cdr(xs.top)
    while !null(cp)
        n += 1
        cp = cdr(cp)
    end
    n
end

# 巡回
function foreach(func::Function, xs::LinkedList)
    cp = cdr(xs.top)
    while !null(cp)
        func(car(cp))
        cp = cdr(cp)
    end
end

# イテレータ
start(xs::LinkedList) = cdr(xs.top)
next(::LinkedList, state) = (car(state), cdr(state))
done(::LinkedList, state) = null(state)

# 表示
function show(io::IO, xs::LinkedList)
    print(io, "(")
    cp = cdr(xs.top)
    while !null(cp)
        print(car(cp))
        cp = cdr(cp)
        if !null(cp); print(" "); end
    end
    print(")")
end

# テスト
xs = LinkedList()
for x in 1 : 10
    insert!(xs, 0, x)
end
println(xs)
ys = LinkedList()
for x in 0 : 9
    insert!(ys, x, x)
end
foreach(x -> (@printf "%d " x), ys)
println("")
for x in 0 : 9
    set!(xs, x, nth(xs, x) * 2)
end
println(xs)
println(length(xs))
remove!(xs, 0)
println(xs)
println(length(xs))
remove!(xs, 8)
println(xs)
println(length(xs))
remove!(xs, 3)
println(xs)
println(length(xs))

ys = LinkedList()
for x in 1 : 10
    insert!(ys, 0, x)
end

# イテレータ
for x in ys
    print(x); print(" ")
end
C>julia mlist.jl
(10 9 8 7 6 5 4 3 2 1)
0 1 2 3 4 5 6 7 8 9
(20 18 16 14 12 10 8 6 4 2)
10
(18 16 14 12 10 8 6 4 2)
9
(18 16 14 12 10 8 6 4)
8
(18 16 14 10 8 6 4)
7
10 9 8 7 6 5 4 3 2 1

●連結リスト (immutable)

バージョンアップしました。

リスト : immutable な Lisp 風の連結リスト

# 多重定義用
import Base: show, length, map, filter, foldl, foldr, reverse, null
import Base: start, next, done

# 抽象型
abstract List

# 終端
type Null <: List
end

# シングルトンオブジェクト
nil = Null()

# セル
immutable Cons <: List
    car
    cdr::List
end

# 型述語
null(xs) = xs == nil
listp(xs) = isa(xs, List)
consp(xs) = isa(xs, Cons)
eq(xs, ys) = is(xs, ys)

function equal(xs, ys)
    if eq(xs, ys)
        true
    elseif consp(xs) && consp(ys)
        equal(car(xs), car(ys)) && equal(cdr(xs), cdr(ys))
    elseif !listp(xs) && !listp(ys)
        xs == ys
    else
        false
    end
end

# 表示
function printList(io::IO, xs::List)
    print(io, "(")
    while !null(xs)
        x = car(xs)
        if consp(x)
            printList(io, x)
        elseif null(x)
            print(io, "()")
        else
            print(io, x)
        end
        xs = cdr(xs)
        if !null(xs); print(io, " "); end
    end
    print(io, ")")
end

show(io::IO, xs::List) = printList(io, xs)

# 基本的なリスト操作
car(xs::Cons) = xs.car
car(xs::Null) = nil
cdr(xs::Cons) = xs.cdr
cdr(xs::Null) = nil
cons(x, xs::List) = Cons(x, xs)

# 参照
function nth(xs::List, n::Int)
    while !null(xs)
        if n == 0; return car(xs); end
        xs = cdr(xs)
        n -= 1
    end
    error("nth: out of range")
end

# リストの生成
function list(xs...)
   ys = nil
   for x in xs
       ys = cons(x, ys)
   end
   reverse(ys)
end

# 連結
function append(xs::List, ys::List)
    if null(xs)
        ys
    else
        cons(car(xs), append(cdr(xs), ys))
    end
end

# 逆順
function reverse(xs::List)
    ys = nil
    while !null(xs)
        ys = cons(car(xs), ys)
        xs = cdr(xs)
    end
    ys
end

# 長さ
function length(xs::List)
    c = 0
    while !null(xs)
        c += 1
        xs = cdr(xs)
    end
    c
end

# 高階関数

# マッピング
function map(func::Function, xs::List)
    if null(xs)
        nil
    else
        cons(func(car(xs)), map(func, cdr(xs)))
    end
end

# フィルター
function filter(func::Function, xs::List)
    if null(xs)
        nil
    elseif func(car(xs))
        cons(car(xs), filter(func, cdr(xs)))
    else
        filter(func, cdr(xs))
    end
end

# 畳み込み
function foldl(func::Function, a, xs::List)
    if null(xs)
        a
    else
        foldl(func, func(a, car(xs)), cdr(xs))
    end
end

function foldr(func::Function, a, xs::List)
    if null(xs)
        a
    else
        func(car(xs), foldr(func, a, cdr(xs)))
    end
end

# 巡回
function foreach(func::Function, xs::List)
    while !null(xs)
        func(car(xs))
        xs = cdr(xs)
    end
end

# イテレータ
start(xs::List) = xs
next(::List, state) = (car(state), cdr(state))
done(::List, state) = null(state)

# 簡単なテスト
a = list(1,2,3,4,5,6,7,8)
println(a)
println(length(a))
for i in 0 : 7
    println(nth(a, i))
end
println(reverse(a))
println(append(a, a))
println(map(x -> x * x, a))
println(filter(x -> x % 2 == 0, a))
println(foldl(+, 0, a))
println(foldl((x, y) -> cons(y, x), nil, a))
println(foldr(+, 0, a))
println(foldr(cons, nil, a))
foreach(println, a)

# イテレータ
for x in a
    print(x), print(" ")
end
C>julia imlist.jl
(1 2 3 4 5 6 7 8)
8
1
2
3
4
5
6
7
8
(8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8)
(1 4 9 16 25 36 49 64)
(2 4 6 8)
36
(8 7 6 5 4 3 2 1)
36
(1 2 3 4 5 6 7 8)
1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8

●二分探索木

リスト : 二分探索木

# 多重定義用
import Base: start, next, done

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

# 節
type Node{T}
    item::T
    left::Union{Node{T}, Void}
    right::Union{Node{T}, Void}
end

# 型に別名を付ける
typealias Tree{T} Union{Node{T}, Void}

# 二分木
type Tree2{T}
    root::Tree{T}
    Tree2() = new(nothing)
end

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

# 探索
function search_node{T}(x::T, node::Tree{T})
    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{T}(node::Tree{T})
    while node.left !== nothing
        node = node.left
    end
    node.item
end

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

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

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

# 削除
function delete_node{T}(x::T, node::Tree{T})
    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(x, node.left)
    else
        node.right = delete_node(x, node.right)
    end
    node
end

# 巡回
function foreach_node(func::Function, node::Void)
end
function foreach_node{T}(func::Function, node::Node{T})
    foreach_node(func, node.left)
    func(node.item)
    foreach_node(func, node.right)
end

# イテレータ (CPS 形式)
function iter(node::Void, cont)
    cont()
end
function iter{T}(node::Node{T}, cont)
    iter(node.left, () -> (node.item, () -> iter(node.right, () -> cont())))
end

# 公開するメソッド
# 挿入
function insert_tree{T}(x::T, tree::Tree2{T})
    tree.root = insert_node(x, tree.root)
end

# 探索
function search_tree{T}(x::T, tree::Tree2{T})
    search_node(x, tree.root)
end

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

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

# 削除
function delete_tree{T}(x::T, tree::Tree2{T})
    tree.root = delete_node(x, tree.root)
end

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

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

# 巡回
function foreach_tree{T}(func::Function, tree::Tree2{T})
    foreach_node(func, tree.root)
end

function print_tree{T}(tree::Tree2{T})
  foreach_tree(x -> (print(x); print(" ")), tree)
  println("")
end

# イテレータ
start{T}(tree::Tree2{T}) = iter(tree.root, () -> nothing)
next{T}(::Tree2{T}, state) = (state[1], state[2]())
done{T}(::Tree2{T}, state) = state === nothing

# 簡単なテスト
a = Tree2{Int}()
for x in [5,3,7,1,4,2,9,6,8]
    insert_tree(x, a)
end

# イテレータ
for x in a
    print(x); print(" ")
end
println("")

for x in 0 : 10
    println(search_tree(x, a))
end
println(search_min(a))
println(search_max(a))
delete_max(a)
print_tree(a)
delete_min(a)
print_tree(a)
for x in 1 : 9
    delete_tree(x, a)
    print_tree(a)
end
C>julia tree.jl
1 2 3 4 5 6 7 8 9
false
true
true
true
true
true
true
true
true
true
false
1
9
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8
2 3 4 5 6 7 8
3 4 5 6 7 8
4 5 6 7 8
5 6 7 8
6 7 8
7 8
8



Copyright (C) 2016 Makoto Hiroi
All rights reserved.

[ Home | Light | Julia ]