lazyさ加減に萌 - F#マスターへの道

Seqのlazyさ加減に萌

　恥ずかしながら今日の今日までずっと誤解していたことがありまして、それはどんなことかというと、

F#のシーケンス式はシーケンスを発生する段階では遅延評価しているが、それを処理するSeq.mapといったメソッドは、実行時にシーケンスから値を取り出しながら結果の入ったシーケンスを生成している。

　という思い込みです。
　もちろんこれは後で考えれば何の根拠もないばかりか、冷静に考えればそうする実装上のメリットは何もない、という 恥ずかしい誤解です。しかもリファレンスにしっかり「遅延評価している」と書いてあります。
　というわけで、恥ずかしいついでにSeqモジュールに実装されている関数がどの程度lazyかを調べて見ることにしました。

Seq.mapのlazyっぷり

　その関数が入力をどの程度遅延評価しているかは、副作用を持つ無限シーケンスを渡してみるとはっきりします。

let s = Seq.map (fun i -> printfn "Got : %d" i; i) (Seq.initInfinite (fun i -> printfn "Return : %d" i ; i))

　この式を評価すると以下のようになります。

val s : seq<unit>
> 

　このシーケンスから先頭の数項目を取り出します。

> Seq.take 3 s;;
Return : 0
Got : 0
Return : 1
Got : 1
Return : 2
Got : 2
val it : seq<int> = seq [0; 1; 2]
>

　Seq.mapが、値を要求されて初めて渡されたシーケンスから値を取り出して関数に渡していることがわかります。lazyですねぇ。
　というわけで、Seq.mapは、それ自身ループを回って処理をする関数というわけではなく、「値を要求されたら引数に渡されたシーケンスに値を要求して、引数に渡された関数を適用して返すシーケンスを返す関数」ということになります。同じようなものを実装してみると、こんな感じになります。

let SeqMap f s =
  seq {
    for item in s do
      yield (f item)
  }
let s = SeqMap (fun i -> printfn "Got : %d" i) (Seq.initInfinite (fun i -> printfn "Return : %d" i ; i))

　このSeqMapは、Seq.mapと同じように動きます（実際の実装は少し違いますが）。

それ以外の関数のlazyっぷり

　色々試してみたのですが、Seqモジュールに実装されている関数のうち、シーケンスを引数にとりシーケンスを返すものの多くはlazyに実装されているようです。
　Seq.appendなんかは、最初の引数に無限リストを与えると、二つ目の引数には永遠にはいってきませんが、それでも文句言いません。

> let s = Seq.append 
            (Seq.initInfinite (fun i -> printfn "A : %d" i ; i)) 
            (Seq.initInfinite (fun i -> printfn "B : %d" i ; i));;
> Seq.take 10 s;;
A : 0
A : 1
A : 2
A : 3
A : 4
val it : seq<int> = seq [0; 1; 2; 3; ...]
> 

　これも、Seq.appendが、

let SeqAppend xs ys =
  seq {
    yield! xs
    yield! ys
  }

　というような実装をされていると思えば違和感がありません。
　Seq.concatも同様です。

> let s = Seq.concat [|(Seq.initInfinite (fun i -> printfn "A : %d" i ; i)); seq {1..3} |];;
val s : seq<int>
> Seq.take 10 s;;
A : 0
A : 1
A : 2
A : 3
A : 4
val it : seq<int> = seq [0; 1; 2; 3; ...]
> 

　これも二つ目のシーケンスには永遠に入ることがないでしょう。これの実装は

let SeqConcat s =
  seq {
    for item in s do
      yield! item
  }

　こんな感じでしょうか。

こんな関数もlazy

　ぱっと見ではlazyっぽくないこんな関数も、どこにも書いていませんが試してみるとlazyに動きます。

> let s = Seq.filter (fun i -> i < 100) (Seq.initInfinite (fun i -> printfn "A : %d" i ; i));;
val s : seq<int>
> Seq.take 10 s;;
A : 0
A : 1
A : 2
A : 3
A : 4
val it : seq<int> = seq [0; 1; 2; 3; ...]
> 

　このtakeに100以上の数を与えると、当然ながら帰ってこなくなります。ちなみにこのSeq.takeもlazyです。
　また、distinctも意外にイケます。

> let s = Seq.distinct (Seq.initInfinite (fun i -> printfn "A : %d" i ; 0));;
val s : seq<int>
> Seq.head s;;
A : 0
val it : int = 0
> 

　このシーケンスに、

Seq.take 2 s;;

　などとすると、やはり帰ってこなくなります。

　こうして試してみると、Seqの関数は、sortやlength、groupByといった原理的に不可能なもの以外は極力lazyに実装する方針をとっているようです。

オマケ

　今日色々試していて「おや？」と思ったのが、次の式の評価結果です。

> let s = Seq.nth 5 (Seq. unfold (fun i -> printfn "A : %d" i ; Some(i, i + 1)) 0);;
A : 0
A : 1
A : 2
A : 3
A : 4
A : 5
val s : int = 5
> 

　このようにunfoldを使った無限シーケンスをnthに与えると、当然頭から順番に評価するのですが、

> let s = Seq.nth 5 (Seq.initInfinite (fun i -> printfn "A : %d" i ; i));;
A : 5
val s : int = 5
> 

　のようにinitInfiniteで作った無限シーケンスを与えても、5番目しか評価されないのです。
　一見、nthがinitInfiniteで作られたシーケンスを特別視しているように見えますが、Seq.nthの実装を見てみても、単に末尾再帰で先頭から順に値を見ているだけで、特定の種類のシーケンスだけを特別視しているように見えません。
　タネはinitInfiniteの側にありました。これで作られたシーケンスは、MoveNextメソッドでは与えられた式を評価せず、Currentが評価されて初めて最初の引数の関数を呼ぶように作られていたからなのでした。

　ところでこの文を書いてる間、ずっとマリリンモンローの顔が頭に浮かんでいて、「なんで？」と思って色々ググってみたところ、昔見たマリリンモンローの映画で、彼女が「Lazy」という歌を歌っていたのでした。あ、今頭の中に突然宇宙戦艦ヤマトが浮かんできた。

（文責：片山 功士　　2012/01/06）

今日： - 人
昨日： - 人
トータル： - 人