Julia Language Programming

遅延ストリーム (モジュール編)

拙作のページ「遅延ストリーム (前編, 後編)」で作成したプログラムをモジュール化したものです。学習が目的のプログラムなので実用性はありませんが、興味のある方は試してみてください。

●遅延評価の仕様

• モジュール名: Lazy
• データ型
  • Promise : プロミス (非公開)
• 操作関数とマクロ
  • @delay expr : 式 expr の評価を遅延するためのマクロ, 返り値はプロミス
  • force(p) : プロミスを評価する
    • 評価結果はキャッシュされる
    • 再度評価するとキャッシュした値を返す

julia> a = @delay (println("oops!"); 1 + 2 * 3)
Lazy.Promise(var"#1#2"(), false, nothing)

julia> force(a)
oops!
7

julia> force(a)
7

●遅延ストリームの仕様

• モジュール名: Lazy
• データ型
  • LazyStream : 遅延ストリーム (抽象型, 公開)
  • Nil : 空の遅延ストリーム (非公開)
  • Cons : コンスセル (非公開)
• 定数
  • nils : 空の遅延ストリーム

julia> nils
LazyStream()

• 基本関数とマクロ
  • @cons(x, s) : 遅延ストリーム s の先頭に x を追加した新しい遅延ストリームを返す
  • head(s) : s の先頭要素を返す
  • tail(s) : s の先頭要素を取り除いた遅延ストリームを返す
  • isempty(s) : s が空の遅延ストリームであれば true を返す

julia> isempty(nils)
true

julia> s1 = @cons(1, @cons(2, @cons(3, nils)))
LazyStream(1, ?)

julia> head(s1)
1

julia> tail(s1)
LazyStream(2, ?)

julia> head(tail(s1))
2

julia> head(tail(tail(s1)))
3

julia> tail(tail(tail(s1)))
LazyStream()

• 遅延ストリームの生成
  • unfold(iter, seed, cond = _ -> false) : 逆畳み込み
    • iter: seed に適用する関数, iter(seed) で次の seed を生成する
    • seed: 値, 遅延ストリームの要素になる
    • cond: 終了条件を表す関数, cond(seed) が真になるとき unfold() は nils を返す
    • cond が常に false を返す場合は無限ストリームになる
  • tolazy(iter) : イテレータを遅延ストリームに変換する
  • circle(args...) : 引数 args を繰り返す無限ストリームを生成する
  • cycle(iter) : イテレータを繰り返す無限ストリームを生成する

julia> s = unfold(x -> x + 1, 1)
LazyStream(1, ?)

julia> for _ = 1 : 10
       print("$(head(s)) ")
       global s = tail(s)
       end
1 2 3 4 5 6 7 8 9 10

julia> s = tolazy(1 : 10)
LazyStream(1, ?)

julia> for _ = 1 : 10
       print("$(head(s)) ")
       global s = tail(s)
       end
1 2 3 4 5 6 7 8 9 10

julia> s
LazyStream()

julia> s1 = circle(1,2,3)
LazyStream(1, ?)

julia> for _ = 1 : 10
       print("$(head(s1)) ")
       global s1 = tail(s1)
       end
1 2 3 1 2 3 1 2 3 1

julia> s1
LazyStream(2, ?)

julia> circle()
LazyStream()

julia> s2 = cycle(1 : 4)
LazyStream(1, ?)

julia> for _ = 1 : 10
       print("$(head(s2)) ")
       global s2 = tail(s2)
       end
1 2 3 4 1 2 3 4 1 2

julia> s2
LazyStream(3, ?)

julia> cycle([])
LazyStream()

• 基本的な遅延ストリームの操作
  • nth(s, n) : 遅延ストリーム s の n 番目の要素を返す (Julia と同じく先頭が 1 番目)
  • append(s1, s2) : 引数の遅延ストリーム s1 と s2 を連結した遅延ストリームを返す
    • s1 が無限ストリームの場合、s1 の要素だけが出力されることに注意
  • interleave(s1, s2) : s1 と s2 の要素を交互に出力する遅延ストリームを返す
    • s1 と s2 が無限ストリームでも動作する
  • reverse(s) : s を反転した遅延ストリームを返す (s は有限であること)
  • take(s, n) : s の先頭から n 個の要素を取り出す遅延ストリームを返す
  • takewhile(pred, xs): s の先頭から関数 pred が真を返す間、それらの要素を取り出す遅延ストリームを返す
  • drop(xs, n) : s の先頭から n 個の要素を取り除いた遅延ストリームを返す
  • dropwhile(pred, xs): s の先頭から関数 pred が真を返す間、それらの要素を取り除いた遅延ストリームを返す

julia> s = unfold(x -> x + 1, 1)
LazyStream(1, ?)

julia> nth(s, 1)
1

julia> nth(s, 10)
10

julia> nth(s, 100)
100

julia> s1 = tolazy(1:2:10)
LazyStream(1, ?)

julia> s2 = tolazy(2:2:10)
LazyStream(2, ?)

julia> s3 = append(s1, s2)
LazyStream(1, ?)

julia> for i = 1 : 10
       print("$(nth(s3, i)) ")
       end
1 3 5 7 9 2 4 6 8 10

julia> s3 = interleave(s1, s2)
LazyStream(1, ?)

julia> for i = 1 : 10
       print("$(nth(s3, i)) ")
       end
1 2 3 4 5 6 7 8 9 10

julia> s3 = reverse(s1)
LazyStream(9, ?)

julia> for i = 1 : 5
       print("$(nth(s3, i)) ")
       end
9 7 5 3 1

julia> s4 = take(s, 10)
LazyStream(1, ?)

julia> for i = 1 : 10
       print("$(nth(s4, i)) ")
       end
1 2 3 4 5 6 7 8 9 10

julia> drop(s4, 10)
LazyStream()

julia> drop(s, 10)
LazyStream(11, ?)

julia> s4 = takewhile(x -> x < 6, s)
LazyStream(1, ?)

julia> for i = 1 : 5
       print("$(nth(s4, i)) ")
       end
1 2 3 4 5

julia> s4 = dropwhile(x -> x < 6, s)
LazyStream(6, ?)

julia> for i = 1 : 5
       print("$(nth(s4, i)) ")
       end
6 7 8 9 10

• 高階関数
  • map(f, s...) : 遅延ストリーム s の要素に関数 f を適用した遅延ストリームを返す (マッピング)
  • flatmap(f, s) : マッピングのあと平坦化した遅延ストリームを返す
  • filter(pred, s) : s の要素に関数 pred を適用し、真を返す要素を格納した遅延ストリームを返す
  • foldl(f, s, init) : s の先頭から畳み込む
  • foldr(f, s, init) : s の末尾から畳み込む
  • foreach(f, s) : s の要素に関数 f を適用する
  • foldl(), foldr(), foreach() は有限ストリームのみ対応

julia> s1 = map(x -> x * x, s)
LazyStream(1, ?)

julia> for i = 1 : 10
       print("$(nth(s1, i)) ")
       end
1 4 9 16 25 36 49 64 81 100

julia> s2 = flatmap(x -> tolazy(1:x), s)
LazyStream(1, ?)

julia> for i = 1 : 20
       print("$(nth(s2, i)) ")
       end
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5

julia> s3 = filter(iseven, s)
LazyStream(2, ?)

julia> for i = 1 : 20
       print("$(nth(s3, i)) ")
       end
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

julia> foldl(+, take(s, 10), 0)
55

julia> foldr(+, take(s, 10), 0)
55

julia> foreach(println, take(s, 10))
1
2
3
4
5
6
7
8
9
10

• イテレータ
  • イテレータを実装しているので、それを受け取る関数ならば、たいていの場合は動作する
  • ただし、getindex() や lastindex() を実装していないので、それらを使用している関数は動作しない
  • 無限ストリームを渡すと無限ループになるので注意すること
  • zip(iter...) : イテレータから要素を取り出し、それをタプルに格納して返す (返り値はイテレータ)
  • enumerate(iter) : 添字と要素を返す (返り値はイテレータ)
  • all(f, iter) : イテレータの要素に関数 f を適用し、結果がすべて真ならば真を返す
  • any(f, iter) : イテレータの要素に関数 f を適用し、結果がすべて偽ならば偽を返す (ひとつでも真ならば真を返す)
  • その他いろいろある

julia> s = unfold(x -> x + 1, 1)
LazyStream(1, ?)

julia> for x = take(s, 10)
       print("$x ")
       end
1 2 3 4 5 6 7 8 9 10

julia> for x = zip(take(s, 10), map(x -> x*x, s))
       print(x)
       end
(1, 1)(2, 4)(3, 9)(4, 16)(5, 25)(6, 36)(7, 49)(8, 64)(9, 81)(10, 100)

julia> for x = enumerate(take(map(x -> x*x, s), 10))
       print(x)
       end
(1, 1)(2, 4)(3, 9)(4, 16)(5, 25)(6, 36)(7, 49)(8, 64)(9, 81)(10, 100)

julia> all(x -> x < 10, takewhile(x -> x < 10, s))
true

julia> all(x -> x < 10, takewhile(x -> x < 11, s))
false

julia> any(iseven, take(s, 10))
true

julia> any(iseven, take(filter(isodd, s), 10))
false

• 併合 (マージ) と集合演算
  • 以下の関数はストリームの要素が昇順に並んでいることを前提として動作する
  • merge(s1, s2) : 引数の遅延ストリーム s1 と s2 をマージする
  • unique(s) : s から重複要素を取り除いたリストを返す
  • union(s1, s2) : 和集合
  • intersect(s1, s2) : 積集合

julia> s1 = unfold(x -> x + 2, 1)
LazyStream(1, ?)

julia> s2 = unfold(x -> x + 2, 2)
LazyStream(2, ?)

julia> s3 = merge(s1, s2)
LazyStream(1, ?)

julia> foreach(println, take(s3, 10))
1
2
3
4
5
6
7
8
9
10

julia> for x = unique(tolazy([1,1,2,2,3,3,4,4,5,5]))
       println(x)
       end
1
2
3
4
5

julia> s1 = tolazy(1:8)
LazyStream(1, ?)

julia> s2 = tolazy(4:12)
LazyStream(4, ?)

julia> for x in union(s1, s2)
       print("$x ")
       end
1 2 3 4 5 6 7 8 9 10 11 12

julia> for x in intersect(s1, s2)
       print("$x ")
       end
4 5 6 7 8

●プログラムリスト

#
# Lazy.jl : 遅延評価と遅延ストリーム
#
#           Copyright (C) 2016-2021 Makoto Hiroi
#
#
module Lazy

export @delay, force, LazyStream, nils, @cons, head, tail, unfold, tolazy, circle, cycle
export nth, take, takewhile, drop, dropwhile, append, interleave, append_delay, flatmap

import Base: isempty, iterate, show, reverse, map, filter, foldl, foldr, foreach, merge
import Base: unique, union, intersect

#
# 遅延評価
#

# プロミス
mutable struct Promise
    func
    flag::Bool
    value
end

macro delay(expr)
    :(Promise(() -> $(esc(expr)), false, nothing))
end

function force(p::Promise)
    if !p.flag
        p.value = p.func()
        p.flag = true
    end
    p.value
end

#
# 遅延ストリーム
#
abstract type LazyStream end

# 終端
struct Nil <: LazyStream
end

# 定数
const nils = Nil()

# 終端の判定
Base.isempty(s::LazyStream) = s === nils

# 遅延ストリーム
struct Cons <: LazyStream
    head
    tail::Promise
end

# ストリームを生成するマクロ
macro cons(x, s)
esc(:(Lazy.Cons($x, @delay $s)))
end

# アクセス関数
head(s::Nil) = nils
head(s::Cons) = s.head
tail(s::Nil) = nils
tail(s::Cons) = force(s.tail)

# イテレータ
function iterate(s::LazyStream, state = s)
    if isempty(state)
        nothing
    else
        (head(state), tail(state))
    end
end

# 表示
function show(io::IO, s::LazyStream)
    if isempty(s)
        print(io, "LazyStream()")
    else
        print(io, "LazyStream($(head(s)), ?)")
    end
end

# 遅延ストリームの生成
function unfold(iter::Function, seed, cond::Function = _ -> false)
    if cond(seed)
        nils
    else
        @cons(seed, unfold(iter, iter(seed), cond))
    end
end

# イテレータを遅延ストリームに変換する
function tolazy(iter, state = nothing)
    next = state === nothing ? iterate(iter) : iterate(iter, state)
    if next === nothing
        nils
    else
        @cons(next[1], tolazy(iter, next[2]))
    end
end

# 引数を無限に繰り返す
function circle(args...; idx = 1)
    if isempty(args)
        nils
    else
        @cons(args[idx], circle(args..., idx = length(args) == idx ? 1 : idx + 1))
    end
end

# イテレータを無限に繰り返す
function cycle(iter, state = nothing)
    if state == nothing
        next = iterate(iter)
        if next === nothing
            return nils
        end
    else
        next = iterate(iter, state)
        if next === nothing
            next = iterate(iter)
        end
    end
    @cons(next[1], cycle(iter, next[2]))
end

# n 番目の要素を求める
function nth(s::LazyStream, n::Int)
    while n > 1
        if isempty(s)
            error("nth: empty stream")
        end
        s = tail(s)
        n -= 1
    end
    head(s)
end

# 先頭から n 個の要素を取り出す
function take(s::LazyStream, n::Int)
    if isempty(s) || n <= 0
        nils
    else
        @cons(head(s), take(tail(s), n - 1))
    end
end

# 先頭から n 個の要素を取り除く
function drop(s::LazyStream, n::Int)
    while !isempty(s) && n > 0
        s = tail(s)
        n -= 1
    end
    s
end

# 関数 pred が真を返す間、先頭から要素を取り出す
function takewhile(pred, s::LazyStream)
    if isempty(s) || !pred(head(s))
        nils
    else
        @cons(head(s), takewhile(pred, tail(s)))
    end
end

# 関数 pred が真を返す間、先頭から要素を取り除く
function dropwhile(pred, s::LazyStream)
    while !isempty(s) && pred(head(s))
        s = tail(s)
    end
    s
end

# 連結
function append(s1::LazyStream, s2::LazyStream)
    if isempty(s1)
        s2
    else
        @cons(head(s1), append(tail(s1), s2))
    end
end

function interleave(s1::LazyStream, s2::LazyStream)
    if isempty(s1)
        s2
    else
        @cons(head(s1), interleave(s2, tail(s1)))
    end
end

# 反転
function reverse(s::LazyStream)
    if isempty(s)
        nils
    else
        append(reverse(tail(s)), @cons(head(s), nils))
    end
end

#
# 高階関数
#

# マッピング
function map(func::Function, xs::LazyStream...)
    if any(isempty, xs)
        nils
    else
        @cons(func(map(head, xs)...), map(func, map(tail, xs)...))
    end
end

# フィルター
function filter(pred::Function, s::LazyStream)
    while !isempty(s)
        if pred(head(s))
            return @cons(head(s), filter(pred, tail(s)))
        end
        s = tail(s)
    end
    nils
end

# 畳み込み
function foldl(f::Function, s::LazyStream, a)
    while !isempty(s)
        a = f(a, head(s))
        s = tail(s)
    end
    a
end

function foldr(f::Function, s::LazyStream, a)
    if isempty(s)
        a
    else
        f(head(s), foldr(f, tail(s), a))
    end
end

# 巡回
function foreach(f::Function, s::LazyStream)
    while !isempty(s)
        f(head(s))
        s = tail(s)
    end
end

function append_delay(s1::LazyStream, s2::Promise)
    if isempty(s1)
        force(s2)
    else
        @cons(head(s1), append_delay(tail(s1), s2))
    end
end

# 遅延ストリームの平坦化
function flatmap(f::Function, s::LazyStream)
    if isempty(s)
        s
    else
        append_delay(f(head(s)), @delay flatmap(f, tail(s)))
    end
end

#
# 併合と集合演算
#
# 以下の関数はストリームの要素が昇順で並んでいることを前提としている
#

# 遅延ストリームの併合
function merge(s1::LazyStream, s2::LazyStream)
    if isempty(s1)
        s2
    elseif isempty(s2)
        s1
    elseif head(s1) <= head(s2)
        @cons(head(s1), merge(tail(s1), s2))
    else
        @cons(head(s2), merge(s1, tail(s2)))
    end
end

# 重複要素の削除
function unique(s::LazyStream)
    if isempty(s)
        s
    else
        @cons(head(s), unique(dropwhile(x -> x == head(s), tail(s))))
    end
end

# 和集合
function union(s1::LazyStream, s2::LazyStream)
    if isempty(s1)
        s2
    elseif isempty(s2)
        s1
    elseif head(s1) < head(s2)
        @cons(head(s1), union(tail(s1), s2))
    elseif head(s1) == head(s2)
        @cons(head(s1), union(tail(s1), tail(s2)))
    else
        @cons(head(s2), union(s1, tail(s2)))
    end
end

# 積集合
function intersect(s1::LazyStream, s2::LazyStream)
    while !isempty(s1) && !isempty(s2)
        if head(s1) == head(s2)
            return @cons(head(s1), intersect(tail(s1), tail(s2)))
        elseif head(s1) < head(s2)
            s1 = tail(s1)
        else
            s2 = tail(s2)
        end
    end
    nils
end

end

●簡単なサンプルプログラム

たらいまわし関数

リスト : たらいまわし関数

# 通常版
function tarai(x, y, z)
  if x <= y
    y
  else
    tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
  end
end

# 遅延評価版
function tarai1(x, y, z)
  if x <= y
    y
  else
    zz = force(z)
    tarai1(tarai1(x - 1, y, @delay zz),
           tarai1(y - 1, zz, @delay x),
           @delay tarai1(zz - 1, x, @delay y))
  end
end

julia> @time tarai(14, 7, 0)
  1.805034 seconds
14

julia> @time tarai1(14, 7, @delay 0)
  0.046525 seconds (29.89 k allocations: 1.848 MiB, 93.22% compilation time)
14

実行環境 : Julia ver 1.6.4, Ubuntu 18.04 (WSL), Intel Core i5-6200U 2.30GHz

数列の生成

リスト : 数列の生成

# 整数列 (有限)
integers(low, high) = unfold(x -> x + 1, low, x -> x > high)

# 1 から始まる整数列 (無限)
ints = unfold(x -> x + 1, 1)

# フィボナッチ数
fibonacci(a, b) = @cons(a, fibonacci(b, a + b))

fibos = @cons(0, @cons(1, map(+, tail(fibos), fibos)))

julia> foreach(x -> print("$x "), integers(1, 10))
1 2 3 4 5 6 7 8 9 10
julia> foreach(x -> print("$x "), take(ints, 10))
1 2 3 4 5 6 7 8 9 10
julia> foreach(x -> print("$x "), take(fibonacci(0, 1), 10))
0 1 1 2 3 5 8 13 21 34
julia> foreach(x -> print("$x "), take(fibos, 10))
0 1 1 2 3 5 8 13 21 34
julia> nth(fibos, 40)
63245986

julia> nth(fibos, 50)
7778742049

直積集合

リスト : 直積集合 (有限)

function product(s1::LazyStream, s2::LazyStream)
    flatmap(x -> map(y -> (x, y), s2), s1)
end

julia> s1 = tolazy(1:5)
LazyStream(1, ?)

julia> s2 = tolazy(6:10)
LazyStream(6, ?)

julia> s3 = product(s1, s2)
LazyStream((1, 6), ?)

julia> foreach(print, s3)
(1, 6)(1, 7)(1, 8)(1, 9)(1, 10)
(2, 6)(2, 7)(2, 8)(2, 9)(2, 10)
(3, 6)(3, 7)(3, 8)(3, 9)(3, 10)
(4, 6)(4, 7)(4, 8)(4, 9)(4, 10)
(5, 6)(5, 7)(5, 8)(5, 9)(5, 10)

リスト : 直積集合 (無限)

function product_inf(s1::LazyStream, s2::LazyStream, n = 1)
    append_delay(map((x, y) -> (x, y), take(s1, n), reverse(take(s2, n))),
                 @delay product_inf(s1, s2, n + 1))
end

julia> s = unfold(x -> x + 1, 1)
LazyStream(1, ?)

julia> s1 = product_inf(s, s)
LazyStream((1, 1), ?)

julia> foreach(print, take(s1, 55))
(1, 1)
(1, 2)(2, 1)
(1, 3)(2, 2)(3, 1)
(1, 4)(2, 3)(3, 2)(4, 1)
(1, 5)(2, 4)(3, 3)(4, 2)(5, 1)
(1, 6)(2, 5)(3, 4)(4, 3)(5, 2)(6, 1)
(1, 7)(2, 6)(3, 5)(4, 4)(5, 3)(6, 2)(7, 1)
(1, 8)(2, 7)(3, 6)(4, 5)(5, 4)(6, 3)(7, 2)(8, 1)
(1, 9)(2, 8)(3, 7)(4, 6)(5, 5)(6, 4)(7, 3)(8, 2)(9, 1)
(1, 10)(2, 9)(3, 8)(4, 7)(5, 6)(6, 5)(7, 4)(8, 3)(9, 2)(10, 1)

格子点

リスト : 二次元の格子点

lattice2() = unfold(st -> st[1] == 0 ? (st[2] + 1, 0) : (st[1] - 1, st[2] + 1), (0, 0))

julis> s = lattice2()
LazyStream((0, 0), ?)

julis> foreach(print, take(s, 55))
(0, 0)
(1, 0)(0, 1)
(2, 0)(1, 1)(0, 2)
(3, 0)(2, 1)(1, 2)(0, 3)
(4, 0)(3, 1)(2, 2)(1, 3)(0, 4)
(5, 0)(4, 1)(3, 2)(2, 3)(1, 4)(0, 5)
(6, 0)(5, 1)(4, 2)(3, 3)(2, 4)(1, 5)(0, 6)
(7, 0)(6, 1)(5, 2)(4, 3)(3, 4)(2, 5)(1, 6)(0, 7)
(8, 0)(7, 1)(6, 2)(5, 3)(4, 4)(3, 5)(2, 6)(1, 7)(0, 8)
(9, 0)(8, 1)(7, 2)(6, 3)(5, 4)(4, 5)(3, 6)(2, 7)(1, 8)(0, 9)

出力は手作業で整形しています。

リスト : d 次元格子点の生成

function lattice_sub(d::Int, n::Int)
    if d == 1
        @cons((n,), nils)
    elseif n == 0
        @cons(Tuple(zeros(Int, d)), nils)
    else
        flatmap(x -> map(xs -> (x, xs...), lattice_sub(d - 1, n - x)), tolazy(0 : n))
    end
end

function lattice(d::Int)
    flatmap(n -> lattice_sub(d, n), unfold(x -> x + 1, 0))
end

julis> s1 = lattice(1)
LazyStream((0,), ?)

julis> foreach(print, take(s1, 60))
(0,)(1,)(2,)(3,)(4,)(5,)(6,)(7,)(8,)(9,)(10,)(11,)(12,)(13,)(14,)(15,)(16,)(17,)(18,)(19,)
(20,)(21,)(22,)(23,)(24,)(25,)(26,)(27,)(28,)(29,)(30,)(31,)(32,)(33,)(34,)(35,)(36,)(37,)(38,)(39,)
(40,)(41,)(42,)(43,)(44,)(45,)(46,)(47,)(48,)(49,)(50,)(51,)(52,)(53,)(54,)(55,)(56,)(57,)(58,)(59,)

julis> s2 = lattice(2)
LazyStream((0, 0), ?)

julis> foreach(print, take(s2, 60))
(0, 0)(0, 1)(1, 0)(0, 2)(1, 1)(2, 0)(0, 3)(1, 2)(2, 1)(3, 0)(0, 4)(1, 3)(2, 2)(3, 1)(4, 0)(0, 5)
(1, 4)(2, 3)(3, 2)(4, 1)(5, 0)(0, 6)(1, 5)(2, 4)(3, 3)(4, 2)(5, 1)(6, 0)(0, 7)(1, 6)(2, 5)(3, 4)
(4, 3)(5, 2)(6, 1)(7, 0)(0, 8)(1, 7)(2, 6)(3, 5)(4, 4)(5, 3)(6, 2)(7, 1)(8, 0)(0, 9)(1, 8)(2, 7)
(3, 6)(4, 5)(5, 4)(6, 3)(7, 2)(8, 1)(9, 0)(0, 10)(1, 9)(2, 8)(3, 7)(4, 6)

julis> s3 = lattice(3)
LazyStream((0, 0, 0), ?)

julis> foreach(print, take(s3, 60))
(0, 0, 0)(0, 0, 1)(0, 1, 0)(1, 0, 0)(0, 0, 2)(0, 1, 1)(0, 2, 0)(1, 0, 1)(1, 1, 0)(2, 0, 0)(0, 0, 3)
(0, 1, 2)(0, 2, 1)(0, 3, 0)(1, 0, 2)(1, 1, 1)(1, 2, 0)(2, 0, 1)(2, 1, 0)(3, 0, 0)(0, 0, 4)(0, 1, 3)
(0, 2, 2)(0, 3, 1)(0, 4, 0)(1, 0, 3)(1, 1, 2)(1, 2, 1)(1, 3, 0)(2, 0, 2)(2, 1, 1)(2, 2, 0)(3, 0, 1)
(3, 1, 0)(4, 0, 0)(0, 0, 5)(0, 1, 4)(0, 2, 3)(0, 3, 2)(0, 4, 1)(0, 5, 0)(1, 0, 4)(1, 1, 3)(1, 2, 2)
(1, 3, 1)(1, 4, 0)(2, 0, 3)(2, 1, 2)(2, 2, 1)(2, 3, 0)(3, 0, 2)(3, 1, 1)(3, 2, 0)(4, 0, 1)(4, 1, 0)
(5, 0, 0)(0, 0, 6)(0, 1, 5)(0, 2, 4)(0, 3, 3)

julis> s4 = lattice(4)
LazyStream((0, 0, 0, 0), ?)

julis> foreach(print, take(s4, 60))
(0, 0, 0, 0)(0, 0, 0, 1)(0, 0, 1, 0)(0, 1, 0, 0)(1, 0, 0, 0)(0, 0, 0, 2)(0, 0, 1, 1)(0, 0, 2, 0)
(0, 1, 0, 1)(0, 1, 1, 0)(0, 2, 0, 0)(1, 0, 0, 1)(1, 0, 1, 0)(1, 1, 0, 0)(2, 0, 0, 0)(0, 0, 0, 3)
(0, 0, 1, 2)(0, 0, 2, 1)(0, 0, 3, 0)(0, 1, 0, 2)(0, 1, 1, 1)(0, 1, 2, 0)(0, 2, 0, 1)(0, 2, 1, 0)
(0, 3, 0, 0)(1, 0, 0, 2)(1, 0, 1, 1)(1, 0, 2, 0)(1, 1, 0, 1)(1, 1, 1, 0)(1, 2, 0, 0)(2, 0, 0, 1)
(2, 0, 1, 0)(2, 1, 0, 0)(3, 0, 0, 0)(0, 0, 0, 4)(0, 0, 1, 3)(0, 0, 2, 2)(0, 0, 3, 1)(0, 0, 4, 0)
(0, 1, 0, 3)(0, 1, 1, 2)(0, 1, 2, 1)(0, 1, 3, 0)(0, 2, 0, 2)(0, 2, 1, 1)(0, 2, 2, 0)(0, 3, 0, 1)
(0, 3, 1, 0)(0, 4, 0, 0)(1, 0, 0, 3)(1, 0, 1, 2)(1, 0, 2, 1)(1, 0, 3, 0)(1, 1, 0, 2)(1, 1, 1, 1)
(1, 1, 2, 0)(1, 2, 0, 1)(1, 2, 1, 0)(1, 3, 0, 0)

多角数

リスト : 多角数

# 三角数
triangulars = map(x -> div(x * (x + 1), 2), ints)

# 四角数
squares = map(x -> x * x, ints)

# 平方三角数
trisquares = intersect(triangulars, squares)

julia> foreach(x -> print("$x "), take(triangulars, 10))
1 3 6 10 15 21 28 36 45 55
julia> foreach(x -> print("$x "), take(squares, 10))
1 4 9 16 25 36 49 64 81 100
julia> foreach(x -> print("$x "), take(trisquares, 7))
1 36 1225 41616 1413721 48024900 1631432881

ハミングの問題

リスト : ハミングの問題

hammings = @cons(1, union(union(map(x -> 2x, hammings), map(x -> 3x, hammings)), map(x -> 5x, hammings)))

julia> foreach(x -> print("$x "), take(hammings, 100))
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 
128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 405 432 450 
480 486 500 512 540 576 600 625 640 648 675 720 729 750 768 800 810 864 900 960 972 1000 1024 1080 1125 1152 
1200 1215 1250 1280 1296 1350 1440 1458 1500 1536

FizzBuzz 問題

リスト : FizzBuzz 問題

function fizzbuzz()
    function change(x, y, z)
        m = y + z
        if m == 0
            string(x)
        elseif m == 1
            "Fizz"
        elseif m == 2
            "Buzz"
        else
            "FizzBuzz"
        end
    end
    map(change, unfold(x -> x + 1, 1), circle(0,0,1), circle(0,0,0,0,2))
end

julia> for x = take(fizzbuzz(), 100)
       print("$x ")
       end
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 permutations(n::Int, s::LazyStream)
    if n == 0
        @cons([], nils)
    else
        flatmap(s) do x
            map(y -> vcat([x], y),
                permutations(n - 1, filter(z -> x != z, s)))
        end
    end
end

julia> foreach(println, permutations(4, integers(1, 4)))
Any[1, 2, 3, 4]
Any[1, 2, 4, 3]
Any[1, 3, 2, 4]
Any[1, 3, 4, 2]
Any[1, 4, 2, 3]
Any[1, 4, 3, 2]
Any[2, 1, 3, 4]
Any[2, 1, 4, 3]
Any[2, 3, 1, 4]
Any[2, 3, 4, 1]
Any[2, 4, 1, 3]
Any[2, 4, 3, 1]
Any[3, 1, 2, 4]
Any[3, 1, 4, 2]
Any[3, 2, 1, 4]
Any[3, 2, 4, 1]
Any[3, 4, 1, 2]
Any[3, 4, 2, 1]
Any[4, 1, 2, 3]
Any[4, 1, 3, 2]
Any[4, 2, 1, 3]
Any[4, 2, 3, 1]
Any[4, 3, 1, 2]
Any[4, 3, 2, 1]

組み合わせの生成

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

function combinations(n::Int, s::LazyStream)
    if n == 0
        @cons([], nils)
    elseif isempty(s)
        nils
    else
        append_delay(map(y -> vcat([head(s)], y), combinations(n - 1, tail(s))),
                     @delay combinations(n, tail(s)))
    end
end

julia> foreach(println, combinations(3, integers(1, 5)))
Any[1, 2, 3]
Any[1, 2, 4]
Any[1, 2, 5]
Any[1, 3, 4]
Any[1, 3, 5]
Any[1, 4, 5]
Any[2, 3, 4]
Any[2, 3, 5]
Any[2, 4, 5]
Any[3, 4, 5]

素数

リスト : エラトステネスの篩

function sieve(s)
    if isempty(s)
        s
    else
        x = head(s)
        @cons(x, sieve(filter(n -> n % x != 0, tail(s))))
    end
end

julia> ps = sieve(unfold(x -> x + 1, 2))
LazyStream(2, ?)

julia> foreach(x -> print("$x "), take(ps, 25))
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> @time nth(ps, 5000)
 13.291821 seconds (88.39 M allocations: 2.069 GiB, 64.84% gc time, 0.13% compilation time)
48611

実行環境 : Julia ver 1.6.4, Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz

リスト : 素数列 (遅延ストリーム)

primes = @cons(2, @cons(3, @cons(5, primesfrom(7))))

# 素数の生成
function primesfrom(n)
    while true
        if isprime1(n)
            return @cons(n, primesfrom(n + 2))
        end
        n += 2
    end
end

# n は素数か
function isprime(n)
    all(x -> n % x != 0, takewhile(p -> p * p <= n, primes))
end

# こちらのほうがもっと速い
function isprime1(n)
    s = primes
    while true
        x = head(s)
        if n % x == 0
            return false
        elseif x * x > n
            return true
        end
        s = tail(s)
    end
end

julia> foreach(x -> print("$x "), take(primes, 25))
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> @time nth(primes, 5000)
  0.035903 seconds (762.82 k allocations: 11.867 MiB)
48611

実行環境 : Julia ver 1.6.4, Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz

双子素数

リスト : 双子素数

twinprimes = filter(xs -> xs[2] - xs[1] == 2, map((x, y) -> (x, y), primes, tail(primes)))

julia> foreach(x -> print("$x "), take(twinprimes, 100))
(3, 5) (5, 7) (11, 13) (17, 19) (29, 31) (41, 43) (59, 61) (71, 73) (101, 103) (107, 109) (137, 139) 
(149, 151) (179, 181) (191, 193) (197, 199) (227, 229) (239, 241) (269, 271) (281, 283) (311, 313) 
(347, 349) (419, 421) (431, 433) (461, 463) (521, 523) (569, 571) (599, 601) (617, 619) (641, 643) 
(659, 661) (809, 811) (821, 823) (827, 829) (857, 859) (881, 883) (1019, 1021) (1031, 1033) (1049, 1051) 
(1061, 1063) (1091, 1093) (1151, 1153) (1229, 1231) (1277, 1279) (1289, 1291) (1301, 1303) (1319, 1321) 
(1427, 1429) (1451, 1453) (1481, 1483) (1487, 1489) (1607, 1609) (1619, 1621) (1667, 1669) (1697, 1699) 
(1721, 1723) (1787, 1789) (1871, 1873) (1877, 1879) (1931, 1933) (1949, 1951) (1997, 1999) (2027, 2029) 
(2081, 2083) (2087, 2089) (2111, 2113) (2129, 2131) (2141, 2143) (2237, 2239) (2267, 2269) (2309, 2311) 
(2339, 2341) (2381, 2383) (2549, 2551) (2591, 2593) (2657, 2659) (2687, 2689) (2711, 2713) (2729, 2731) 
(2789, 2791) (2801, 2803) (2969, 2971) (2999, 3001) (3119, 3121) (3167, 3169) (3251, 3253) (3257, 3259) 
(3299, 3301) (3329, 3331) (3359, 3361) (3371, 3373) (3389, 3391) (3461, 3463) (3467, 3469) (3527, 3529) 
(3539, 3541) (3557, 3559) (3581, 3583) (3671, 3673) (3767, 3769) (3821, 3823)