今回は「遅延評価」と「遅延ストリーム」について説明します。
遅延評価の例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数 fun tarai(x, y, z) = if x <= y then y else tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) fun tak(x, y, z) = if x <= y then z else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。
関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Windows 10, Intel Core i5-6200U 2.30GHz, SML/NJ ver 110.98 です。
tarai(14, 7, 0) : 2.81 [s] tak(22, 11, 0) : 3.64 [s]
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
関数 tarai は「遅延評価 (delayed evaluation または lazy evaluation)」を行う処理系、たとえば関数型言語の Haskell では高速に実行することができます。また、Scheme でも delay と force を使って遅延評価を行うことができます。
tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。
標準的な Standard ML の場合、遅延評価のサポートはありませんが、SML/NJ では独自の拡張として Scheme のような遅延評価を行うモジュール SMLofNJ.Susp が用意されています。また、モジュール Control にある変数 lazysml を true にセットすると、キーワード lazy を使って遅延評価を行うことができます。
なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。
まず最初に、モジュール SMLofNJ.Susp に用意されている関数 delay と force を説明します。
delay は型 unit -> 'a を持つ関数を受け取り、その関数を評価しないで 'a susp という型を持つデータを返します。このデータを遅延オブジェクトと呼ぶことにします。関数はこの遅延オブジェクトに保存されていて、force を実行すると関数を評価してその値を返します。このとき、値が遅延オブジェクトに保存されることに注意してください。再度 force を実行すると、保存された値が返されます。
簡単な使用例を示しましょう。
- open SMLofNJ.Susp;
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[library $SMLNJ-BASIS/(basis.cm):basis-common.cm is stable]
[autoloading done]
opening SMLofNJ.Susp
type'a susp = 'a ?.Susp.susp
val delay : (unit -> 'a) -> 'a susp
val force : 'a susp -> 'a
- val s = delay (fn () => (print "oops!\n"; 10 + 20));
val s = - : int susp
- force s;
oops!
val it = 30 : int
- force s;
val it = 30 : int
delay (fn () => (print "oops!\n"; 10 + 20)) の返り値を変数 s にセットします。このとき、匿名関数はまだ評価されていません。force s を評価すると、匿名関数を評価して値 30 を返します。このとき、画面に oops! が表示されます。次に、force s を再度実行すると、同じ匿名関数を再評価することなく値を求めることができます。つまり、遅延オブジェクトに保存された値 30 が返されるので、画面に oops! は表示されません。
このように、delay に渡すデータは匿名関数 (クロージャ) になります。そして、遅延オブジェクトを force で評価すると、格納されている匿名関数が実行されるわけです。
次は lazy の基本的な使い方について説明します。Control.lazysml に true をセットして、モジュール Lazy をオープンします。
- Control.lazysml := true;
[autoloading]
・・・省略・・・
[autoloading done]
val it = () : unit
- open Lazy;
[autoloading]
[autoloading done]
opening Lazy
datatype'a susp = $ of 'a
lazysml の設定は sml を起動するときにコマンドラインから指定することもできます。
C>sml -Cparser.lazy-keyword=true
Standard ML of New Jersey (32-bit) v110.98 [built: Fri Jul 17 15:16:19 2020]
- Control.lazysml;
[autoloading]
・・・省略・・・
[autoloading done]
val it = ref true : bool ref
- open Lazy;
[autoloading]
[autoloading done]
opening Lazy
datatype'a susp = $ of 'a
lazy キーワードは val, val rec, datatype の後ろに記述することができます。また、fun は val, val rec の糖衣構文なので、fun の後ろにも lazy を記述することができます。val, val rec で lazy を指定すると、その変数の型は遅延オブジェクト ('a susp) になります。Lazy モジュールにある $ が遅延オブジェクトのコンストラクタです。右辺で "$ 式" を指定すると、遅延オブジェクトが生成されますが、このとき、式の評価が遅延されることに注意してください。
簡単な例を示しましょう。
- val lazy s = $ (print "oops!\n"; 10 + 20); val s = $$ : int susp - val ($ a) = s; oops! val a = 30 : int - val ($ b) = s; val b = 30 : int
$ に式 (print "oops!"; 10 + 20) を渡して遅延オブジェクトを生成して変数 s にセットします。変数 s には lazy が指定されているので、式はすぐに評価されません。s を ($ a) をマッチングすると、遅延オブジェクトに格納されている式が評価され、画面に oops! が表示されて a の値は 30 になります。評価結果は遅延オブジェクトに保存されるので、val ($ b) = s を実行すると、b の値は 30 になりますが、oops! は画面に表示されません。
次に示すように、遅延オブジェクトから値を求める関数 force を用意しておくと便利だと思います。それから、"$ 式" は遅延オブジェクトを生成しますが、lazy を指定しないと遅延評価が行われません。次の例を見てください。
- fun force ($ x) = x; val force = fn : 'a susp -> 'a - force s; val it = 30 : int - val s1 = $ (print "oops!\n"; 10 + 20); oops! val s1 = $$ : int susp - force s1; val it = 30 : int
変数 s1 には lazy の指定がないので、$ の評価と一緒に式も評価されます。その結果、画面に oops! が表示され、遅延オブジェクトには 10 + 20 の計算結果 30 が格納されます。
fun の後ろに lazy をつけると、その返り値のデータ型は遅延オブジェクトになります。そして、返り値を評価するとき、$ に渡した式が遅延評価されます。次の例を見てください。
- fun lazy foo(a, b) = $ (print "oops!\n"; a + b); val foo = fn : int * int -> int susp val foo_ = fn : int * int -> int - val a = foo(10, 20); val a = $$ : int susp - force a; oops! val it = 30 : int - force a; val it = 30 : int
関数 foo は lazy が指定されているので、返り値のデータ型は遅延オブジェクト (int susp) になります。このとき、$ に渡した式は遅延評価されることになります。foo の返り値を変数 a にセットし、force で評価すると画面に oops! が表示され、式 10 + 20 が計算されます。再度 force a を評価すると、遅延オブジェクトにキャッシュされた結果 30 が得られます。
datatype で lazy を指定すると、コンストラクタで生成したデータは遅延オブジェクトになります。つまり、"$ (コンストラクタ 式)" と記述しなくても、"コンストラクタ 式" で遅延オブジェクトを生成することができます。
簡単な例を示しましょう。
- datatype lazy lazy_int = LazyInt of int; datatype lazy_int! = LazyInt of int type lazy_int = lazy_int! susp - val lazy s = LazyInt(print "oops!\n"; 100 + 200); val s = $$ : lazy_int! susp - force s; oops! val it = LazyInt 300 : lazy_int! - force s; val it = LazyInt 300 : lazy_int! - val lazy s1 = LazyInt(print "oops!\n"; 10 + 20); val s1 = $$ : lazy_int! susp - val LazyInt n1 = s1; oops! val n1 = 30 : int - val LazyInt n2 = s1; val n2 = 30 : int - fun lazy foo1(a, b) = LazyInt(print "oops!\n"; a + b); val foo1 = fn : int * int -> lazy_int! susp val foo1_ = fn : int * int -> lazy_int! - val b = foo1(100, 200); val b = $$ : lazy_int! susp - force b; oops! val it = LazyInt 300 : lazy_int! - force b; val it = LazyInt 300 : lazy_int!
datatype で lazy_int を定義します。lazy を指定しているので、コンストラクタ LazyInt で生成したデータは遅延オブジェクトになります。したがって、lazy を指定した変数 s に lazy_int をセットすると、コンストラクタに渡した式の評価が遅延されます。遅延オブジェクトを評価するとき force を使ってもかまいませんが、LazyInt とパターンマッチングすれば、遅延オブジェクト内の式が評価されて値を求めることができます。また、関数 foo1 で lazy を指定した場合、LazyInt で生成したデータを返すとき、LazyInt に渡した式の評価が遅延されます。
lazy の使い方は、eldesh さんの「SML/NJで遅延リスト(再び)」を参考にさせていただきました。SML の情報を公開されている eldesh さんに感謝いたします。
それでは、Shiro さんの WiLiKi にある「Scheme:たらいまわしべんち」を参考に、プログラムを作ってみましょう。
delay と force を使うと、たらいまわし関数は次のようになります。
リスト : delay と force による遅延評価
fun tarai1(x, y, z) =
if x <= y then y
else
let
val zz = force z
in
tarai1(tarai1(x - 1, y, z),
tarai1(y - 1, zz, delay (fn() => x)),
delay (fn() => tarai1(zz - 1, x, delay (fn() => y))))
end
val tarai1 = fn : int * int * int susp -> int
遅延評価したい処理を遅延オブジェクトにして引数 z に渡します。そして、x > y のときに引数 z の遅延オブジェクトを force で評価します。すると、遅延オブジェクト内の処理が評価されて z の値を求めることができます。たとえば、delay (fn() => 0) を z に渡す場合、force z とすると返り値は 0 になります。delay (fn() => x) を渡せば、x に格納されている値が返されます。delay (fn() => tarai1( ... )) を渡せば tarai1 が実行されて、その値を求めることができます。
ところで、delay と force がなくても、クロージャを使って遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
fun tarai2(x, y, z) =
if x <= y then y
else
let
val zz = z ()
in
tarai2(tarai2(x - 1, y, fn() => zz),
tarai2(y - 1, zz, fn() => x),
fn() => tarai2(zz - 1, x, fn() => y))
end
val tarai2 = fn : int * int * (unit -> int) -> int
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、fn () => 0 を z に渡す場合、z () とすると返り値は 0 になります。fn () => x を渡せば、x に格納されている値が返されます。fn () => tarai2( ... ) を渡せば、関数 tarai2 が実行されてその値が返されるわけです。
ただし、クロージャでは評価結果を保存できないことに注意してください。たとえば、fn() => zz を渡すところで、z をそのまま渡すこともできますが、z を評価するとき同じ計算を繰り返すことになり、実行速度は遅くなります。逆に、遅延オブジェクトを使う場合は、zz の値を使って新しい遅延オブジェクトを生成するよりも、z をそのまま渡したほうが速くなります。
lazy を使ったプログラムは次のようになります。
リスト : lazy による遅延評価
fun tarai3(x, y, z) =
if x <= y then y
else
let
val zz = force z
val lazy lz = $ (tarai3(zz - 1, x, $ y))
in
tarai3(tarai3(x - 1, y, z), tarai3(y - 1, zz, $ x), lz)
end
val tarai3 = fn : int * int * int susp -> int
遅延評価したい処理を遅延オブジェクトにして引数 z に渡し、x > y のときに引数 z の遅延オブジェクトを force で評価するところは同じです。関数 tarai3 の第 3 引数に渡す遅延オブジェクトを生成するため、変数 lz に lazy を付加して、$ (tarai3(zz - 1, x, $ y)) を評価します。これで $ に渡した式の評価が遅延されます。
すべての引数を遅延評価にすることも簡単です。次のリストを見てください。
リスト : lazy による遅延評価 (2)
fun tarai4(x, y, z) =
let
fun lazy tarai(x, y, z) =
if force x <= force y then y
else tarai(tarai($ ((force x) - 1), y, z),
tarai($ ((force y) - 1), z, x),
tarai($ ((force z) - 1), x, y))
in
force (tarai($ x, $ y, $ z))
end
val tarai4 = fn : int * int * int -> int
実際の処理は局所関数 tarai で行います。tarai の返り値は lazy なので、関数の型は int susp * int susp * int susp -> int susp になります。実際の値が必要になったとき、force で遅延オブジェクトを評価して値を取り出します。tarai は int susp を返すので、最後に force で返り値から値を取り出すことに注意してください。
それでは、実際に実行してみましょう。実行環境は Windows 10, Intel Core i5-6200U 2.30GHz, SML/NJ ver 110.98 です。
tarai1(3000, 1500, 0) : 109 msec tarai2(3000, 1500, 0) : 62 msec tarai3(3000, 1500, 0) : 109 msec tarai4(3000, 1500, 0) : 828 msec
クロージャの方が delay と force よりも少しだけ速いですね。delay と force は処理が複雑になる分だけ、クロージャを使った遅延評価よりも実行速度は少し遅くなるようです。また、すべての引数を遅延評価する tarai4 は、他の関数よりも遅くなりました。余分な処理が増えるので、実行速度が遅くなるのは仕方がないと思います。それでも実行速度は十分に高速なので、遅延評価の効果は絶大であることがわかります。
ところで、遅延評価やクロージャを使わなくても、関数 tarai を高速化する方法があります。C++:language&libraries (cppll) (リンク切れ) で Akira Higuchi さんが書かれたＣ言語の tarai 関数はとても高速です。SML/NJ でプログラムすると次のようになります。
リスト : tarai の遅延評価
fun tarai5(x, y, z) =
if x <= y then y
else tarai5_lazy(tarai5(x - 1, y, z), tarai5(y - 1, z, x), z - 1, x, y)
and tarai5_lazy(x, y, xx, yy, zz) =
if x <= y then y
else
let
val z = tarai5(xx, yy, zz)
in
tarai5_lazy(tarai5(x - 1, y, z), tarai5(y - 1, z, x), z - 1, x, y)
end
関数 tarai5_lazy の引数 xx, yy, zz で z の値を表すところがポイントです。つまり、z の計算に必要な値を引数に保持し、z の値が必要になったときに tarai5(xx, yy, zz) で計算するわけです。実際に実行してみると tarai5(3000, 1500, 0) は 47 [msec] になりました。Akira Higuchi さんに感謝いたします。
「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、リストを使ってストリームを表すこともできます。ただし、単純なリストでは有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成する関数を用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいた関数を呼び出して値を求めればよいわけです。
遅延ストリームのデータ型は次のようになります。
リスト : 遅延ストリームのデータ型 open SMLofNJ.Susp (* 例外 *) exception Empty_stream (* データ型 *) datatype 'a stream = Nils | Cons of 'a * 'a stream susp (* アクセス関数 *) fun stream_head (Cons(x, _)) = x | stream_head Nils = raise Empty_stream fun stream_tail (Cons(_, s)) = force s | stream_tail Nils = raise Empty_stream
val stream_head = fn : 'a stream -> 'a val stream_tail = fn : 'a stream -> 'a stream
データ型は 'a stream としました。Nils はストリームの終端を表します。無限ストリームだけを扱うのであれば Nils は必要ありません。Cons が遅延ストリームの本体を表していて、組の最初の要素が現時点での先頭データを表し、次の要素が遅延ストリームを生成する関数を格納する遅延オブジェクト (susp) です。この要素を force することで、次の要素を格納した遅延ストリームを生成します。
関数 stream_head は Cons の第 1 要素を返します。stream_head は Cons の第 2 要素を force して、新しい遅延ストリームを生成して返します。ようするに、Cons, stream_head, stream_tail はリストのコンス演算子, head, tail に対応するわけです。
それでは、遅延ストリームを生成する関数を作りましょう。たとえば、low から high までの整数列を生成するストリームは次のようにプログラムすることができます。
リスト : 整数列を生成するストリーム
fun range(low, high) =
if low > high then Nils
else Cons (low, delay (fn() => range(low + 1, high)))
関数 range は遅延ストリームを生成して返します。Cons の第 1 要素が現時点でのデータになります。第 2 要素の遅延オブジェクトを force すると、range(low + 1, high) が実行されて次のデータを格納した遅延ストリームが返されます。そして、その中の遅延オブジェクトを force すると、その次のデータを得ることができます。
関数 range の型は次のようになります。
val range = fn : int * int -> int stream
簡単な例を示しましょう。
- val s = range(1, 10); val s = Cons (1,-) : int stream - stream_head s; val it = 1 : int - stream_head (stream_tail s); val it = 2 : int - stream_head (stream_tail (stream_tail s)); val it = 3 : int - stream_head (stream_tail (stream_tail (stream_tail s))); val it = 4 : int
このように、stream_tail で第 2 要素の遅延オブジェクトを force することで、次々とデータを生成することができます。
もう一つ、簡単な例を示しましょう。フィボナッチ数列を生成する遅延ストリームを作ります。次のリストを見てください。
リスト : フィボナッチ数列を生成する遅延ストリーム fun fibo(a, b) = Cons(a, delay (fn() => fibo(b, a + b)))
関数 fibo の型は次のようになります。
val fibo = fn : int * int -> int stream
関数 fibo の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、遅延オブジェクトに fibo(b, a + b) を格納しておけば、force することでフィボナッチ数列を生成することができます。なお、この関数は無限ストリームを生成しますが、SML/NJ の整数 (int) には上限値があるので、際限なくフィボナッチ数列を生成できるわけではありません。ご注意ください。
簡単な実行例を示します。
- val f = fibo(0, 1); val f = Cons (0,-) : int stream - stream_head f; val it = 0 : int - stream_head (stream_tail f); val it = 1 : int - stream_head (stream_tail (stream_tail f)); val it = 1 : int - stream_head (stream_tail (stream_tail (stream_tail f))); val it = 2 : int - stream_head (stream_tail (stream_tail (stream_tail (stream_tail f)))); val it = 3 : int - stream_head (stream_tail (stream_tail (stream_tail (stream_tail (stream_tail f))))); val it = 5 : int
次は遅延ストリームを操作する関数を作りましょう。最初は n 番目の要素を求める関数 stream_ref です。今回は先頭の要素を 1 番目とします。
リスト : n 番目の要素を求める fun stream_ref(Nils, _) = raise Empty_stream | stream_ref(Cons(x, _), 1) = x | stream_ref(Cons(_, tail), n) = stream_ref(force tail, n - 1)
関数 stream_ref の型は次のようになります。
val stream_ref = fn : 'a stream * int -> 'a
stream_ref は Cons の第 2 要素 tail を force してデータを生成し、それを n 回繰り返すことで n 番目の要素を求めます。force tail は遅延ストリームを返すことに注意してください。あとは、stream_ref を n 回再帰呼び出しすればいいわけです。
ストリームから n 個の要素を取り出してリストに格納して返す関数 stream_take も同様にプログラムすることができます。
リスト : n 個の要素を取り出す fun stream_take(Nils, _) = raise Empty_stream | stream_take(Cons(x, _), 1) = [x] | stream_take(Cons(x, tail), n) = x :: stream_take(force tail, n - 1)
関数 stream_take の型は次のようになります。
val stream_take = fn : 'a stream * int -> 'a list
stream_take を再帰呼び出ししてストリームのデータ x を生成します。そして、n が 1 の場合はリスト [x] を返し、そうでなければ x を stream_ref の返り値 (リスト) に追加します。
それでは、簡単な実行例を示しましょう。
- val s1 = fibo(0, 1); val s1 = Cons (0,-) : int stream - let val i = ref 1 in while !i <= 10 do (print(Int.toString(stream_ref(s1, !i)) ^ "\n"); i := !i + 1) end; 0 1 1 2 3 5 8 13 21 34 val it = () : unit - stream_take(s1, 10); val it = [0,1,1,2,3,5,8,13,21,34] : int list
変数 s1 にフィボナッチ数列を生成するストリームをセットします。stream_ref で順番に要素を 10 個取り出すと、その値はフィボナッチ数列になっていますね。同様に、stream_take で 10 個の要素を取り出すと、リストの要素はフィボナッチ数列になります。
ところで、遅延ストリームは高階関数も定義することができます。次のリストを見てください。
リスト : 高階関数
(* マッピング *)
fun stream_map _ Nils = Nils
| stream_map proc (Cons(x, tail)) =
Cons (proc x, delay (fn() => (stream_map proc (force tail))))
(* フィルター *)
fun stream_filter _ Nils = Nils
| stream_filter pred (Cons(x, tail)) =
if pred x then Cons(x, delay (fn() => stream_filter pred (force tail)))
else stream_filter pred (force tail)
(* 畳み込み *)
fun stream_foldl _ a Nils = a
| stream_foldl proc a (Cons(x, tail)) =
stream_foldl proc (proc(x, a)) (force tail)
fun stream_foldr _ a Nils = a
| stream_foldr proc a (Cons(x, tail)) =
proc(x, stream_foldr proc a (force tail))
関数の型は次のようになります。
val stream_map = fn : ('a -> 'b) -> 'a stream -> 'b stream
val stream_filter = fn : ('a -> bool) -> 'a stream -> 'a stream
val stream_foldl = fn : ('a * 'b -> 'b) -> 'b -> 'a stream -> 'b
val stream_foldr = fn : ('a * 'b -> 'b) -> 'b -> 'a stream -> 'b
stream_map と stream_filter は関数と遅延ストリームを受け取り、新しい遅延ストリームを生成して返します。stream_map は引数のストリームの要素に関数 proc を適用した結果を新しいストリームに格納して返します。stream_filter は述語 pred が真を返す要素だけを新しいストリームに格納して返します。
stream_foldl と stream_foldr は遅延ストリームに対して畳み込み処理を行います。無限ストリームの場合は処理が終了しないので注意してください。
簡単な実行例を示しましょう。
- val s1 = range(1, 100); val s1 = Cons (1,-) : int stream - val s2 = stream_map (fn(x) => x * x) s1; val s2 = Cons (1,-) : int stream - stream_take(s2, 10); val it = [1,4,9,16,25,36,49,64,81,100] : int list - val s3 = stream_filter (fn(x) => x mod 2 = 0) s1; val s3 = Cons (2,-) : int stream - stream_take(s3, 10); val it = [2,4,6,8,10,12,14,16,18,20] : int list - stream_foldl (op +) 0 s1; val it = 5050 : int - stream_foldr (op +) 0 s1; val it = 5050 : int
変数 s1 に 1 から始まる整数列を生成するストリームをセットします。次に、s1 の要素を 2 乗するストリームを stream_map で生成して変数 s2 にセットします。stream_take で s2 から要素を 10 個取り出すと、s1 の要素を 2 乗した値になります。
s1 から偶数列のストリームを得るには、引数が偶数のときに真を返す述語を stream_filter に渡します。その返り値を変数 s3 にセットして、stream_take で 10 個の要素を取り出すと、リストの要素は 2 から 20 までの値になります。
s1 は有限個の遅延ストリームなので畳み込みを行うことができます。stream_foldl と stream_foldr で要素の合計値を求めると 5050 になります。
今回はここまでです。次回は遅延ストリームを使って素数や順列を求めてみましょう。
(*
* delay.sml : 遅延ストリーム
*
* Copyright (C) 2012-2021 Makoto Hiroi
*
*)
open SMLofNJ.Susp
(* 遅延ストリーム *)
exception Empty_stream
datatype 'a stream = Nils | Cons of 'a * 'a stream susp
(* アクセス関数 *)
fun stream_head (Cons(x, _)) = x
| stream_head Nils = raise Empty_stream
fun stream_tail (Cons(_, s)) = force s
| stream_tail Nils = raise Empty_stream
(* 整数列を生成するストリーム *)
fun range(low, high) =
if low > high then Nils
else Cons (low, delay (fn() => range(low + 1, high)))
(* フィボナッチ数列を生成するストリーム *)
fun fibo(a, b) = Cons(a, delay (fn() => fibo(b, a + b)))
(* n 番目の要素を求める *)
fun stream_ref(Nils, _) = raise Empty_stream
| stream_ref(Cons(x, _), 1) = x
| stream_ref(Cons(_, tail), n) = stream_ref(force tail, n - 1)
(* n 個の要素を取り出す *)
fun stream_take(Nils, _) = raise Empty_stream
| stream_take(Cons(x, _), 1) = [x]
| stream_take(Cons(x, tail), n) = x :: stream_take(force tail, n - 1)
(* マッピング *)
fun stream_map _ Nils = Nils
| stream_map proc (Cons(x, tail)) =
Cons (proc x, delay (fn() => (stream_map proc (force tail))))
(* フィルター *)
fun stream_filter _ Nils = Nils
| stream_filter pred (Cons(x, tail)) =
if pred x then Cons(x, delay (fn() => stream_filter pred (force tail)))
else stream_filter pred (force tail)
(* 畳み込み *)
fun stream_foldl _ a Nils = a
| stream_foldl proc a (Cons(x, tail)) =
stream_foldl proc (proc(x, a)) (force tail)
fun stream_foldr _ a Nils = a
| stream_foldr proc a (Cons(x, tail)) =
proc(x, stream_foldr proc a (force tail))
ご参考までに lazy を使ったプログラムを示します。
(*
* lazy.sml : lazy を使った遅延ストリーム
*
* Copyright (C) 2012-2021 Makoto Hiroi
*
*)
(*
* lazy keyword を有効にする
* コマンドラインから入力してもよい
* sml -Cparser.lazy-keyword=true
*)
Control.lazysml := true;
open Lazy
(* 遅延オブジェクトを評価する *)
fun force ($ x) = x
(* 例外 *)
exception Empty_stream
(* 遅延ストリームの定義 *)
datatype lazy 'a stream = Nils | Cons of 'a * 'a stream
(* アクセス関数 *)
fun stream_head (Cons(x, _)) = x
| stream_head Nils = raise Empty_stream
fun lazy stream_tail (Cons(_, s)) = s
| stream_tail Nils = raise Empty_stream
(* 整数列の生成 *)
fun lazy range(low, high) =
if low > high then Nils else Cons (low, range(low + 1, high))
(* フィボナッチ数列の生成 *)
fun lazy fibo(a, b) = Cons(a, fibo(b, a + b))
(* n 番目の要素を取り出す *)
fun stream_ref(Nils, _) = raise Empty_stream
| stream_ref(Cons(x, _), 1) = x
| stream_ref(Cons(_, tail), n) = stream_ref(tail, n - 1)
(* n 個の要素を取り出す *)
fun stream_take(Nils, _) = raise Empty_stream
| stream_take(Cons(x, _), 1) = [x]
| stream_take(Cons(x, tail), n) = x :: stream_take(tail, n - 1)
(* マッピング *)
fun lazy stream_map _ Nils = Nils
| stream_map proc (Cons(x, tail)) =
Cons (proc x, stream_map proc tail)
(* フィルター *)
fun lazy stream_filter _ Nils = Nils
| stream_filter pred (Cons(x, tail)) =
if pred x then Cons(x, stream_filter pred tail)
else stream_filter pred tail
(* 畳み込み *)
fun stream_foldl _ a Nils = a
| stream_foldl proc a (Cons(x, tail)) =
stream_foldl proc (proc(x, a)) tail
fun stream_foldr _ a Nils = a
| stream_foldr proc a (Cons(x, tail)) =
proc(x, stream_foldr proc a tail)
簡単な実行例を示します。
- val s = range(1, 10); val s = $$ : int stream! susp - stream_head s; val it = 1 : int - stream_head (stream_tail s); val it = 2 : int - stream_head (stream_tail (stream_tail s)); val it = 3 : int - val s4 = fibo(0, 1); val s4 = $$ : int stream! susp - stream_take(s4, 10); val it = [0,1,1,2,3,5,8,13,21,34] : int list - val s5 = stream_map (fn(x) => x * x) s; val s5 = $$ : int stream! susp - stream_take(s5, 5); val it = [1,4,9,16,25] : int list