functional readerから遅延リストを作る
('a, 'b) reader
SML(のStringCvt)には
datatype ('a, 'b) reader = 'b -> ('a, 'b) option
という型が定義されています.
これは'b型の入力から'a型の値を読み出して, 読み出した残りのデータとのペアを返す関数型です.*1
読み出しに失敗した場合はNONEが返ります.
これを使って入力ストリーム(StreamIO.instreamなど)から任意のデータ(文字など)を読み込むことが出来ます.
が,この入力から複数のデータを連続して読み出したい場合,
ネストしたcase式になるので読みづらいコードになります.
(* 3文字読んで表示するコード *) structure ss = Substring val ss.getc : substring -> (char, substring) option (* getcのシグネチャ *) val ins = ss.full "0123456789"; case ss.getc ins (* 1文字目を読む *) of NONE => NONE | SOME(r,s) => (case ss.getc s (* 2文字目を読む *) of NONE => NONE | SOME(r',s') => (case ss.getc s (* 3文字目を読む *) of NONE => NONE | SOME(r'',s'') => (print(concat[r,r',r'']) ;SOME(r'',s''))))
そこで, どっかで見たような演算子を定義します.
fun >>= (SOME x,f) = f x | >>= (NONE ,_) = NONE infix >>= structure ss = Substring val ins = ss.full "0123456789"; (ss.getc ins) >>= (fn (r ,s ) => (* 1文字目を読み込む *) ss.getc s >>= (fn (r' ,s' ) => (* 2文字目を読み込む *) ss.getc s' >>= (fn (r'',s'') => (* 3文字目を読み込む *) (print(concat[r,r',r'']); SOME(r'',s'')))));
はい.非常に読みやすくなりました.
ですが,これではある数だけ読み込むとか,必要なだけ読み続けるとかいった柔軟な読み込みが実現できません.
遅延リスト
datatype 'a lazylist = nil | ::: of 'a * 'a lazylist susp
これは ある値と,呼び出すと残りのリストを返す関数 のペアによって
要素を取り出す度に次の要素を作り出すリストになっています.
readerを遅延リストへ
reader型を遅延リストにすることを考えてみると,readerから読み出した1要素と
*次を読み込むために必要な文脈をそろえた関数*を返すサンクとのペアを作れば,遅延リストになりそうです.
(* readerから遅延リストを作る *) fromReader (rd:('a, 'b) reader) (v:'b) : 'b lazylist = case rd v of SOME (x, vs) => x ::: delay (fn ()=>fromReader rd vs) | NONE => lnil
あっさり出来ました(^^)v
実際に使ってみます.
structure ss = Substring val ins = ss.full "0123456789" (* 入力ストリームを文字列から作成 *) (* 読み込んだことが分かるように表示するreader *) fun getc s = ss.getc s >>= (fn(c,s')=>(print ((Char.str c)^"\n");SOME(c,s'))) val xs = take 5 (fromReader getc ins) -!- xs (* 実際に読み込みが行われるように正格リストにする *) 0 (* 順に評価されて,読み込まれた値が表される *) 1 2 3 4
これによって,任意の入力から値を読み出すreaderに対して,
遅延リスト用に定義したあらゆる操作が可能になりました!