SMLで遅延リスト
- 作者: 大堀淳
- 出版社/メーカー: 共立出版
- 発売日: 2001/09/30
- メディア: 単行本
- 購入: 1人 クリック: 10回
- この商品を含むブログ (4件) を見る
以下遅延リストまとめと7章(遅延リストのとこ)の回答.
(この本の公式サイトは問題の解答がほとんど無いんですがやる気あるんですかね？)
遅延リスト
遅延リスト([0..]みたいなやつ)を作るには,(普通のリストと比べて)
尾部を扱うために評価が一回余分に必要になるようにすればよい.
- datatype 'a inflist = nil | cons of 'a * (unit -> 'a inflist);
手動でリストを構築してみる.
- cons (1, fn ()=>(cons (2, fn ()=>(cons (3, fn ()=>nil))))); val xs = cons (1,fn) : int inflist
手動だと面倒なのでリストを構築する関数を作る.
- fun fromN n = cons (n, fn ()=>fromN (n+1)); val fromN = fn : int -> int inflist
headとtailも作る
fun head (cons (h,_)) = h; fun tail (cons (_,t)) = t (); (* unitに適用する *)
問 7.14 へ回答
リストへの基本的な関数を作る問題.
TAKE
fun TAKE 0 _ = [] | TAKE n xs = head xs :: TAKE (n-1) (tail xs);
DROP
先頭からn個の要素を読み捨てる関数. いきなり定義せずに関数を任意回適用する関数iterateを作ってみた.
fun iterate 0 f a = a | iterate n f a = iterate (n-1) f (f a) ; fun DROP n xs = iterate n tail xs ;
VIEW
fromからn個の要素を得る.
fun VIEW (from,n) xs = TAKE n $ DROP (from-1) xs ;
エラトステネスの篩
遅延評価と言えばコレ.
fun SIFT nil = nil | SIFT xs = let val h = head xs in cons (h, fn ()=> SIFT (lfilter (fn x=>x mod h<>0) (tail xs))) end ; - TAKE 10 $ SIFT $ fromN 2; val it = [2,3,5,7,11,13,17,19,23,29] : int list
問 7.15 へ回答
二次元配列の様に扱うために, 無限リストの無限リストを作る問題.
xs[y][x]==f (y,x)になるようなリストのリストを作る.
要は以下のようなデータを作ればよい(ハズ)
(* (f : int * int -> int) *) →Y ↓[f(0,0), f(0,1), f(0,2), ...] X [f(1,0), f(1,1), f(1,2), ...] [f(2,0), f(2,1), f(2,2), ...] [f(3,0), f(3,1), f(3,2), ...] . . .
まず上の図でのY軸方向のリストを作る関数を定義.
fun yaxis f x y = cons (f (x,y), fn ()=> yaxis f x (y+1));
次に, 今作ったY方向の無限リストをX軸方向に並べる.
fun xyaxis f x y = cons (yaxis f x y, fn ()=> xyaxis f (x+1) y);
これを使って(0,0)からのリストを作る
fun graph f = xyaxis f 0 0; fun point (x,y) xxs = at y $ at x xxs;
使ってみる.
fun plus (x,y) = x+y; - point (10,15) (graph plus); val it = 25 : int
7.15.3
二次元リスト上をジグザグにたどる無限リストを作る問題(AAが難しいので略).
*1
fun sum n = let fun sum_ n acc = if 0<n then sum_ (n-1) (n+acc) else acc in sum_ n 0 end fun enumerate () = let fun snake (x,y) = sum (x+y) + y in xyaxis snake 0 0 end
SML/njで遅延リスト
SML/njには処理系専用ライブラリとして遅延データ構造のためのstructureが用意されているので,それを使うべきな気がする.
type 'a susp val delay : (unit -> 'a) -> 'a susp val force : 'a susp -> 'a
これを使うと,遅延リストは次のように定義できる.
structure Lazy = SMLofNJ.Susp; datatype 'a inflist = nil | cons of 'a * 'a inflist Lazy.susp;
手動でリストを作ると,
(* [1,2,3] *) - val xs = cons(1, Lazy.delay(fn ()=> (cons (2, Lazy.delay (fn ()=> (cons (3, Lazy.delay (fn ()=>nil)))))))); val xs = cons (1,-) : int inflist
より面倒になったような….
ついでにheadとtailは
fun head (cons(x,xs) : 'a inflist) : 'a = x | head (nil : 'a inflist) = raise Empty ; fun tail (cons (_,xs)) = Lazy.force xs | tail nil = raise Empty;
となり, 最初に作ったリストのunitへの適用がLazy.forceに替わる.
あとはこれまでと同じ定義で関数が定義できる.
おまけ
こんなん作れば…レンジ的な…何か…orz.
fun op|| (xs, f) = FILTER f xs; (* op| は文法的にダメっぽい *) infix ||; (* Nats () => [1,2,3,...] *) - TAKE 5 (Nats () || (fn x=>x mod 2=0) || (fn x=>x>10)); val it = [12,14,16,18,20] : int list
ちなみにop$は以下. こっちは必須ですね.
fun op$ (f,a) = f a; infixr $;
感想
SMLには型クラスとか無いので何かデータを操作すると,途端に具体型になっちゃう.
型の定義は簡単に多相になるのになんだか勿体ない感じ. (リスト関係ない)
structureとか真面目に定義しろってことですね.
あと,今回定義した遅延リストは直接Cleanとかのリストと対応するのかよく分からない.
もしかして[]じゃなくて[!](頭部正格リスト)と対応するんじゃないかとか.
書き終わってから思った. 'aが多相なんだからどっちでもいいのかしら？
つまり…内包表記よこせ！！
