SML/NJで遅延リスト(再び) - ::Eldesh a b = LEFT a

以前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