SMLでZipListを作る

sml bluebird

本物のプログラマはHaskellを使うで紹介されているZipListを定義してみました。
この型を使うと、zipWithN をその場で組上げることが出来ます。(といっても最初にタプルのコンストラクタ渡すんですが)

型の定義

まず *モト* となる型を定義します。

signature ZIPLIST =
sig
  type 'a list
  datatype 'a ZipList = ZipList of 'a list
  val getZipList : 'a ZipList -> 'a list
end

structure ZipList : ZIPLIST =
struct
local
  structure L = LazyList
in
  type 'a list = 'a L.lazylist
  datatype 'a ZipList = ZipList of 'a list
  fun getZipList (ZipList xs) = xs
end (* local *)
end

隠蔽してもしょうがないのでsignatureに型を公開します。実体は後述する都合で遅延リストにしています。
SMLはHaskellのようにレコードのメンバが1個でも省略出来たりしないため、 getZipList は関数として追い出しました。コードの意味は変わっていません。

実装

次に ZipListで Applicative のプリミティブなインターフェースを実装します。

structure ZipListApplicative : APPLICATIVE_CORE =
struct
local
  structure L = LazyList
  fun id x = x
in
  (* ---> SML/NJ workaround *)
  infix <*>
  (* SML/NJ workaround <--- *)
  open ZipList
  type 'a t = 'a ZipList.ZipList
  fun fmap f (ZipList xs) = ZipList (L.map f xs)
  fun pure x = ZipList (L.repeat x)
  fun (ZipList fs) <*> (ZipList xs) = ZipList (L.zipWith (fn (f,a)=> f a) fs xs)
end (* local *)
end

pure の実装で L.repeat (= [1,1,1,...]) を使うため ZipList の実体を遅延リストにしました。
Applicativeの要件である pure id <*> xs = xs を満たすためにこのようになっているようです。

強化版ZipListを作る

元のZipListとApplicativeを実装したZipListを一つのstructureに統合します。

structure ZipListApplicative =
struct
local
  structure XZipList = MkApplicative(ZipListApplicative)
in
  open ZipList XZipList
  structure Open = XZipList.Open
end
end

もう単純作業でメンドクサイんですがどうしようもないです…。

動作確認

fun tup x y = (x,y);
fun tup3 x y z = (x,y,z); (* タプルはレコードなのでコンストラクタというモノは無い *)
infix -->
fun s --> e = L.range s (SOME e); (* [s,s+1,s+2,...,e] の意味 *)

- l.-!- (getZipList (tup <$> ZipList (0-->10) <*> ZipList (0-->10)));
val it = [(0,0),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10)] : (int * int) list
- l.-!- (getZipList (pure tup3 <*> ZipList (0-->10) <*> ZipList (0-->10) <*> ZipList (0-->10)));
val it = [(0,0,0),(1,1,1),(2,2,2),(3,3,3),(4,4,4),(5,5,5),(6,6,6),(7,7,7),(8,8,8),(9,9,9),(10,10,10)] : (int * int) list

うまく動いてるようです。この調子で <*> で繋げていくと zipWithN が作り出せます。


ちなみにSML標準ライブラリにもzipWith相当の関数は定義されています。(当然正格リスト向けですが)

ListPair.map : ('a * 'b -> 'c) -> 'a list * 'b list -> 'c list

終わり

うーむあんまりウレシイ感じがしないなー。もし現実にzipWithが使いたくても手元にあるのは普通のリストだろうし。
まぁ単体で便利なものじゃないのかも知れない。


コードはcodeplexに置いてあります。 (ziplist.use)