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

Julia Language Programming

連結リスト (immutable)

[ Home | Light | Julia ]

●連結リストの使い方

Lisp 風の immutable な連結リストのバージョンアップ版です。ファイル imlist2.jl をカレントディレクトリに置く場合、LOAD_PATH にカレントディレクトリを追加すれば、using imlist2 でプログラムをロードすることができます。


●プログラムリスト

#
# imlist2.jl : Lisp ライクで immutable な連結リスト (ver 0.2)
#
#              Copyright (C) 2016 Makoto Hiroi
#
module imlist2

export List, nil, null, listp, consp, atom, equal
export car, cdr, cons, nth, second, third, fourth, fifth
export list, make_list, tabulate, iota, tolist, append, remove
export flatten, foreach, member, acons, assoc, pairlis, subst
export substitute, merge_sort, remove_duplicate, difference

# 多重定義用
import Base: show, null, first, last, reverse, length, map, filter, foldr
import Base: start, next, done, getindex, take, drop, find, position
import Base: merge, issubset, union, intersect

# リストの定義
abstract List

# 空リスト
immutable Nil <: List
end

const nil = Nil()

# コンスセル
immutable Cons <: List
    car
    cdr
end

# 基本関数
car(xs::Cons) = xs.car
cdr(xs::Cons) = xs.cdr
cons(x, y) = Cons(x, y)

# 述語
null(xs)   = xs === nil
atom(xs)   = typeof(xs) != Cons
consp(xs)  = typeof(xs) == Cons
listp(xs)  = null(xs) || consp(xs)

# 等値の判定
function equal(xs, ys)
    if xs == ys
        true
    elseif consp(xs) && consp(ys)
        equal(car(xs), car(ys)) && equal(cdr(xs), cdr(ys))
    else
        false
    end
end

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

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

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

# 参照は O(N) なので getindex() と endof() は実装しない
function nth(xs::List, n::Int)
    i = n
    ys = xs
    while consp(ys) && i > 1
        ys = cdr(ys)
        i -= 1
    end
    if consp(ys)
        car(ys)
    else
        throw(BoundsError(xs, n))
    end
end

first(xs::Cons)  = xs.car
second(xs::Cons) = xs.cdr.car
third(xs::Cons)  = xs.cdr.cdr.car
fourth(xs::Cons) = xs.cdr.cdr.cdr.car
fifth(xs::Cons)  = xs.cdr.cdr.cdr.cdr.car

# 末尾の要素 (O(N) なので遅い)
function last(xs::Cons)
    while !null(cdr(xs)); xs = cdr(xs); end
    car(xs)
end

# リストの生成
function list(args...)
    xs = nil
    for i in length(args) : -1 : 1
        xs = cons(args[i], xs)
    end
    xs
end

function make_list(n::Int, x)
    xs = nil
    for _ in 1 : n; xs = cons(x, xs); end
    xs
end

tabulate(f::Function, x::Range) = list(map(f, collect(x))...)

iota(x::Range) = list(collect(x)...)

tolist(xs) = list(xs...)

# リストの連結
function append(xs::List...)
    function append1(xs::List, ys::List)
        if atom(xs)
            ys
        else
            cons(car(xs), append(cdr(xs), ys))
        end
    end
    n = length(xs)
    if n == 0
        nil
    elseif n == 1
        xs[1]
    else
        # 後ろからつなげていく
        ys = xs[n]
        for i in n - 1 : -1 : 1
            ys = append1(xs[i], ys)
        end
        ys
    end
end

# リストの反転
function reverse(xs::List)
    ys = nil
    for x in xs; ys = cons(x, ys); end
    ys
end

# リストの長さ
function length(xs::List)
    c = 0
    while consp(xs)
        c += 1
        xs = cdr(xs)
    end
    c
end

# 先頭から n 個の要素を取り出す
# Julia の take(iter, n) はイテレータを返す
function take(xs::List, n::Int)
    if atom(xs) || n == 0
        nil
    else
        cons(car(xs), take(cdr(xs), n - 1))
    end
end

# 先頭から n 個の要素を取り除く
# Julia の drop(iter, n) はイテレータを返す
function drop(xs::List, n::Int)
    while consp(xs) && n > 0
        xs = cdr(xs)
        n -= 1
    end
    xs
end

# リストの平坦化
function flatten(xs::List)
    function flat(xs, a::List)
        if null(xs)
            a
        elseif atom(xs)
            cons(xs, a)
        else
            flat(car(xs), flat(cdr(xs), a))
        end
    end
    flat(xs, nil)
end

# マッピング
function map(f::Function, xs::List...)
    if any(atom, xs)
        nil
    else
        args = map(car, xs)
        xs1  = map(cdr, xs)
        cons(f(args...), map(f, xs1...))
    end
end

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

function remove(f::Function, xs::List)
    if atom(xs)
        nil
    elseif !f(car(xs))
        cons(car(xs), remove(f, cdr(xs)))
    else
        remove(f, cdr(xs))
    end
end

function remove(x, xs::List)
    if atom(xs)
        nil
    elseif car(xs) != x
        cons(car(xs), remove(x, cdr(xs)))
    else
        remove(x, cdr(xs))
    end
end

# 畳み込み
# foldl は julia の foldl(op, v, iter) で OK
# foldr は endof() が必要なので自前で実装
function foldr(f::Function, a, xs::List)
    if atom(xs)
        a
    else
        f(car(xs), foldr(f, a, cdr(xs)))
    end
end

# 巡回
function foreach(f::Function, xs::List)
    for x in xs; f(x); end
end

# リストの探索
function member(f::Function, xs::List)
    while consp(xs)
        if f(car(xs)); break; end
        xs = cdr(xs)
    end
    xs
end

function member(y, xs::List)
    while consp(xs)
        if car(xs) == y; break; end
        xs = cdr(xs)
    end
    xs
end

function find(f::Function, xs::List)
    for x in xs
        if f(x); return x; end
    end
    false
end

function find(y, xs::List)
    for x in xs
        if x == y; return true; end
    end
    false
end

function position(f::Function, xs::List)
    for (n, x) in enumerate(xs)
        if f(x); return n; end
    end
    0
end

function position(y, xs::List)
    for (n, x) in enumerate(xs)
        if x == y; return n; end
    end
    0
end

# リストの置換
function substitute(f::Function, y, xs::List)
    if atom(xs)
        nil
    else
        x = car(xs)
        cons(f(x) ? y : x, substitute(f, y, cdr(xs)))
    end
end

# 木の置換
function subst(f::Function, y, xs)
    if f(xs)
        y
    elseif atom(xs)
        xs
    else
        cons(subst(f, y, car(xs)), subst(f, y, cdr(xs)))
    end
end

# リストのマージ
function merge(xs::List, ys::List, f = <=)
    if atom(xs)
        ys
    elseif atom(ys)
        xs
    else
        x = car(xs)
        y = car(ys)
        if f(x, y)
            cons(x, merge(cdr(xs), ys, f))
        else
            cons(y, merge(xs, cdr(ys), f))
        end
    end
end

# マージソート
function merge_sort(xs::List, f = <=)
    function sort(xs::List, n::Int)
        if n == 1
            list(car(xs))
        elseif n == 2
            x = car(xs)
            y = car(cdr(xs))
            f(x, y) ? list(x, y) : list(y, x)
        else
            m = div(n, 2)
            merge(sort(xs, m), sort(drop(xs, m), n - m), f)
        end
    end
    sort(xs, length(xs))
end

# 連想リスト
acons(key, val, alist::List) = cons(cons(key, val), alist)
assoc(key, xs::List) = find(xs -> equal(key, car(xs)), xs)

function pairlis(xs::List, ys::List, zs = nil)
    if null(xs) || null(ys)
        zs
    else
        cons(cons(car(xs), car(ys)), pairlis(cdr(xs), cdr(ys)))
    end
end

# 集合演算

# 重複要素の削除
function remove_duplicate(xs::List)
    ys = nil
    for x in xs
        if !find(x, ys)
            ys = cons(x, ys)
        end
    end
    reverse(ys)
end

# 和集合
function union(xs::List, ys::List)
    if atom(xs)
        ys
    elseif !find(car(xs), ys)
        cons(car(xs), union(cdr(xs), ys))
    else
        union(cdr(xs), ys)
    end
end

# 積集合
function intersect(xs::List, ys::List)
    if atom(xs)
        nil
    elseif find(car(xs), ys)
        cons(car(xs), intersect(cdr(xs), ys))
    else
        intersect(cdr(xs), ys)
    end
end

# 差集合
function difference(xs::List, ys::List)
    if atom(xs)
        nil
    elseif !find(car(xs), ys)
        cons(car(xs), difference(cdr(xs), ys))
    else
        difference(cdr(xs), ys)
    end
end

# 部分集合の判定
function issubset(xs::List, ys::List)
    if null(xs)
        true
    elseif !find(car(xs), ys)
        false
    else
        issubset(cdr(xs), ys)
    end
end

end

●リストで遊ぼう

  1. リストの要素がただひとつか調べる関数 singlep を定義してください。
  2. リストの要素が二つあるか調べる関数 doublep を定義してください。
  3. リスト xs はリスト ys よりも長いか調べる関数 longerp(xs, ys) を定義してください。
  4. リスト xs の最後尾から n 個の要素を取り除く関数 butlast(xs, n = 1) を定義してください。
  5. リスト xs を長さ n の部分リストに分割する関数 group(xs, n) を定義してください。
  6. リスト xs の要素を関数 f で二分割する関数 partition(f, xs) を定義してください。返り値は多値 (タプル) で返すものとします。
  7. リスト xs をクイックソートする関数 quick_sort(xs) を定義してください。
  8. リスト xs を木とみなして、x と等しい要素 (葉) を探す関数 member_tree(x, xs) を定義してください。
  9. リスト xs を木とみなして、要素 (葉) を数える関数 count_leaf(xs) を定義してください。
  10. リスト xs から n 個の要素を選ぶ順列を求める関数 permutations(n, xs) を定義してください。
  11. リスト xs から n 個の要素を選ぶ組み合わせを求める関数 combination(n, ls) を定義してください。
  12. リスト xs のべき集合を求める関数 power_set(xs) を定義してください。
  13. n 以下の素数をリストに格納して返す関数 prime_list(n) を定義してください。
  14. リストを使って N Queens Problem を解くプログラムを作ってください。
  15. リストを使ってマスターマインドを解くプログラムを作ってください。

●解答1

リスト : リストの要素はひとつか?

singlep(xs::List) = consp(xs) && null(cdr(xs))
julia> singlep(nil)
false
julia> singlep(list(1))
true
julia> singlep(list(1, 2))
false

●解答2

リスト : リストの要素はふたつか?

doublep(xs::List) = consp(xs) && singlep(cdr(xs))
julia> doublep(nil)
false
julia> doublep(list(1))
false
julia> doublep(list(1,2))
true
julia> doublep(list(1,2,3))
false

●解答3

リスト : リスト xs はリスト ys よりも長いか?

function longer(xs::List, ys::List)
    if null(xs)
        false
    elseif null(ys)
        true
    else
        longer(cdr(xs), cdr(ys))
    end
end

# 別解
function longer1(xs::List, ys::List)
    while consp(xs) && consp(ys)
        xs = cdr(xs)
        ys = cdr(ys)
    end
    null(ys)
end
julia> longer(list(1,2,3), list(1,2,3,4))
false
julia> longer(list(1,2,3,4), list(1,2,3))
true
julia> longer1(list(1,2,3), list(1,2,3,4))
false
julia> longer1(list(1,2,3,4), list(1,2,3))
true

●解答4

リスト : リストの末尾から n 個の要素を取り除く

butlast(xs::List, n::Int = 1) = reverse(drop(reverse(xs), n))

# 別解
butlast1(xs::List, n::Int = 1) = take(xs, length(xs) - n)
julia> butlast(list(1,2,3,4,5))
(1 2 3 4)
julia> butlast(list(1,2,3,4,5), 3)
(1 2)
julia> butlast(list(1,2,3,4,5), 5)
()

julia> butlast1(list(1,2,3,4,5))
(1 2 3 4)
julia> butlast1(list(1,2,3,4,5), 3)
(1 2)
julia> butlast1(list(1,2,3,4,5), 5)
()

●解答5

リスト : リストを長さ n の部分リストに分割する

function group(xs::List, n::Int)
    if null(xs)
        nil
    else
        cons(take(xs, n), group(drop(xs, n), n))
    end
end
julia> group(list(1,2,3,4,5,6), 2)
((1 2) (3 4) (5 6))
julia> group(list(1,2,3,4,5,6), 3)
((1 2 3) (4 5 6))
julia> group(list(1,2,3,4,5,6), 4)
((1 2 3 4) (5 6))

●解答6

リスト : リストの要素を関数 f を基準に二分割する

function partition(f::Function, xs::List)
    if null(xs)
        nil, nil
    else
        ys, zs = partition(f, cdr(xs))
        if f(car(xs))
            cons(car(xs), ys), zs
        else
            ys, cons(car(xs), zs)
        end
    end
end

# 別解
function partition1(f::Function, xs::List)
    ys = nil
    zs = nil
    for x in xs
        if f(x)
            ys = cons(x, ys)
        else
            zs = cons(x, zs)
        end
    end
    reverse(ys), reverse(zs)
end
julia> partition(x -> x % 2 == 0, iota(1:9))
((2 4 6 8),(1 3 5 7 9))
julia> partition(x -> x > 4, iota(1:9))
((5 6 7 8 9),(1 2 3 4))

julia> partition1(x -> x % 2 == 0, iota(1:9))
((2 4 6 8),(1 3 5 7 9))
julia> partition1(x -> x > 4, iota(1:9))
((5 6 7 8 9),(1 2 3 4))

●解答7

リスト : クイックソート

function quick_sort(xs::List)
    if null(xs)
        nil
    else
        ys, zs = partition(x -> x < car(xs), cdr(xs))
        append(quick_sort(ys), cons(car(xs), quick_sort(zs)))
    end
end
julia> quick_sort(list(5,6,4,7,3,8,2,9,1,0))
(0 1 2 3 4 5 6 7 8 9)
julia> quick_sort(list(0,1,2,3,4,5,6,7,8,9))
(0 1 2 3 4 5 6 7 8 9)
julia> quick_sort(list(9,8,7,6,5,4,3,2,1,0))
(0 1 2 3 4 5 6 7 8 9)

●解答8

リスト : 木の探索

function member_tree(x, xs::List)
    function iter(xs)
        if consp(xs)
            iter(car(xs)) || iter(cdr(xs))
        else
            xs == x
        end
    end
    iter(xs)
end
julia> xs = list(1, list(2, list(3, list(4, list(5), 6), 7), 8), 9)
(1 (2 (3 (4 (5) 6) 7) 8) 9)
julia> for x in 0:10; println(member_tree(x, xs)); end
false
true
true
true
true
true
true
true
true
true
false

●解答9

リスト : 葉の個数を数える

function count_leaf(xs::List)
    function iter(xs)
        if null(xs)
            0
        elseif consp(xs)
            iter(car(xs)) + iter(cdr(xs))
        else
            1
        end
    end
    iter(xs)
end
julia> xs
(1 (2 (3 (4 (5) 6) 7) 8) 9)
julia> count_leaf(xs)
9
julia> count_leaf(nil)
0
julia> count_leaf(iota(1:10))
10

●解答10

リスト : 順列の生成

# 高階関数版
function permutations(f::Function, xs::List, n::Int)
    function perm(xs, m, a)
        if n == m
            f(reverse(a))
        else
            for x in xs
                perm(remove(x, xs), m + 1, cons(x, a))
            end
        end
    end
    perm(xs, 0, nil)
end

# map の結果を平坦化する
flatmap(f, xs) = append(map(f, xs)...)

# 順列をリストに格納して返す
function permutations(xs::List, n::Int)
    if n == 0
        list(nil)
    else
        flatmap(xs) do x
            map(y -> cons(x, y), permutations(remove(x, xs), n - 1))
        end
    end
end
julia> permutations(println, iota(1:4), 3)
(1 2 3)
(1 2 4)
(1 3 2)
(1 3 4)
(1 4 2)
(1 4 3)
(2 1 3)
(2 1 4)
(2 3 1)
(2 3 4)
(2 4 1)
(2 4 3)
(3 1 2)
(3 1 4)
(3 2 1)
(3 2 4)
(3 4 1)
(3 4 2)
(4 1 2)
(4 1 3)
(4 2 1)
(4 2 3)
(4 3 1)
(4 3 2)

julia> permutations(iota(1:4), 3)
((1 2 3) (1 2 4) (1 3 2) (1 3 4) (1 4 2) (1 4 3) (2 1 3) (2 1 4) (2 3 1) (2 3 4)
 (2 4 1) (2 4 3) (3 1 2) (3 1 4) (3 2 1) (3 2 4) (3 4 1) (3 4 2) (4 1 2) (4 1 3)
 (4 2 1) (4 2 3) (4 3 1) (4 3 2))

●解答11

リスト : 組み合わせの生成

# 高階関数版
function combinations(f::Function, xs::List, n::Int)
    function comb(xs, m, a)
        if n == m
            f(reverse(a))
        elseif length(xs) == n - m
            f(append(reverse(a), xs))
        else
            comb(cdr(xs), m + 1, cons(car(xs), a))
            comb(cdr(xs), m, a)
        end
    end
    comb(xs, 0, nil)
end

# 組み合わせをリストに格納して返す
function combinations(xs::List, n::Int)
    if n == 0
        list(nil)
    elseif n == length(xs)
        list(xs)
    else
        append(map(x -> cons(car(xs), x), combinations(cdr(xs), n - 1)),
               combinations(cdr(xs), n))
    end
end
julia> combinations(println, iota(1:5), 3)
(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)

julia> combinations(iota(1:5), 3)
((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))

●解答12

リスト : べき集合の生成

# 高階関数版
function power_set(f::Function, xs::List)
    function power(xs::List, a::List)
        if null(xs)
            f(reverse(a))
        else
            power(cdr(xs), a)
            power(cdr(xs), cons(car(xs), a))
        end
    end
    power(xs, nil)
end

# 生成した集合をリストに格納して返す
function power_set(xs::List)
    if null(xs)
        list(nil)
    else
        append(power_set(cdr(xs)),
               map(ys -> cons(car(xs), ys), power_set(cdr(xs))))
    end
end
julia> power_set(println, iota(1:4))
()
(4)
(3)
(3 4)
(2)
(2 4)
(2 3)
(2 3 4)
(1)
(1 4)
(1 3)
(1 3 4)
(1 2)
(1 2 4)
(1 2 3)
(1 2 3 4)

julia> power_set(iota(1:4))
(() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4)
(1 2 3) (1 2 3 4))

●解答13

リスト : 素数を求める

function prime_list(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
julia> prime_list(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)

julia> prime_list(500)
(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)

●解答14

リスト : N Queens Problem (単純な生成検定法)

# 衝突の検出
function attack(q, board)
    for (i, x) in enumerate(board)
        if x == q - i || x == q + i
            return true
        end
    end
    false
end

# 安全か?
function issafe(board::List)
    while !singlep(board)
        if attack(car(board), cdr(board))
            return false
        end
        board = cdr(board)
    end
    true
end

# 盤面の表示
function print_board(board)
    for q in board
        for x in 1 : length(board)
            print(x == q ? "Q " : ". ")
        end
        println("")
    end
    println("")
end

function nqueens(n)
    cnt = 0
    permutations(iota(1:n), n) do board
        if issafe(board)
            print_board(board)
            cnt += 1
        end
    end
    println(cnt)
end
julia> nqueens(4)
. Q . .
. . . Q
Q . . .
. . Q .

. . Q .
Q . . .
. . . Q
. Q . .

2

julia> nqueens(6)
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

. . Q . . .
. . . . . Q
. Q . . . .
. . . . Q .
Q . . . . .
. . . Q . .

. . . Q . .
Q . . . . .
. . . . Q .
. Q . . . .
. . . . . Q
. . Q . . .

. . . . Q .
. . Q . . .
Q . . . . .
. . . . . Q
. . . Q . .
. Q . . . .

4

●解答15

リスト : マスターマインドの解法

# bulls を数える
count_bulls(xs, ys) = count(x -> x, map(==, xs, ys))

# 同じ数字を数える
count_same_number(xs, ys) = length(intersect(xs, ys))

# query の構造
# ((code bulls cows) ...)

# アクセス関数
get_code(qs)  = first(qs)
get_bulls(qs) = second(qs)
get_cows(qs)  = third(qs)

# 質問したコードと矛盾していないか
function check_query(query, code)
    all(query) do qs
        bulls = count_bulls(code, get_code(qs))
        cows = count_same_number(code, get_code(qs)) - bulls
        bulls == get_bulls(qs) && cows == get_cows(qs)
    end
end

# 解法
function mastermind(answer)
    query = nil
    try
        permutations(iota(0 : 9), 4) do code
            if check_query(query, code)
                bulls = count_bulls(answer, code)
                cows = count_same_number(answer, code) - bulls
                query = cons(list(code, bulls, cows), query)
                n = length(query)
                println("$n: $code, bulls = $bulls, cows = $cows")
                if bulls == 4
                    throw("Good Job!")
                end
            end
        end
    catch e
        println(e)
    end
end
julia> mastermind(list(9,8,7,6))
1: (0 1 2 3), bulls = 0, cows = 0
2: (4 5 6 7), bulls = 0, cows = 2
3: (5 4 8 9), bulls = 0, cows = 2
4: (6 7 9 8), bulls = 0, cows = 4
5: (8 9 7 6), bulls = 2, cows = 2
6: (9 8 7 6), bulls = 4, cows = 0
Good Job!

julia> mastermind(list(9,4,3,1))
1: (0 1 2 3), bulls = 0, cows = 2
2: (1 0 4 5), bulls = 0, cows = 2
3: (2 3 5 4), bulls = 0, cows = 2
4: (3 4 0 6), bulls = 1, cows = 1
5: (3 5 6 1), bulls = 1, cows = 1
6: (6 5 0 2), bulls = 0, cows = 0
7: (7 4 3 1), bulls = 3, cows = 0
8: (8 4 3 1), bulls = 3, cows = 0
9: (9 4 3 1), bulls = 4, cows = 0
Good Job!

Copyright (C) 2016 Makoto Hiroi
All rights reserved.

[ Home | Light | Julia ]