M.Hiroi's Home Page

Julia Language Programming

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


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

Julia の基礎知識

●配列の操作

julia> a = [1 2 3; 4 5 6]
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

julia> eltype(a)
Int64

julia> ndims(a)
2

julia> size(a)
(2, 3)

julia> size(a, 1)
2

julia> size(a, 2)
3

julia> b = copy(a)
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

julia> b[1, 1] = 10
10

julia> a
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

julia> b
2×3 Matrix{Int64}:
 10  2  3
  4  5  6

julia> Vector{Int}(undef, 5)
5-element Vector{Int64}:
 0
 0
 0
 0
 0

julia> Matrix{Int}(undef, 3, 4)
3×4 Matrix{Int64}:
 0  0  0  0
 0  0  0  0
 0  0  0  0

julia> Matrix{Float64}(undef, 3, 4)
3×4 Matrix{Float64}:
 0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0

julia> using LinearAlgebra

julia> Matrix{Float64}(I, 4, 4)
4×4 Matrix{Float64}:
 1.0  0.0  0.0  0.0
 0.0  1.0  0.0  0.0
 0.0  0.0  1.0  0.0
 0.0  0.0  0.0  1.0

julia> rand(3, 3)
3×3 Matrix{Float64}:
 0.656057  0.13851   0.624263
 0.918642  0.923451  0.218356
 0.138388  0.717213  0.786006

julia> randn(3, 3)
3×3 Matrix{Float64}:
 -1.54448   -0.133406   1.29957
 -1.85525   -0.591922  -0.70398
  0.422188   0.315499   0.811839

julia> fill(10, 2, 3)
2×3 Matrix{Int64}:
 10  10  10
 10  10  10

julia> fill!(b, 100)
2×3 Matrix{Int64}:
 100  100  100
 100  100  100

julia> b
2×3 Matrix{Int64}:
 100  100  100
 100  100  100

julia> reshape(b, 3, 2)
3×2 Matrix{Int64}:
 100  100
 100  100
 100  100

julia> reshape(b, 1, 6)
1×6 Matrix{Int64}:
 100  100  100  100  100  100

julia> reshape(b, 6, 1)
6×1 Matrix{Int64}:
 100
 100
 100
 100
 100
 100

julia> reshape(collect(1:16), 4, 4)
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7  11  15
 4  8  12  16

julia> a = [11 12 13 14; 15 16 17 18; 19 20 21 22]
3×4 Matrix{Int64}:
 11  12  13  14
 15  16  17  18
 19  20  21  22

julia> stride(a, 1)
1

julia> stride(a, 2)
3

julia> strides(a)
(1, 3)

julia> a[1]
11

julia> a[2]
15

julia> a[3]
19

julia> a[12]
22

julia> a[11]
18

julia> a[10]
14

julia> for x = eachindex(a)
       print(x, " ")
       end
1 2 3 4 5 6 7 8 9 10 11 12

julia> a = collect(1 : 8)
8-element Vector{Int64}:
 1
 2
 3
 4
 5
 6
 7
 8

julia> a[3 : 5]
3-element Vector{Int64}:
 3
 4
 5

julia> a[1 : 2 : end]
4-element Vector{Int64}:
 1
 3
 5
 7

julia> a[end : -1 : 1]
8-element Vector{Int64}:
 8
 7
 6
 5
 4
 3
 2
 1

julia> b = a[:]
8-element Vector{Int64}:
 1
 2
 3
 4
 5
 6
 7
 8

julia> b[1] = 10
10

julia> b[2 : 4] = [11, 12, 13]
3-element Vector{Int64}:
 11
 12
 13

julia> b
8-element Vector{Int64}:
 10
 11
 12
 13
  5
  6
  7
  8

julia> a
8-element Vector{Int64}:
 1
 2
 3
 4
 5
 6
 7
 8

julia> b[[3, 2, 1]]
3-element Vector{Int64}:
 12
 11
 10

julia> c = reshape(collect(1 : 16), 4, 4)
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7  11  15
 4  8  12  16

julia> c[1 : 3, 2 : 4]
3×3 Matrix{Int64}:
 5   9  13
 6  10  14
 7  11  15

julia> c[[1, 3], [3, 2, 1]]
2×3 Matrix{Int64}:
  9  5  1
 11  7  3

julia> c[[1, 3], 4]
2-element Vector{Int64}:
 13
 15

julia> c[2, [1, 3]]
2-element Vector{Int64}:
  2
 10

julia> c[1 : 2, 1 : 2] = [100 200; 300 400]
2×2 Matrix{Int64}:
 100  200
 300  400

julia> c
4×4 Matrix{Int64}:
 100  200   9  13
 300  400  10  14
   3    7  11  15
   4    8  12  16

julia> a = collect(11 : 18)
8-element Vector{Int64}:
 11
 12
 13
 14
 15
 16
 17
 18

julia> a[[1 3; 5 6]]
2×2 Matrix{Int64}:
 11  13
 15  16

julia> a[[1 2; 3 4]] = [1 2; 3 4]
2×2 Matrix{Int64}:
 1  2
 3  4

julia> a
8-element Vector{Int64}:
  1
  2
  3
  4
 15
 16
 17
 18

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

julia> a
8-element Vector{Int64}:
  1
  3
  2
  4
 15
 16
 17
 18

julia> b = reshape(collect(11:37), 3, 3, 3)
3×3×3 Array{Int64, 3}:
[:, :, 1] =
 11  14  17
 12  15  18
 13  16  19

[:, :, 2] =
 20  23  26
 21  24  27
 22  25  28

[:, :, 3] =
 29  32  35
 30  33  36
 31  34  37

julia> c = reshape(collect(1:8), 2, 2, 2)
2×2×2 Array{Int64, 3}:
[:, :, 1] =
 1  3
 2  4

[:, :, 2] =
 5  7
 6  8

julia> b[c]
2×2×2 Array{Int64, 3}:
[:, :, 1] =
 11  13
 12  14

[:, :, 2] =
 15  17
 16  18

julia> b[[1 2; 3 4]]
2×2 Matrix{Int64}:
 11  12
 13  14

julia> d = rand(3, 3)
3×3 Matrix{Float64}:
 0.501875  0.775976  0.344637
 0.360713  0.184347  0.59974
 0.924875  0.371442  0.251967

julia> d[[true, false, true], :]
2×3 Matrix{Float64}:
 0.501875  0.775976  0.344637
 0.924875  0.371442  0.251967

julia> d[[true false true; false true false; true false true]]
5-element Vector{Float64}:
 0.5018752512220828
 0.9248752675744198
 0.1843468573998286
 0.34463739835964713
 0.25196665765465065

julia> a = [1 2 3; 4 5 6]
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

julia> b = [11 12 13; 14 15 16]
2×3 Matrix{Int64}:
 11  12  13
 14  15  16

julia> cat(a, b, dims=1)
4×3 Matrix{Int64}:
  1   2   3
  4   5   6
 11  12  13
 14  15  16

julia> cat(a, b, dims=2)
2×6 Matrix{Int64}:
 1  2  3  11  12  13
 4  5  6  14  15  16

julia> vcat(a, b)
4×3 Matrix{Int64}:
  1   2   3
  4   5   6
 11  12  13
 14  15  16

julia> hcat(a, b)
2×6 Matrix{Int64}:
 1  2  3  11  12  13
 4  5  6  14  15  16

julia> hvcat((2, 2), 1, 2, 3, 4)
2×2 Matrix{Int64}:
 1  2
 3  4

julia> hvcat((2, 2, 2), 1, 2, 3, 4, 5, 6)
3×2 Matrix{Int64}:
 1  2
 3  4
 5  6

julia> hvcat((3, 3), 1, 2, 3, 4, 5, 6)
2×3 Matrix{Int64}:
 1  2  3
 4  5  6

julia> c = reshape(1:8, 2,2,2)
2×2×2 reshape(::UnitRange{Int64}, 2, 2, 2) with eltype Int64:
[:, :, 1] =
 1  3
 2  4

[:, :, 2] =
 5  7
 6  8

julia> d = reshape(11:18, 2,2,2)
2×2×2 reshape(::UnitRange{Int64}, 2, 2, 2) with eltype Int64:
[:, :, 1] =
 11  13
 12  14

[:, :, 2] =
 15  17
 16  18

julia> cat(c, d, dims=1)
4×2×2 Array{Int64, 3}:
[:, :, 1] =
  1   3
  2   4
 11  13
 12  14

[:, :, 2] =
  5   7
  6   8
 15  17
 16  18

julia> cat(c, d, dims=2)
2×4×2 Array{Int64, 3}:
[:, :, 1] =
 1  3  11  13
 2  4  12  14

[:, :, 2] =
 5  7  15  17
 6  8  16  18

julia> cat(c, d, dims=3)
2×2×4 Array{Int64, 3}:
[:, :, 1] =
 1  3
 2  4

[:, :, 2] =
 5  7
 6  8

[:, :, 3] =
 11  13
 12  14

[:, :, 4] =
 15  17
 16  18

●ビュー (View)

julia> a = reshape(collect(1 : 16), 4, 4)
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7  11  15
 4  8  12  16

julia> b = view(a, :, 1)
4-element view(::Matrix{Int64}, :, 1) with eltype Int64:
 1
 2
 3
 4

julia> b[1]
1

julia> b[4]
4

julia> b[4] *= 10
40

julia> b
4-element view(::Matrix{Int64}, :, 1) with eltype Int64:
  1
  2
  3
 40

julia> a
4×4 Matrix{Int64}:
  1  5   9  13
  2  6  10  14
  3  7  11  15
 40  8  12  16

julia> c = @view a[4, :]
4-element view(::Matrix{Int64}, 4, :) with eltype Int64:
 40
  8
 12
 16

julia> fill!(c, 0)
4-element view(::Matrix{Int64}, 4, :) with eltype Int64:
 0
 0
 0
 0

julia> a
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7  11  15
 0  0   0   0


julia> d = @view a[3:end, 3:end]
2×2 view(::Matrix{Int64}, 3:4, 3:4) with eltype Int64:
 11  15
  0   0

julia> d[:,:] = [1 2; 3 4]
2×2 Matrix{Int64}:
 1  2
 3  4

julia> a
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7   1   2
 0  0   3   4

julia> parent(b)
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7   1   2
 0  0   3   4

julia> parentindices(b)
(Base.Slice(Base.OneTo(4)), 1)

julia> @view a[parentindices(b)...]
4-element view(::Matrix{Int64}, :, 1) with eltype Int64:
 1
 2
 3
 0

julia> parent(c)
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7   1   2
 0  0   3   4

julia> parentindices(c)
(4, Base.Slice(Base.OneTo(4)))

julia> @view a[parentindices(c)...]
4-element view(::Matrix{Int64}, 4, :) with eltype Int64:
 0
 0
 3
 4

julia> parent(d)
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7   1   2
 0  0   3   4

julia> parentindices(d)
(3:4, 3:4)

julia> @view a[parentindices(d)...]
2×2 view(::Matrix{Int64}, 3:4, 3:4) with eltype Int64:
 1  2
 3  4

●配列の演算

julia> a = rand(3, 3)
3×3 Matrix{Float64}:
 0.774048   0.174833  0.533835
 0.527699   0.28474   0.712182
 0.0534123  0.160258  0.237476

julia> b = rand(3, 3)
3×3 Matrix{Float64}:
 0.0766265  0.595025   0.365214
 0.887855   0.233891   0.899877
 0.190746   0.0984789  0.438805

julia> a .+ b
3×3 Matrix{Float64}:
 0.850675  0.769858  0.899048
 1.41555   0.518631  1.61206
 0.244159  0.258737  0.676281

julia> a .- b
3×3 Matrix{Float64}:
  0.697422  -0.420193    0.168621
 -0.360156   0.0508489  -0.187695
 -0.137334   0.0617789  -0.201329

julia> a .* b
3×3 Matrix{Float64}:
 0.0593126  0.10403    0.194964
 0.46852    0.0665981  0.640876
 0.0101882  0.015782   0.104205

julia> a ./ b
3×3 Matrix{Float64}:
 10.1016    0.293824  1.46171
  0.594353  1.2174    0.791421
  0.280017  1.62733   0.541188

julia> a .+ 10
3×3 Matrix{Float64}:
 10.774   10.1748  10.5338
 10.5277  10.2847  10.7122
 10.0534  10.1603  10.2375

julia> a .* 10
3×3 Matrix{Float64}:
 7.74048   1.74833  5.33835
 5.27699   2.8474   7.12182
 0.534123  1.60258  2.37476

julia> a .- 10
3×3 Matrix{Float64}:
 -9.22595  -9.82517  -9.46617
 -9.4723   -9.71526  -9.28782
 -9.94659  -9.83974  -9.76252

julia> a ./ 10
3×3 Matrix{Float64}:
 0.0774048   0.0174833  0.0533835
 0.0527699   0.028474   0.0712182
 0.00534123  0.0160258  0.0237476

julia> sin.(a)
3×3 Matrix{Float64}:
 0.699036   0.173944  0.508838
 0.503546   0.280908  0.653487
 0.0533869  0.159573  0.23525

julia> square(x) = x * x
square (generic function with 1 method)

julia> square.(a)
3×3 Matrix{Float64}:
 0.599151    0.0305665  0.284979
 0.278466    0.0810768  0.507203
 0.00285287  0.0256826  0.0563947

julia> a .^ 2
3×3 Matrix{Float64}:
 0.599151    0.0305665  0.284979
 0.278466    0.0810768  0.507203
 0.00285287  0.0256826  0.0563947

●基本的な線形代数

julia> a = [1 2; 3 4]
2×2 Matrix{Int64}:
 1  2
 3  4

julia> b = [5 6; 7 8]
2×2 Matrix{Int64}:
 5  6
 7  8

julia> c = a * b
2×2 Matrix{Int64}:
 19  22
 43  50

julia> inv(a)
2×2 Matrix{Float64}:
 -2.0   1.0
  1.5  -0.5

julia> a * inv(a)
2×2 Matrix{Float64}:
 1.0          0.0
 8.88178e-16  1.0

julia> inv(a) * c
2×2 Matrix{Float64}:
 5.0  6.0
 7.0  8.0

julia> a \ c
2×2 Matrix{Float64}:
 5.0  6.0
 7.0  8.0

julia> [1 1; 1 0] ^ 2
2×2 Matrix{Int64}:
 2  1
 1  1

julia> [1 1; 1 0] ^ 3
2×2 Matrix{Int64}:
 3  2
 2  1

julia> [1 1; 1 0] ^ 4
2×2 Matrix{Int64}:
 5  3
 3  2

julia> [1 1; 1 0] ^ 10
2×2 Matrix{Int64}:
 89  55
 55  34

julia> [1 1; 1 0] ^ 40
2×2 Matrix{Int64}:
 165580141  102334155
 102334155   63245986

julia> a'
2×2 adjoint(::Matrix{Int64}) with eltype Int64:
 1  3
 2  4

julia> transpose(a)
2×2 transpose(::Matrix{Int64}) with eltype Int64:
 1  3
 2  4

julia> [1 2 3; 4 5 6; 7 8 9]'
3×3 adjoint(::Matrix{Int64}) with eltype Int64:
 1  4  7
 2  5  8
 3  6  9

julia> transpose([1 2 3; 4 5 6; 7 8 9])
3×3 transpose(::Matrix{Int64}) with eltype Int64:
 1  4  7
 2  5  8
 3  6  9

julia> using LinearAlgebra

julia> a = [1 2 3; 4 5 6; 7 8 10]
3×3 Matrix{Int64}:
 1  2   3
 4  5   6
 7  8  10

julia> det(a)
-3.0

julia> tr(a)
16

julia> rank(a)
3

julia> diag(a)
3-element Vector{Int64}:
  1
  5
 10

julia> diag(a, 1)
2-element Vector{Int64}:
 2
 6

julia> diag(a, 2)
1-element Vector{Int64}:
 3

julia> diag(a, -1)
2-element Vector{Int64}:
 4
 8

julia> diag(a, -2)
1-element Vector{Int64}:
 7

julia> diagm(0 => [1, 2, 3])
3×3 Matrix{Int64}:
 1  0  0
 0  2  0
 0  0  3

julia> diagm(1 => [1, 2, 3])
4×4 Matrix{Int64}:
 0  1  0  0
 0  0  2  0
 0  0  0  3
 0  0  0  0

julia> diagm(-1 => [1, 2, 3])
4×4 Matrix{Int64}:
 0  0  0  0
 1  0  0  0
 0  2  0  0
 0  0  3  0

julia> diagm(0 => [1, 1, 1, 1], -1 => [1, 2, 3])
4×4 Matrix{Int64}:
 1  0  0  0
 1  1  0  0
 0  2  1  0
 0  0  3  1

julia> norm([1, 1])
1.4142135623730951

julia> norm([1, 1, 1])
1.7320508075688772

julia> dot([1, 2], [3, 4])
11

julia> dot([1, 2, 3], [4, 5, 6])
32

簡単なプログラム

●ソート

#
# sort.jl : ファイルのソート
#
#           Copyright 2016-2021 Makoto Hiroi
#

# 単純挿入ソート
function insert_sort!(buff::Vector{T}) where {T}
    for i = 2 : length(buff)
        temp = buff[i]
        j = i - 1
        while j > 0 && temp < buff[j]
            buff[j + 1] = buff[j]
            j -= 1
        end
        buff[j + 1] = temp
    end
end

# 中央値を返す
function median3(a, b, c)
    if a > b
        if b > c
            b
        elseif a < c
            a
        else
            c
        end
    else
        if b < c
            b
        elseif a < c
            c
        else
            a
        end
    end
end

# 9 つの中から中央値を選ぶ
function median9(buff, low, high)
    m2 = div(high - low, 2)
    m4 = div(m2, 2)
    m8 = div(m4, 2)
    a = buff[low]
    b = buff[low + m8]
    c = buff[low + m4]
    d = buff[low + m2 - m8]
    e = buff[low + m2]
    f = buff[low + m2 + m8]
    g = buff[high - m4]
    h = buff[high - m8]
    i = buff[high]
    median3(median3(a,b,c), median3(d,e,f), median3(g,h,i))
end

# クイックソート
function quick_sort!(buff::Vector{T}) where {T}
    function qsort(low::Int, high::Int)
        if high - low < 16
            return
        end
        pivot = median9(buff, low, high)
        i = low
        j = high
        while true
            while pivot > buff[i]; i += 1; end
            while pivot < buff[j]; j -= 1; end
            if i >= j; break; end
            buff[i], buff[j] = buff[j], buff[i]
            i += 1
            j -= 1
        end
        qsort(low, i - 1)
        qsort(j + 1, high)
    end
    #
    qsort(1, length(buff))
    insert_sort!(buff)
end

# ファイルのソート
function sort(fin)
    buff = readlines(fin)
    quick_sort!(buff)
    for x = buff
        println(x)
    end
end

if length(ARGS) == 0
    sort(stdin)
elseif length(ARGS) == 1
    open(ARGS[1], "r") do fin
        sort(fin)
    end
else
    println("usage: julia sort.jl [filename]")
end

●フィボナッチ数

フィボナッチ数 Fn の漸化式を行列で表すと次のようになります。 

F0 = 0
F1 = 1
[Fn Fn-1] = [1 1; 1 0] * [Fn-1 Fn-2]

したがって、Fn を求める問題は行列 [1 1; 1 0] の n 乗を求める問題に帰着します。xn は log2 n 程度の手間で求めることが可能です。Fn を繰り返しで求めると n に比例する時間がかかるので、n が大きくなると行列を使ったほうが速くなると思われます。 

リスト : フィボナッチ数

function fibo(n)
    if n == 0
        0
    elseif n == 1
        1
    else
        f = ([1 1; 1 0] ^ (n - 1)) * [1, 0]
        f[1]
    end
end

for x = 0 : 40
    print("$(fibo(x)) ")
end

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 
28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 
5702887 9227465 14930352 24157817 39088169 63245986 102334155

フィボナッチ数列の最初の 2 項を 2, 1 に置き換えた数列の項を「リュカ数 (Lucas number)」といいます。 

リスト : リュカ数

function lucas(n)
    if n == 0
        2
    elseif n == 1
        1
    else
        f = ([1 1; 1 0] ^ (n - 1)) * [1, 2]
        f[1]
    end
end

for x = 0 : 40
    print("$(lucas(x)) ")
end

2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 
39603 64079 103682 167761 271443 439204 710647 1149851 1860498 3010349 4870847 
7881196 12752043 20633239 33385282 54018521 87403803 141422324 228826127

次の漸化式で生成される数列をトリボナッチ数列といいます。 

T0 = T1 = 0, T2 = 1
Tn+3 = Tn+2 + Tn+1 + Tn

リスト : トリボナッチ数

function tribo(n)
    if n == 0 || n == 1
        0
    elseif n == 2
        1
    else
        t = ([1 1 1; 1 0 0; 0 1 0] ^ (n - 2)) * [1, 0, 0]
        t[1]
    end
end

for x = 0 : 30
    print("$(tribo(x)) ")
end

0 0 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012
 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591

次の漸化式で生成される数列をテトラナッチ数列といいます。 

T0 = T1 = T2 = 0, T3 = 1
Tn+4 = Tn+3 + Tn+2 + Tn+1 + Tn

リスト : テトラナッチ数列

function tetra(n)
    if n == 0 || n == 1 || n == 2
        0
    elseif n == 3
        1
    else
        t = ([1 1 1 1; 1 0 0 0 ; 0 1 0 0; 0 0 1 0] ^ (n - 3)) * [1, 0, 0, 0]
        t[1]
    end
end

for x = 0 : 30
    print("$(tetra(x)) ")
end

0 0 0 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424
147312 283953 547337 1055026 2033628 3919944 7555935 14564533 28074040

●連結リスト (mutable)

#
# list.jl : mutable な連結リスト
#
#           Copyright (C) 2016-2021 Makoto Hiroi
#

# 抽象型
abstract type List end

# セル
mutable struct Cell <: List
    item
    next :: List
end

# 終端 
# メンバ変数の無い immutable なデータ型を生成すると
# シングルトンオブジェクトを返す
struct 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

# 連結リスト
struct 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 Base.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 Base.delete!(xs::LinkedList, n::Int)
    cp = nth_cell(xs.top, n - 1)
    if null(cp) || null(cdr(cp))
        error("delete!: out of range")
    else
        set_cdr!(cp, cdr(cdr(cp)))
    end
end

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

# 空リストか？
function Base.isempty(xs::LinkedList)
    null(cdr(xs.top))
end

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

# イテレータ
function Base.iterate(xs::LinkedList, state = cdr(xs.top))
    if null(state)
        nothing
    else
       (car(state), cdr(state))
    end
end

# 表示
function Base.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()
println(isempty(xs))
for x = 1 : 10
    insert!(xs, 0, x)
end
println(xs)
println(isempty(xs))
ys = LinkedList()
for x = 0 : 9
    insert!(ys, x, x)
end
foreach(x -> print("$x "), ys)
println("")
for x = 0 : 9
    set!(xs, x, nth(xs, x) * 2)
end
println(xs)
println(length(xs))
delete!(xs, 0)
println(xs)
println(length(xs))
delete!(xs, 8)
println(xs)
println(length(xs))
delete!(xs, 3)
println(xs)
println(length(xs))
while !isempty(xs)
    delete!(xs, 0)
    println(xs)
    println(length(xs))
end
println(isempty(xs))

# イテレータ
for x = ys
    print("$x ")
end
println("")

$ julia list.jl
true
(10 9 8 7 6 5 4 3 2 1)
false
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
(16 14 10 8 6 4)
6
(14 10 8 6 4)
5
(10 8 6 4)
4
(8 6 4)
3
(6 4)
2
(4)
1
()
0
true
0 1 2 3 4 5 6 7 8 9

●双方向リスト

#
# dlist.jl : 双方向リスト (mutable)
#
#            Copyright (C) 2016-2021 Makoto Hiroi
#
import Base: first, last, push!, pop!, pushfirst!, popfirst!, isempty, length, show

# 双方向リスト (セル)
mutable struct Cell
    item
    prev::Cell
    next::Cell
    Cell(a) = (x = new(a); x.next = x; x.prev = x)
end

# 表示
function show(io::IO, head::Cell)
    xs = head.next
    print(io, "(")
    while xs !== head
        print(io, xs.item)
        xs = xs.next
        if xs !== head; print(io, " "); end
    end
    print(io, ")")
end

# 空か？
isempty(xs::Cell) = xs.next === xs

# 長さ
function length(head::Cell)
    c = 0
    xs = head.next
    while xs !== head
        c += 1
        xs = xs.next
    end
    c
end

# 参照
function first(head::Cell)
    if isempty(head)
        error("front: Empty DList")
    end
    head.next.item
end

function last(head::Cell)
    if isempty(head)
        error("back: Empty DList")
    end
    head.prev.item
end

# 先頭に挿入
function pushfirst!(xs::Cell, args...)
    for x = args
        ys = Cell(x)
        zs = xs.next
        ys.prev = xs
        ys.next = zs
        zs.prev = ys
        xs.next = ys
    end
    xs
end

# 先頭要素を取り出す
function popfirst!(xs::Cell)
    if isempty(xs)
        error("shift!: Empty DList")
    end
    ys = xs.next
    zs = ys.next
    xs.next = zs
    zs.prev = xs
    ys.item
end

# 末尾に挿入
function push!(xs::Cell, args...)
    for x = args
        ys = Cell(x)
        zs = xs.prev
        ys.next = xs
        ys.prev = zs
        xs.prev = ys
        zs.next = ys
    end
    xs
end

# 末尾要素を取り出す
function pop!(xs::Cell)
    if isempty(xs)
        error("shift!: Empty DList")
    end
    ys = xs.prev
    zs = ys.prev
    xs.prev = zs
    zs.next = xs
    ys.item
end

# スタック
mutable struct Stack
    top::Cell
    Stack() = new(Cell(nothing))
end

isempty(xs::Stack) = isempty(xs.top)
length(xs::Stack) = length(xs.top)
show(io::IO, xs::Stack) = show(io, xs.top)
first(xs::Stack) = last(xs.top)
push!(xs::Stack, args...) = push!(xs.top, args...)
pop!(xs::Stack) = pop!(xs.top)

# キュー
mutable struct Queue
    head::Cell
    Queue() = new(Cell(nothing))
end

isempty(xs::Queue) = isempty(xs.head)
length(xs::Queue) = length(xs.head)
show(io::IO, xs::Queue) = show(io, xs.head)
first(xs::Queue) = first(xs.head)
push!(xs::Queue, args...) = push!(xs.head, args...)
pop!(xs::Queue) = popfirst!(xs.head)

# ディーキュー
mutable struct Deque
    head::Cell
    Deque() = new(Cell(nothing))
end

isempty(xs::Deque) = isempty(xs.head)
length(xs::Deque) = length(xs.head)
show(io::IO, xs::Deque) = show(io, xs.head)
first(xs::Deque) = first(xs.head)
last(xs::Deque) = last(xs.head)
push!(xs::Deque, args...) = push!(xs.head, args...)
pop!(xs::Deque) = pop!(xs.head)
popfirst!(xs::Deque) = popfirst!(xs.head)
pushfirst!(xs::Deque, args...) = pushfirst!(xs.head, args...)

julia> include("dlist.jl")
pushfirst! (generic function with 10 methods)

julia> a = Stack()
()

julia> push!(a, 1, 2, 3, 4, 5)
(1 2 3 4 5)

julia> first(a)
5

julia> length(a)
5

julia> while !isempty(a); println(pop!(a)); end
5
4
3
2
1

julia> b = Queue()
()

julia> push!(b, 1, 2, 3, 4, 5)
(1 2 3 4 5)

julia> first(b)
1

julia> length(b)
5

julia> while !isempty(b); println(pop!(b)); end
1
2
3
4
5

julia> c = Deque()
()

julia> push!(c, 1, 2, 3, 4, 5)
(1 2 3 4 5)

julia> first(c)
1

julia> last(c)
5

julia> pushfirst!(c, 1, 2, 3, 4, 5)
(5 4 3 2 1 1 2 3 4 5)

julia> pop!(c)
5

julia> c
(5 4 3 2 1 1 2 3 4)

julia> popfirst!(c)
5

julia> c
(4 3 2 1 1 2 3 4)
初版 2018 年 10 月 20 日
改訂 2021 年 11 月 27 日