Lisp 風の immutable な連結リストです。再帰定義を多用しているため、長いリストを扱うとスタックオーバーフローする危険性があります。学習が目的のプログラムなので実用性はありませんが、興味のある方は試してみてください。
ファイル Imlist.jl がカレントディレクトリにある場合、次のコマンドを実行してください。
julia> include("Imlist.jl") julia> using .Imlist
これで連結リストを使用することができます。パッケージとして使用する場合は管理ツール pkg を使うと簡単です。
Imlist を使用するたびに activate するのは面倒な場合、LOAD_PATH に Imlist があるディレクトリのパスを追加します。Julia はホームディレクトリ (Windows 10 の場合は環境変数 HOMEPATH, UNIX 系 OS の場合は HOME) にディレクトリ .julia を作成します。ホームディレクトリのパスを ~ で表すと、Julia は起動するとファイル ~/.julia/config/startup.jl があれば、それを最初に読み込んで実行します。この中で ImList のパス を LOAD_PATH に追加すれば OK です。
julia> nil ()
julia> cons(1, 2) (1 . 2) julia> xs = cons(1, cons(2, cons(3, nil))) (1 2 3) julia> car(xs) 1 julia> cdr(xs) (2 3) julia> car(nil) () julia> cdr(nil) ()
julia> null(nil) true julia> null(cons(1, nil)) false julia> consp(nil) false julia> consp(cons(1, nil)) true julia> atom(1) true julia> atom(cons(1, nil)) false julia> atom(nil) true julia> listp(cons(1, nil)) true julia> listp(nil) true julia> listp(1) false julia> xs (1 2 3) julia> equal(xs, cons(1, cons(2, cons(3, nil)))) true julia> equal(xs, cons(1, cons(2, nil))) false julia> equal(xs, cons(1, cons(2, cons(4, nil)))) false
julia> list("foo", "bar", "baz") (foo bar baz) julia> makelist(10, 0) (0 0 0 0 0 0 0 0 0 0) julia> tabulate(x -> x * x, 1 : 10) (1 4 9 16 25 36 49 64 81 100) julia> iota(1 : 2 : 10) (1 3 5 7 9) julia> xs = [1, 2, 3, 4, 5] 5-element Vector{Int64}: 1 2 3 4 5 julia> tolist(xs) (1 2 3 4 5)
julia> xs = iota(0 : 9) (0 1 2 3 4 5 6 7 8 9) julia> first(xs) 0 julia> second(xs) 1 julia> third(xs) 2 julia> fourth(xs) 3 julia> fifth(xs) 4 julia> last(xs) 9 julia> lastpair(xs) (9) julia> nth(xs, 1) 0 julia> nth(xs, 2) 1 julia> nth(xs, 10) 9
julia> xs (0 1 2 3 4 5 6 7 8 9) julia> length(xs) 10 julia> append(list(1, 2, 3), list(4, 5, 6), list(7, 8, 9)) (1 2 3 4 5 6 7 8 9) julia> reverse(xs) (9 8 7 6 5 4 3 2 1 0) julia> take(xs, 5) (0 1 2 3 4) julia> drop(xs, 5) (5 6 7 8 9) julia> takewhile(x -> x < 5, xs) (0 1 2 3 4) julia> dropwhile(x -> x < 5, xs) (5 6 7 8 9) julia> ys = list(1, list(2, list(3, list(4, 5), 6), 7), 8) (1 (2 (3 (4 5) 6) 7) 8) julia> flatten(ys) (1 2 3 4 5 6 7 8)
julia> xs = list(1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5) (1 2 1 2 3 1 2 3 4 1 2 3 4 5) julia> member(4, xs) (4 1 2 3 4 5) julia> member(6, xs) () julia> member(x -> x % 3 == 0, xs) (3 1 2 3 4 1 2 3 4 5) julia> member(x -> x % 7 == 0, xs) () julia> 1 in xs true julia> 5 in xs true julia> 0 in xs false julia> findfirst(isequal(3), xs) 5 julia> findfirst(isequal(6), xs) julia> findnext(isequal(4), xs, 1) 9 julia> findnext(isequal(4), xs, 10) 13 julia> findnext(isequal(4), xs, 14) julia> count(x -> x == 1, xs) 4 julia> count(x -> x % 2 == 0, xs) 6 julia> count(x -> x == 7, xs) 0
julia> xs = tolist(0 : 9) (0 1 2 3 4 5 6 7 8 9) julia> map(x -> x * x, xs) (0 1 4 9 16 25 36 49 64 81) julia> map(+, list(1, 2, 3, 4), list(5, 6, 7, 8)) (6 8 10 12) julia> filter(x -> x % 2 == 0, xs) (0 2 4 6 8) julia> remove(x -> x % 2 == 0, xs) (1 3 5 7 9) julia> remove(isequal(5), xs) (0 1 2 3 4 6 7 8 9) julia> foldl(+, xs, 0) 45 julia> foldr(+, xs, 0) 45 julia> foldl((x, y) -> cons(y, x), xs, nil) (9 8 7 6 5 4 3 2 1 0) julia> foldr(cons, xs, nil) (0 1 2 3 4 5 6 7 8 9) julia> unfold(x -> x > 10, x -> x + 1, 1) (1 2 3 4 5 6 7 8 9 10) julia> unfold(x -> x > 10, x -> x + 1, 1, x -> 2x) (2 4 6 8 10 12 14 16 18 20) julia> foreach(println, xs) 0 1 2 3 4 5 6 7 8 9
julia> xs = iota(1 : 2 : 20) (1 3 5 7 9 11 13 15 17 19) julia> for x = xs; print("$x "); end 1 3 5 7 9 11 13 15 17 19 julia> for (i, x) = enumerate(xs); print("($i, $x)"); end (1, 1)(2, 3)(3, 5)(4, 7)(5, 9)(6, 11)(7, 13)(8, 15)(9, 17)(10, 19) julia> for x = zip(list(1,2,3), list(4,5,6), list(7,8,9)) println(x) end (1, 4, 7) (2, 5, 8) (3, 6, 9) julia> map(tuple, list(1, 2, 3), list(4, 5, 6), list(7, 8, 9)) ((1, 4, 7) (2, 5, 8) (3, 6, 9)) julia> all(x -> x % 2 == 0, list(2, 4, 6, 8, 10)) true julia> all(x -> x % 2 == 0, list(2, 4, 6, 8, 10, 11)) false julia> any(x -> x % 2 != 0, list(2, 4, 6, 8, 10, 11)) true julia> any(x -> x % 2 != 0, list(2, 4, 6, 8, 10)) false
julia> xs = list(1, 2, 3, 4, 5) (1 2 3 4 5) julia> substitute(x -> x % 2 == 0, 0, xs) (1 0 3 0 5) julia> ys = list(1, list(2, list(3, list(4, 5), 6), 7), 8) (1 (2 (3 (4 5) 6) 7) 8) julia> substitute(x -> typeof(x) == Int && x % 2 == 0, 0, ys) (1 (2 (3 (4 5) 6) 7) 0) julia> subst(x -> typeof(x) == Int && x % 2 == 0, 0, ys) (1 (0 (3 (0 5) 0) 7) 0)
julia> merge(list(1, 3, 5, 7, 9), list(2, 4, 6, 8, 10)) (1 2 3 4 5 6 7 8 9 10) julia> mergesort(list(5, 6, 4, 7, 3, 8, 2, 9, 1, 0)) (0 1 2 3 4 5 6 7 8 9) julia> mergesort(list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)) (0 1 2 3 4 5 6 7 8 9) julia> mergesort(list(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)) (0 1 2 3 4 5 6 7 8 9)
julia> xs = pairlis(list(:a, :b, :c, :d), list(1, 2, 3, 4)) ((a . 1) (b . 2) (c . 3) (d . 4)) julia> assoc(:a, xs) (a . 1) julia> assoc(:d, xs) (d . 4) julia> assoc(:e, xs) () julia> ys = acons(:e, 5, xs) ((e . 5) (a . 1) (b . 2) (c . 3) (d . 4)) julia> assoc(:e, ys) (e . 5)
julia> unique(list(1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5)) (1 2 3 4 5) julia> xs = list(1, 2, 3, 4) (1 2 3 4) julia> ys = list(3, 4, 5, 6) (3 4 5 6) julia> union(xs, ys) (1 2 3 4 5 6) julia> intersect(xs, ys) (3 4) julia> difference(xs, ys) (1 2) julia> issubset(list(1,2), xs) true julia> issubset(list(1,5), xs) false julia> issubset(nil, xs) true julia> issubset(xs, xs) true julia> product() (()) julia> product(list(1, 2, 3)) ((1) (2) (3)) julia> product(list(1, 2, 3), list(4, 5, 6)) ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6)) julia> product(list(1, 2, 3), list(4, 5, 6), list(7, 8, 9)) ((1 4 7) (1 4 8) (1 4 9) (1 5 7) (1 5 8) (1 5 9) (1 6 7) (1 6 8) (1 6 9) (2 4 7) (2 4 8) (2 4 9) (2 5 7) (2 5 8) (2 5 9) (2 6 7) (2 6 8) (2 6 9) (3 4 7) (3 4 8) (3 4 9) (3 5 7) (3 5 8) (3 5 9) (3 6 7) (3 6 8) (3 6 9)) julia> product(list(1, 2), list(3, 4), list(5, 6), list(7, 8)) ((1 3 5 7) (1 3 5 8) (1 3 6 7) (1 3 6 8) (1 4 5 7) (1 4 5 8) (1 4 6 7) (1 4 6 8) (2 3 5 7) (2 3 5 8) (2 3 6 7) (2 3 6 8) (2 4 5 7) (2 4 5 8) (2 4 6 7) (2 4 6 8))
# # Imlist.jl : Lisp ライクで immutable な連結リスト (Julia ver 1.6 対応版) # # Copyright (C) 2016-2021 Makoto Hiroi # module Imlist export List, nil, car, cdr, cons, null, listp, consp, atom, equal, lastpair export list, makelist, tabulate, iota, tolist, nth, second, third, fourth, fifth export append, take, drop, takewhile, dropwhile, flatten, remove, unfold, member export mergesort, acons, assoc, pairlis, difference, substitute, subst, product # 多重定義用 import Base: show, iterate, first, last, length, reverse, filter, map, foldl, foldr import Base: foreach, in, findfirst, findnext, merge, union, intersect, issubset, unique # # リストの定義 # abstract type List end # 空リスト struct Nil <: List end # 終端 const nil = Nil() # コンスセル struct Cons <: List car cdr end # # 基本関数 # car(xs::Cons) = xs.car car(xs::Nil) = nil cdr(xs::Cons) = xs.cdr cdr(xs::Nil) = nil 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) # # イテレータ # function iterate(xs::List, state = xs) if null(state) nothing else (car(state), cdr(state)) end end # # 参照 # function nth(xs::List, n::Int) if consp(xs) if n == 1 car(xs) else nth(cdr(xs), n - 1) end 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 # 末尾のコンスセルを返す function lastpair(xs::Cons) if consp(cdr(xs)) lastpair(cdr(xs)) else xs end end # 末尾の要素 function last(xs::Cons) car(lastpair(xs)) end # # リストの生成 # list(args...) = foldr(cons, args, init = nil) function makelist(n::Int, x, xs::List = nil) if n <= 0 xs else makelist(n - 1, x, cons(x, xs)) end end function tolist(xs::AbstractVector{T}) where {T} ys = nil for i = length(xs): -1 : 1 ys = cons(xs[i], ys) end ys end tabulate(f::Function, x::AbstractRange) = tolist(map(f, x)) iota(x::AbstractRange) = tolist(x) # # 基本的なリスト操作 # # 連結 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 foldr(append1, xs) # 後ろからつなげていく end end # 反転 function reverse(xs::List, ys::List = nil) if atom(xs) ys else reverse(cdr(xs), cons(car(xs), ys)) end end # 長さ function length(xs::List, c::Int = 0) if atom(xs) c else length(cdr(xs), c + 1) end end # 先頭から要素を取り出す function take(xs::List, n::Int) if atom(xs) || n == 0 nil else cons(car(xs), take(cdr(xs), n - 1)) end end function takewhile(pred::Function, xs::List) if atom(xs) || !pred(car(xs)) nil else cons(car(xs), takewhile(pred, cdr(xs))) end end # 先頭から要素を取り除く function drop(xs::List, n::Int) if n == 0 || atom(xs) xs else drop(cdr(xs), n - 1) end end function dropwhile(pred::Function, xs::List) if atom(xs) || !pred(car(xs)) xs else dropwhile(pred, cdr(xs)) end 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(pred::Function, xs::List) if atom(xs) nil elseif pred(car(xs)) cons(car(xs), filter(pred, cdr(xs))) else filter(pred, cdr(xs)) end end function remove(pred::Function, xs::List) if atom(xs) nil elseif !pred(car(xs)) cons(car(xs), remove(pred, cdr(xs))) else remove(pred, cdr(xs)) end end # 畳み込み function foldl(f::Function, xs::List, a) if atom(xs) a else foldl(f, cdr(xs), f(a, car(xs))) end end function foldr(f::Function, xs::List, a) if atom(xs) a else f(car(xs), foldr(f, cdr(xs), a)) end end # 逆畳み込み function unfold(cond::Function, iter::Function, s, func::Function = identity) if cond(s) nil else cons(func(s), unfold(cond, iter, iter(s), func)) end end # 巡回 function foreach(f::Function, xs::List) if consp(xs) f(car(xs)) foreach(f, cdr(xs)) end end # # 探索 # function member(pred::Function, xs::List) if atom(xs) nil elseif pred(car(xs)) xs else member(pred, cdr(xs)) end end function member(y, xs::List, op = equal) if atom(xs) nil elseif op(car(xs), y) xs else member(y, cdr(xs), op) end end # とりあえず missing は考慮しない function in(x, xs::List) !null(member(x, xs)) end function findfirst(pred::Function, xs::List, i::Int = 1) if atom(xs) nothing elseif pred(car(xs)) i else findfirst(pred, cdr(xs), i + 1) end end function findnext(pred::Function, xs::List, i::Int) idx = findfirst(pred, drop(xs, i - 1)) if idx === nothing nothing else idx + i - 1 end 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, op = <=) if atom(xs) ys elseif atom(ys) xs else x = car(xs) y = car(ys) if op(x, y) cons(x, merge(cdr(xs), ys, op)) else cons(y, merge(xs, cdr(ys), op)) end end end # マージソート function mergesort(xs::List, op = <=) function sort(xs::List, n::Int) if n == 1 list(car(xs)) elseif n == 2 x = car(xs) y = car(cdr(xs)) op(x, y) ? list(x, y) : list(y, x) else m = div(n, 2) merge(sort(xs, m), sort(drop(xs, m), n - m), op) end end sort(xs, length(xs)) end # 連想リスト acons(key, val, alist::List) = cons(cons(key, val), alist) assoc(key, xs::List) = car(member(ys -> equal(key, car(ys)), 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 unique(xs::List, ys::List = nil) if atom(xs) reverse(ys) # 順序を保つ必要がなければ reverse は不要 elseif car(xs) in ys unique(cdr(xs), ys) else unique(cdr(xs), cons(car(xs), ys)) end end # 和集合 function union(xs::List, ys::List) if atom(xs) ys elseif car(xs) in ys union(cdr(xs), ys) else cons(car(xs), union(cdr(xs), ys)) end end # 積集合 function intersect(xs::List, ys::List) if atom(xs) nil elseif car(xs) in 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 car(xs) in ys difference(cdr(xs), ys) else cons(car(xs), difference(cdr(xs), ys)) end end # 部分集合の判定 function issubset(xs::List, ys::List) if null(xs) true elseif car(xs) in ys issubset(cdr(xs), ys) else false end end # 直積集合 function product(args::List...) if length(args) == 0 list(nil) else xs = map(x -> list(x), args[end]) for i = length(args) - 1: -1 : 1 xs = append(map(y -> map(zs -> cons(y, zs), xs), args[i])...) end xs end end end
リスト : リストの要素はひとつか? singlep(xs::List) = consp(xs) && null(cdr(xs))
julia> singlep(nil) false julia> singlep(list(1)) true julia> singlep(list(1, 2)) false
リスト : リストの要素はふたつか? 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
リスト : リスト 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
リスト : リストの末尾から 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) ()
リスト : リストを長さ 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))
リスト : リストの要素を関数 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 = 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))
リスト : クイックソート function quicksort(xs::List) if null(xs) nil else ys, zs = partition(x -> x < car(xs), cdr(xs)) append(quicksort(ys), cons(car(xs), quicksort(zs))) end end
julia> quicksort(list(5, 6, 4, 7, 3, 8, 2, 9, 1, 0)) (0 1 2 3 4 5 6 7 8 9) julia> quicksort(list(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)) (0 1 2 3 4 5 6 7 8 9) julia> quicksort(list(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)) (0 1 2 3 4 5 6 7 8 9)
リスト : 木の探索 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 = 0 : 10; println(member_tree(x, xs)); end false true true true true true true true true true false
リスト : 葉の個数を数える function countleaf(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> countleaf(xs) 9 julia> countleaf(nil) 0 julia> countleaf(iota(1 : 10)) 10
リスト : 順列の生成 # 高階関数版 function permutations(f::Function, xs::List, n::Int) function perm(xs, m, a) if n == m f(reverse(a)) else for x = xs perm(remove(isequal(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(isequal(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))
リスト : 組み合わせの生成 # 高階関数版 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))
リスト : べき集合の生成 # 高階関数版 function powerset(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 powerset(xs::List) if null(xs) list(nil) else append(powerset(cdr(xs)), map(ys -> cons(car(xs), ys), powerset(cdr(xs)))) end end
julia> powerset(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> powerset(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))
リスト : 素数を求める # xs を反転して ys と連結する function reverse_append(xs, ys) for x = xs ys = cons(x, ys) end ys end function primelist(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> primelist(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> primelist(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)
リスト : N Queens Problem (単純な生成検定法) # 衝突の検出 function attack(q, board) for (i, x) = 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 = board for x = 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
リスト : マスターマインドの解法 # 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!