SML/NJで遅延リスト(再び)
以前SMLで遅延リストを作る方法を紹介しましたが, どうしてもサンクを作るためにラムダ式をその場で作らなければならず, 記述が冗長でした.
以前の記述
open SMLofNJ.Susp datatype 'a lazylist = lnil | ::: of 'a * 'a lazylist Susp.susp (* takeの実装例 *) fun take 0 xs = lnil | take _ lnil= raise Empty | take n xs = (head xs):::delay (fn ()=>take (n-1) (tail xs))
しかしSML/NJには拡張機能としてlazyパターンが備わっているので, これを使えば以前のような冗長な記述は避けられます.
こんな風になります.
val take : int -> 'a llist susp -> 'a llist susp val $ : 'a -> 'a susp fun lazy take 0 _ = $ lnil | take n ($ (x:::xs)) = $ (x:::(take (n-1) xs)) | take n ($ lnil ) = raise Empty
関数名にlazyと書いて, 普通に(正格な関数と同じように)関数を書いた後, 全体に $ をつけて型をあわせます.
lazyを付けると, 右辺で自分自身を呼び出すような記述をしても, その場では評価されずに $ に式が渡されます.
そして結果の型に susp が付きます.
最初の例と比較すると, わざわざラムダ式を余分に記述する必要がなくなり, より自然にロジックが記述できています.(…よね?)
SML/NJの拡張機能の使い方
トップレベルから見えるControl structureの参照を直に書き換えてもよいですが,
replの起動時にも指定できます.(sml -Hすると使えるオプションが一覧できます)
$ sml -Cparser.lazy-keyword=true Standard ML of New Jersey v110.72 [built: Tue Aug 24 10:47:04 2010] - (* lazyが使える状態でreplが起動する *)
次にサンクのコンストラクタ($)を使うため, Lazyをオープンします.
- open Lazy; opening Lazy datatype 'a susp = $ of 'a
サンクの評価を行う関数がなぜか用意されていないので自前で定義します.
fun force ($ x) = x
これでlazyパターンを使った遅延評価がすっきり記述できるようになります.
コード全体
一通りの操作を今回紹介した機能を使って実装したコードを載せます.
(* * sample code for using lazy-pattern extension of SML/NJ * $ sml -Cparser.lazy-keyword=true (or eval Control.lazysml := true; on repl) *) structure Main = struct open Lazy fun force ($ x) = x datatype 'a llist = lnil | ::: of 'a * 'a llist susp infixr 5 ::: fun lazy fromN n = $ (n:::fromN (n+1)) fun head ($ (x:::_)) = x | head ($ lnil ) = raise Empty fun lazy tail ($ (_:::xs)) = xs | tail ($ lnil ) = raise Empty fun lazy take 0 _ = $ lnil | take n ($ (x:::xs)) = $ (x:::(take (n-1) xs)) | take n ($ lnil ) = raise Empty fun lazy foldr f init ($ lnil) = init | foldr f init ($ (x:::xs)) = (f ($ x, foldr f init xs)) fun lazy foldl f init ($ lnil) = init | foldl f init ($ (x:::xs)) = foldl f (f ($ x, init)) xs fun lazy map f ($ lnil) = $ lnil | map f ($ (x:::xs)) = $ (f x:::map f xs) fun lazy zip2 ($ lnil) ys = $ lnil | zip2 xs ($ lnil) = $ lnil | zip2 ($(x:::xs)) ($(y:::ys)) = $ ((x,y):::zip2 xs ys) fun lazy filter f ($ lnil) = $ lnil | filter f ($ (x:::xs)) = if f x then $ (x:::filter f xs) else filter f xs fun <!> ($ lnil) = [] | <!> ($ (x:::xs)) = x::(<!> xs) end
大分すっきりしました\(^o^)/
PFDS
今回紹介した機能を使うとPFDSのStreamの説明と同じように記述できるようになります.
Purely Functional Data Structures
- 作者: Okasaki
- 出版社/メーカー: Cambridge University Press
- 発売日: 1999/07/01
- メディア: ペーパーバック
- 購入: 5人 クリック: 46回
- この商品を含むブログ (25件) を見る