要素を一列に並べたデータ構造を「シーケンス (sequence)」とか「列」と呼びます。リスト、一次元配列 (ベクタ)、文字列などはシーケンスとして考えることができます。プログラミング言語によっては、これらのデータ型を列型 (sequence) として統一的に扱うことができるもの、たとえば Common Lisp や Clojure などがあります。
プログラミングの世界では、データの流れを抽象化したデータ構造を「ストリーム (stream)」といいます。たとえば、ファイル入出力はストリームと考えることができます。また、ベクタや連結リストを使ってストリームを表すこともできます。ただし、単純な配列や連結リストでは有限個のデータの流れしか表すことができません。
ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。Clojure にはシーケンスの要素を遅延評価する「遅延シーケンス (lazy-sequence)」が用意されています。今回は遅延シーケンスについて簡単に説明します。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成する関数を用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいた関数を呼び出して値を求めればよいわけです。
たとえば、拙作のページ Common Lisp 入門「遅延ストリーム」で作成したプログラムを Clojure で書き直すと次のようになります。
リスト : 遅延ストリーム (1) ;; 遅延ストリームの生成 (defmacro stream-cons [a b] `(list ~a (delay ~b))) ;; 先頭要素を参照する (defn stream-first [s] (first s)) ;; 先頭要素を取り除く (defn stream-rest [s] (force (rest s)))
マクロ stream-cons はリストの第 1 要素にストリームの要素 a を格納し、第 2 要素にプロミスを格納します。プロミスにはストリームを生成する関数 b を格納します。プロミスを force することで、次の要素を格納した遅延ストリームを生成します。ストリームの終端は () で表すことにします。
関数 stream-first は遅延ストリーム s から要素を取り出して返します。関数 stream-rest は s のプロミスを force して、次の要素を格納した遅延ストリームを生成して返します。ようするに、これらのマクロと関数はリスト操作の cons, first, rest に対応するわけです。
簡単な実行例を示します。
user=> (def a (stream-cons 1 (stream-cons 2 (stream-cons 3 '()))))
#'user/a
user=> a
(1 #object[clojure.lang.Delay 0x562c877a {:status :pending, :val nil}])
user=> (stream-first a)
1
user=> (stream-first (stream-rest a))
2
user=> a
(1 #object[clojure.lang.Delay 0x562c877a {:status :ready, :val
(2 #object[clojure.lang.Delay 0x748fe51d {:status :pending, :val nil}])}])
user=> (stream-first (stream-rest (stream-rest a)))
3
user=> a
(1 #object[clojure.lang.Delay 0x562c877a {:status :ready, :val
(2 #object[clojure.lang.Delay 0x748fe51d {:status :ready, :val
(3 #object[clojure.lang.Delay 0xaf78c87 {:status :pending, :val nil}])}])}])
user=> (stream-rest (stream-rest (stream-rest a)))
()
user=> a
(1 #object[clojure.lang.Delay 0x562c877a {:status :ready, :val
(2 #object[clojure.lang.Delay 0x748fe51d {:status :ready, :val
(3 #object[clojure.lang.Delay 0xaf78c87 {:status :ready, :val ()}])}])}])
このように stream-rest を順番に適用することで、新しい要素が生成されていきます。
ところで、stream-cons は遅延ストリームを生成するとき、ストリームの先頭になる要素を評価してしまいます。先頭要素が評価されると困る場合もあるでしょう。拙作のページ Scheme 入門「遅延ストリーム (3)」では、リストの第 1 要素と第 2 要素をまとめて遅延評価することで、先頭の要素が評価されることを回避しています。Clojure でプログラムすると、次のようになります。
リスト : 遅延ストリーム (2) ;; 遅延ストリームの生成 (defmacro stream-cons' [a b] `(delay (list ~a ~b))) ;; 先頭要素を参照する (defn stream-first' [s] (first (force s))) ;; 先頭要素を取り除く (defn stream-rest' [s] (second (force s)))
簡単な実行例を示します。
user=> (def a (stream-cons' 1 (stream-cons' 2 (stream-cons' 3 '()))))
#'user/a
user=> a
#object[clojure.lang.Delay 0x963176 {:status :pending, :val nil}]
user=> (stream-first' a)
1
user=> a
#object[clojure.lang.Delay 0x963176 {:status :ready, :val (1
#object[clojure.lang.Delay 0x444548a0 {:status :pending, :val nil}])}]
user=> (stream-first' (stream-rest' a))
2
user=> a
#object[clojure.lang.Delay 0x963176 {:status :ready, :val (1
#object[clojure.lang.Delay 0x444548a0 {:status :ready, :val (2
#object[clojure.lang.Delay 0x2dbd803f {:status :pending, :val nil}])}])}]
user=> (stream-first' (stream-rest' (stream-rest' a)))
3
user=> a
#object[clojure.lang.Delay 0x963176 {:status :ready, :val (1
#object[clojure.lang.Delay 0x444548a0 {:status :ready, :val (2
#object[clojure.lang.Delay 0x2dbd803f {:status :ready, :val (3 ())}])}])}]
user=> (stream-rest' (stream-rest' (stream-rest' a)))
()
Clojure の遅延シーケンスは遅延ストリーム (2) と同様の方法を採用しています。Clojure の場合、stream-cons に対応するマクロが lazy-seq で、stream-first, stream-rest に対応する関数が first, rest です。最初に、lazy-seq の基本的な使い方を説明します。
1. (lazy-seq coll) 2. (lazy-seq (cons item lazy-sequence))
1 は引数 coll を遅延シーケンスに変換します。coll は評価されないことに注意してください。2 も同様に、引数 (cons item lazy-sequence) は評価されません。遅延シーケンスの値を求めるとき、引数は 1 回だけ評価され、その結果がキャッシュされます。2 の場合、lazy-sequence には次の要素を格納した遅延シーケンスを生成する関数 (マクロ) を指定するのが一般的です。
簡単な例を示しましょう。
user=> (def a (lazy-seq '(1 2 3 4 5))) #'user/a user=> a (1 2 3 4 5) user=> (type a) clojure.lang.LazySeq user=> (type '(1 2 3 4 5)) clojure.lang.PersistentList user=> (def b (lazy-seq (list 1 2 3 4 5 (do (println "oops") 6)))) #'user/b user=> b (oops 1 2 3 4 5 6) user=> b (1 2 3 4 5 6)
変数 a に遅延シーケンスをセットします。このとき、引数 '(1 2 3 4 5) は評価されていません。変数 a にアクセスすると、引数 '(1 2 3 4 5) を評価して、その結果が遅延シーケンスに変換されます。REPL の場合、遅延シーケンスはリストと同じく ( ... ) で表示されますが、type でデータ型を調べると、a は遅延シーケンス (LazySeq) であることがわかります。無限シーケンスの場合、画面の表示も無限に続くので注意してください。
次の例では、変数 b に (lazy-seq (list 1 2 3 4 5 (do (println "oops") 6))) をセットします。このとき、lazy-seq の引数は評価されないので、oops は表示されません。最初に b にアクセスしたとき、引数 (list ...) が評価されて oops が表示されます。2 回目以降は、キャッシュされた値が返されます。
user=> (def c (lazy-seq (cons 1 (lazy-seq (cons 2 (lazy-seq (cons 3 '()))))))) #'user/c user=> (first a) 1 user=> (first (rest a)) 2 user=> (first (rest (rest a))) 3 user=> (rest (rest (rest a))) () user=> a (1 2 3)
リストを生成する関数 cons と同様に、lazy-seq をつなげて遅延シーケンスを生成することもできます。リストと同様に、遅延シーケンスは first, rest でアクセスすることができます。
それでは、遅延シーケンスを生成する関数を作りましょう。たとえば、start から end までの整数列を生成するシーケンスは次のようにプログラムすることができます。
リスト : 整数列の生成
(defn range' [start end]
(if (>= start end)
'()
(lazy-seq (cons start (range' (inc start) end)))))
Clojure には同様の機能を持つ関数 range が用意されているので、関数名は range' としました。range' は遅延シーケンスを生成して返します。引数 (cons ...) を評価すると、start と (range' (inc start) end) が評価されて、その結果を格納した遅延シーケンスが返されます。range' を再帰呼び出ししているように見えますが、そうではなく、遅延評価していることに注意してください。
簡単な実行例を示しましょう。
user=> (def a (range' 1 10)) #'user/a user=> (first a) 1 user=> (first (rest a)) 2 user=> (first (rest (rest a))) 3 user=> (first (rest (rest (rest a)))) 4 user=> a (1 2 3 4 5 6 7 8 9)
このように、遅延シーケンスの要素にアクセスすると、遅延評価されていた (cons ...) が評価されて、次々とデータを生成することができます。
もう一つ、簡単な例を示しましょう。フィボナッチ数列を生成する遅延シーケンスを作ります。次のリストを見てください。
リスト : フィボナッチ数列を生成する遅延シーケンス (defn fibonacci ([] (fibonacci 0N 1N)) ([a b] (lazy-seq (cons a (fibonacci b (+ a b))))))
関数 fibonacci の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、cons の第 2 引数に (fibonacci b (+ a b)) を格納しておけば、それを評価することでフィボナッチ数列を生成することができます。Clojure は多倍長整数をサポートしているので、メモリの許す限りフィボナッチ数列を生成することができます。
user=> (def b (fibonacci)) #'user/b user=> (first b) 0N user=> (first (rest b)) 1N user=> (first (rest (rest b))) 1N user=> (first (rest (rest (rest b)))) 2N user=> (first (rest (rest (rest (rest b))))) 3N
これらの関数の動作を一般化すると、次のような関数を定義することができます。
リスト : 遅延シーケンスの生成 (逆畳み込み)
(defn unfold
([iterate seed] (unfold iterate seed (fn [_] false)))
([iterate seed pred]
(if (pred seed)
'()
(lazy-seq (cons seed (unfold iterate (iterate seed) pred))))))
関数 unfold は初項 seed を受け取り、次項を関数 iterate で生成します。cons の第 1 引数に seed を渡して、第 2 引数で unfold を呼び出すときに (iterate seed) の返り値を渡します。引数 pred は終了条件を表す述語です。(pred seed) が真であればシーケンスの終端 () を返します。pred のデフォルトは無条件で false を返すので無限シーケンスになります。
簡単な実行例を示します。
user=> (def c (unfold inc 1)) #'user/c user=> (first c) 1 user=> (first (rest c)) 2 user=> (first (rest (rest c))) 3 user=> (first (rest (rest (rest c)))) 4 user=> (def d (unfold (fn [[a b]] (list b (+ a b))) '(0 1))) #'user/d user=> (first d) (0 1) user=> (first (rest d)) (1 1) user=> (first (rest (rest d))) (1 2) user=> (first (rest (rest (rest d)))) (2 3) user=> (first (rest (rest (rest (rest d))))) (3 5)
Clojure には unfold と同様の動作を行う関数 iterate が用意されています。
iterate は x, f(x), f(f(x)), ... を要素とする無限シーケンスを返します。簡単な使用例を示します。
user=> (def e (iterate (fn [[a b]] (list b (+ a b))) '(0 1))) #'user/e user=> (first e) (0 1) user=> (first (rest e)) (1 1) user=> (first (rest (rest e))) (1 2) user=> (first (rest (rest (rest e)))) (2 3) user=> (first (rest (rest (rest (rest e))))) (3 5)
次は遅延シーケンスを操作する関数を作りましょう。最初は n 番目の要素を求める関数 nth' です。Clojure の関数 nth は遅延シーケンスにも対応しているので、私たちが自作する必要はありませんが、Clojure のお勉強ということで、あえてプログラムを作ってみましょう。
リスト : n 番目の要素を求める
(defn nth' [s n]
(if (zero? n)
(first s)
(recur (rest s) (dec n))))
user=> (def b (fibonacci)) #'user/b user=> (dotimes [x 10] (println (nth' b (+ x 40)))) 102334155N 165580141N 267914296N 433494437N 701408733N 1134903170N 1836311903N 2971215073N 4807526976N 7778742049N nil user=> (nth' b 60) 1548008755920N user=> (nth' b 80) 23416728348467685N user=> (nth' b 100) 354224848179261915075N
nth' は rest でデータを生成し、それを n 回繰り返すことで n 番目の要素を求めます。rest は遅延シーケンスを返すことに注意してください。あとは、n が 0 になったら first でシーケンスの要素を取り出せばいいわけです。
シーケンスから n 個の要素を取り出してシーケンスに格納して返す関数 take' と、n 個の要素を取り除く関数 drop' も同様にプログラムすることができます。なお、Clojure の関数 take, drop は遅延シーケンスに対応しています。
リスト : 先頭から n 個の要素を取り出す
(defn take' [n s]
(if (or (not (seq s)) (zero? n))
'()
(lazy-seq (cons (first s) (take' (dec n) (rest s))))))
リスト : 先頭から n 個の要素を取り除く
(defn drop' [n s]
(if (or (not (seq s)) (zero? n))
s
(recur (dec n) (rest s))))
どちらの関数も引数 s が遅延シーケンスで、引数 n が要素の個数です。s が空になるか、n が 0 になるまで処理を繰り返します。take' は first で要素を取り出し、それを新しいシーケンスに追加して返します。take' は有限の遅延シーケンスを返すことに注意してください。drop' は rest を n 回繰り返すだけです。
簡単な実行例を示します。
user=> (def b (fibonacci)) #'user/b user=> (dotimes [x 10] (println (nth' b x))) 0N 1N 1N 2N 3N 5N 8N 13N 21N 34N nil user=> (take' 16 b) (0N 1N 1N 2N 3N 5N 8N 13N 21N 34N 55N 89N 144N 233N 377N 610N) user=> (take' 10 (drop' 20 b)) (6765N 10946N 17711N 28657N 46368N 75025N 121393N 196418N 317811N 514229N)
変数 b にフィボナッチ数列を生成するシーケンスをセットします。nth' で順番に要素を 10 個求めると、その値はフィボナッチ数列になります。同様に、take' で 16 個の要素を取り出すと、シーケンスの要素はフィボナッチ数列になります。drop' で 20 個の要素を取り除き、そのあと take' で 10 個の要素を取り出すと、21 番目以降のフィボナッチ数列を求めることができます。
次は、2 つの遅延シーケンスを受け取って 1 つの遅延シーケンスを返す関数を考えます。一番簡単な操作は 2 つの遅延シーケンスを結合することです。次のリストを見てください。
リスト : 遅延シーケンスの結合
(defn concat' [s1 s2]
(if-not (seq s1)
s2
(lazy-seq (cons (first s1)
(concat' (rest s1) s2)))))
Clojure にはシーケンスを連結する関数 concat があるので、名前を concat' としました。concat' はシーケンス s1 と s2 を結合したシーケンスを返します。処理は簡単で、s1 の要素を順番に取り出していき、s1 が空になったら s2 を返すだけです。
簡単な実行例を示しましょう。
user=> (range' 1 5) (1 2 3 4) user=> (range' 5 9) (5 6 7 8) user=> (concat' (range' 1 5) (range 5 9)) (1 2 3 4 5 6 7 8)
次は遅延シーケンス s1 と s2 の要素を交互に出力するシーケンスを作ります。次のリストを見てください。
リスト : 遅延シーケンスの要素を交互に出力
(defn interleave' [s1 s2]
(if-not (seq s1)
s2
(lazy-seq (cons (first s1)
(interleave' s2 (rest s1))))))
Clojure には同様の機能を持つ関数 interleave が用意されているので、名前を interleave' としました。interleave' はシーケンス s1 と s2 を受け取ります。そして、s1 の要素を新しい遅延シーケンスに格納したら、次は s2 の要素を新しい遅延シーケンスに格納します。これは lazy-seq で interleave' を呼び出すとき、引数 s1 と s2 の順番を交換するだけです。このとき、s1 は rest で次の要素を求めます。これで s1 と s2 の要素を交互に出力することができます。
簡単な実行例を示しましょう。
user=> (interleave' (range 1 5) (range 5 9)) (1 5 2 6 3 7 4 8)
concat' の場合、無限シーケンスを結合することはできませんが、interleave’ ならば無限シーケンスにも対応することができます。簡単な例を示しましょう。
user=> (def ones (lazy-seq (cons 1 ones))) #'user/ones user=> (take' 10 ones) (1 1 1 1 1 1 1 1 1 1) user=> (def twos (lazy-seq (cons 2 twos))) #'user/twos user=> (take' 10 twos) (2 2 2 2 2 2 2 2 2 2) user=> (take' 10 (interleave' ones twos)) (1 2 1 2 1 2 1 2 1 2)
ones は 1 を無限に出力するシーケンスで、twos は 2 を無限に出力するシーケンスです。concat' で ones と twos を結合しても無限に 1 を出力するだけですが、interleave で ones と twos を結合すれば、1 と 2 を交互に出力することができます。これで無限シーケンスの要素を混ぜ合わせることができます。
次は遅延シーケンス用の高階関数を作りましょう。
リスト : 高階関数
;; マッピング
(defn map' [proc s]
(if-not (seq s)
'()
(lazy-seq (cons (proc (first s))
(map' proc (rest s))))))
;; フィルター
(defn filter' [pred s]
(cond
(not (seq s)) '()
(pred (first s)) (lazy-seq (cons (first s) (filter' pred (rest s))))
:else (filter' pred (rest s))))
;; 畳み込み
(defn fold-left [proc a s]
(if-not (seq s)
a
(recur proc (proc a (first s)) (rest s))))
(defn fold-right [proc a s]
(if-not (seq s)
a
(proc (first s) (fold-right proc a (rest s)))))
;; 累積値を格納した遅延シーケンスを返す
(defn scan-left [proc a s]
(lazy-seq (cons a (if-not (seq s)
'()
(scan-left proc (proc (first s) a) (rest s))))))
;; 巡回
(defn for-each [proc s]
(when (seq s)
(proc (first s))
(recur proc (rest s))))
Clojure の map と filter は遅延シーケンスに対応しています。map' は引数のシーケンスの要素に関数 proc を適用した結果を新しいシーケンスに格納して返します。filter' は述語 pred が真を返す要素だけを新しいシーケンスに格納して返します。
fold-left と fold-right は遅延シーケンスに対して畳み込み処理を行います。これは拙作のページ「高階関数と無名関数」で作成した foldl, foldr と同じです。for-each は遅延シーケンスの要素に関数 proc を適用します。無限シーケンスの場合、これらの関数は処理が終了しないので注意してください。
scan-left は遅延シーケンス s の先頭から畳み込みを行い、計算途中の累積値を格納した遅延シーケンスを返します。fold-left と違って、s が無限シーケンスでも動作します。
簡単な実行例を示しましょう。
user=> (def s1 (unfold inc 1)) #'user/s1 user=> (def s2 (map' #(* % %) s1)) #'user/s2 user=> (take' 10 s2) (1 4 9 16 25 36 49 64 81 100) user=> (def s3 (filter' even? s1)) #'user/s3 user=> (take' 10 s3) (2 4 6 8 10 12 14 16 18 20) user=> (fold-left + 0 (take' 10 s1)) 55 user=> (fold-right + 0 (take' 10 s1)) 55 (for-each println (take' 10 s1)) 1 2 3 4 5 6 7 8 9 10 nil user=> (def s4 (scan-left + 0 s1)) #'user/s4 user=> (take' 20 s4) (0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190) user=> (take' 20 (scan-left * 1 s1)) (1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000)
変数 s1 に 1 から始まる整数列を生成する遅延シーケンスをセットします。次に、s1 の要素を 2 乗する遅延シーケンスを map' で生成して変数 s2 にセットします。take' で s2 から要素を 10 個取り出すと、s1 の要素を 2 乗した値になります。
s1 から偶数列の遅延シーケンスを得るには、引数が偶数のときに真を返す述語を filter' に渡します。その返り値を変数 s3 にセットして、take' で 10 個の要素を取り出すと、リストの要素は 2 から 20 までの値になります。
take' で有限個の遅延シーケンスを生成すると畳み込みを行うことができます。fold-left と fold-right で要素の合計値を求めると 55 になります。もちろん、for-each も正常に動作します。
scan-left に関数 + と初期値 0 を渡すと、s1 の累積度数を求めることができます。関数 * と初期値 1 と s1 を渡すと、階乗の数列を生成することができます。
ところで、Clojureの map は複数の遅延シーケンスを受け取ることができるので、それらの遅延シーケンスに対していろいろな処理を定義することができます。次の例を見てください。
user=> (defn add-seq [s1 s2] (map + s1 s2)) #'user/add-stream user=> (add-seq (range 1 5) (range 11 15)) (12 14 16 18)
add-seq は s1 と s2 の要素を加算した遅延シーケンスを返します。この add-seq を使うと、整数を生成する遅延シーケンスは次のように定義することができます。
user=> (def ones (lazy-seq (cons 1 ones))) #'user/ones user=> (def int-seq (lazy-seq (cons 1 (add-seq ones int-seq)))) #'user/int-seq user=> (take 10 int-seq) (1 2 3 4 5 6 7 8 9 10) user=> (def fibo-seq (lazy-seq (cons 0 (lazy-seq (cons 1 (add-seq (rest fibo-seq) fibo-seq)))))) #'user/fibo-seq user=> (take 20 fibo-seq) (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
シーケンス int-seq は、現在の int-seq に 1 を足し算することで整数を生成しています。fib-seq は現在のフィボナッチ数列を表していて、(rest fibs) で次の要素を求め、それらを足し算することで、その次の要素を求めています。この場合、シーケンスの初期値として 2 つの要素が必要になることに注意してください。
なお、scan-left を使ってもフィボナッチ数列を定義することができます。
user=> (def fibo-seq1 (lazy-seq (cons 0 (scan-left + 1 fibo-seq1)))) #'user/fibo-seq1 user=> (take 20 fibo-seq1) (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
次は高階関数 flatmap を作りましょう。flatmap は map の結果を平坦化する関数で、具体的には map が返すリストの要素を concat で連結する動作になります。Clojure には遅延シーケンスにも対応する関数 mapcat が用意されています。flatmap は拙作のページ「クロージャ」の問題 1 で作成したことがあります。引数がリストの場合、次のように定義することができます。
リスト : マッピングした結果を平坦化する (defn flatmap [proc xs] (apply concat (map proc xs)))
apply を使ってリストの要素を concat でつなげば、リストを一段階だけ平坦化することができます。
簡単な実行例を示します。
user=> (flatmap #(list % %) '(1 2 3 4 5)) (1 1 2 2 3 3 4 4 5 5) user=> (flatmap #(repeat % %) '(1 2 3 4 5)) (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5)
遅延シーケンスに対応する場合、次のように concat' を使うと問題が発生します。
リスト : stream-flatmap の定義 (間違い)
(defn flatmap' [proc s]
(if-not (seq s)
'()
(concat' (proc (first s))
(flatmap' proc (rest s)))))
Clojure の関数は正格評価なので、concat' を実行する前に引数が評価されます。つまり、flatmap' の評価は遅延されるのではなく、遅延シーケンスが空になるまで flatmap' が再帰呼び出しされるのです。これでは無限シーケンスに対応することができません。
そこで、引数を遅延評価する関数 concat-delay を作ることにします。プログラムは次のようになります。
リスト : concat-delay と flatmap''
;; 遅延シーケンスの連結 (遅延評価版)
(defn concat-delay [s1 s2]
(if-not (seq s1)
(force s2)
(lazy-seq (cons (first s1)
(concat-delay (rest s1) s2)))))
;; マッピングの結果を平坦化する
(defn flatmap'' [proc s]
(if-not (seq s)
'()
(concat-delay (proc (first s))
(delay (flatmap'' proc (rest s))))))
concat-delay は concat' とほぼ同じですが、遅延シーケンス s1 が空になったらプロミス s2 を force で評価するところが異なります。flatmap'' では、concat' のかわりに concat-delay を使います。このとき、delay で生成したプロミスを引数に渡します。
それでは実行してみましょう。
user=> (def s1 (unfold inc 1)) #'user/s1 user=> (take 10 s1) (1 2 3 4 5 6 7 8 9 10) user=>(def s2 (flatmap'' #(range 1 %) s1)) #'user/s2 user=>(take 52 s2) (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7)
s1 は無限ストリームになりますが、flatmap'' は正常に動作していますね。
次は、遅延シーケンスの先頭から述語が真を返す要素を取り出す take-while と要素を取り除く drop-while を作ります。これらの関数は Clojure に定義されているので、名前を take-while' と drop-while' とします。
リスト : take-while' と drop-while'
;; 述語 pred が真を返す要素を取り出す
(defn take-while' [pred s]
(if-not (pred (first s))
'()
(lazy-seq (cons (first s)
(take-while' pred (rest s))))))
;; 述語 pred が真を返す要素を取り除く
(defn drop-while' [pred s]
(if-not (pred (first s))
s
(recur pred (rest s))))
どちらの関数も難しいところはないと思います。簡単な実行例を示しましょう。
user=> (def s1 (unfold inc 1)) #'user/s1 user=> (take-while' #(< % 10) s1) (1 2 3 4 5 6 7 8 9) user=> (take 10 (drop-while' #(< % 10) s1)) (10 11 12 13 14 15 16 17 18 19)
次は、2 つのシーケンスからその要素の組み合わせを生成するシーケンスを作りましょう。要素が n 個のシーケンスの場合、組み合わせは n * n 個あります。次の図を見てください。
(a0, b0) (a0, b1) (a0, b2) ... (a0, bn)
(a1, b0) (a1, b1) (a1, b2) ... (a1, bn)
(a2, b0) (a2, b1) (a2, b2) ... (a2, bn)
...
(an, b0) (an, b1) (an, b2) ... (an, bn)
図 : n * n 個の組
これは「直積集合」を求めることと同じです。遅延シーケンスが有限であれば、リスト内包表記 (for) を使って簡単にプログラムできます。
(for [x (range 1 5) y (range 5 9)] (list x y)) ((1 5) (1 6) (1 7) (1 8) (2 5) (2 6) (2 7) (2 8) (3 5) (3 6) (3 7) (3 8) (4 5) (4 6) (4 7) (4 8))
ところが、この方法では無限シーケンスに対応できません。実際、y に無限シーケンス s2 を渡した場合、x に渡す遅延シーケンス s1 の先頭要素を a0 とすると、(a0 s2の要素) という組しか生成されません。実際に試してみましょう。
user=> (take 16 (for [x (range 1 5) y (unfold inc 5)] (list x y))) ((1 5) (1 6) (1 7) (1 8) (1 9) (1 10) (1 11) (1 12) (1 13) (1 14) (1 15) (1 16) (1 17) (1 18) (1 19) (1 20))
| a0 a1 a2 a3 a4 a5 ---+----------------------------- b0 | 0 1 3 6 10 15 ... | b1 | 2 4 7 11 16 ... | b2 | 5 8 12 17 ... | b3 | 9 13 18 ... | b4 | 14 19 ... | b5 | 20 ... | | ... 図 : 無限シーケンスによる組の生成
そこで、上図に示すように、対角線上に組を生成していくことにします。
図を見ればおわかりのように、対角線の要素数を n とすると、組は (an-1 b0), (an-2 b1), ..., (a1 bn-2), (a0 bn-1) となっています。これは、s1 から n 個の要素を取り出したリストと、s2 から n 個の要素を取り出して反転したリストを zip でまとめた形になっています。プログラムは次のようになります。
リスト : 組の生成
(defn pair-seq
([s1 s2] (pair-seq s1 s2 1))
([s1 s2 n]
(concat-delay
(map #(list %1 %2) (take n s1) (reverse (take n s2)))
(delay (pair-seq s1 s2 (inc n))))))
関数 pair-stream の引数 n が対角線上の要素数を表します。s1 から n 個の要素を take で取り出し、s2 から取り出したリストを reverse で反転し、それらを map に渡して組を生成します。あとは、concat-delay で map と pair-stream を連結すればいいわけです。これで無限シーケンスに対応することができます。
それでは実行してみましょう。
(def ps (pair-seq (unfold inc 1) (unfold inc 1))) #'user/ps user=> (take 55 ps) ((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)) user=> (nth ps 10) (1 5) user=> (nth ps 54) (10 1) user=> (nth ps 100) (10 5)
正常に動作していますね。