unfoldで配列の生成
SMLの標準ライブラリには、配列を扱うモジュールとして Array と Vector があります。
これらのデータ構造を構築するために標準に用意されている関数は
val tabulate : int * (int -> 'a) -> 'a array (* or vector *)
これだけです。インデックスを受け取って対応する場所に入る要素を返す関数を渡します。
しかし、これでは 関数:(int -> 'a) に状態を持てません(´・ω・`)
これでは不便なので、より一般化して、任意の状態を持てるようにした生成関数を作ります。そのような関数は unfold として知られています。
ナイーブな定義は以下のようになります。
fun unfold f e = case f e of NONE => [] | SOME(x,e') => (x::unfold f e')
これはコンテナの要素(x)が出てくる度に追加していますが、今欲しいのは固定長配列の生成関数なので少し工夫が必要です。
infixr 1 $ ;fun f $ a = f a fun unfold (n:int) (f:'a -> 'b * 'a) (e:'a) : 'b array = if n=0 then fromList [] else let val (x,e') = f e val xs = array (n, x) (* 先頭に指定された値を使って初期化 *) fun go i e = if n=i then () (* 欲しいのは xs なので何も返さない *) else let val (x,e') = f e in (* 再帰しながら配列を書き換える *) (update (xs, i, x); go (i+1) e') end in (go 1 e'; xs) end
(Gistに動く状態のコードを張ってあります。)
ナイーブな unfold ではシーケンスの終わりを NONE で判定していましたが、固定長配列なので最初に指定させて関数内部で管理します。
状態は (e:'a) で管理しているので任意の型を取ることができます。
使用例。
- Array.unfold 10 (fn i=> (i,i+2)) 0; val it = [|0,2,4,6,8,10,12,14,16,18|] : int array - Array.unfold 5 (fn s=> (s,s^s)) "1"; val it = [|"1","11","1111","11111111","1111111111111111"|] : string array - Array.unfold 10 (fn (i,i1)=> (i,(i+i1,i))) (1,0); (* フィボナッチ数列 *) val it = [|1,1,2,3,5,8,13,21,34,55|] : int array
終端の判定をする必要がないので意外とすっきりしてますね。*1
*1:しかしSMLで Array なんて持ち出すときは大抵周辺が汚くなってると思われますが…w