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!