いわゆる遅延リストとか遅延ストリーム。F# PowerPackのLazyListって、結局のところどんなことをしてくれているのか。

個人的に息詰まる毎日が続いておりますが、みなさんいかがお過ごしでしょうか(誰
今回は、F# PowerPack*1のLazyList<'T>をさわってみたので、そのメモ。

LazyList<'T>はいわゆる遅延リストあるいは遅延ストリームなどと呼ばれるもので、それをF#でお手軽に扱えるようにしたものです。　
遅延リストとは、簡単に言えばいくつかの遅延計算の集合を表すリストで、
すぐには評価されずに、結果が必要となったときにはじめて評価される計算の集まりを表現するための器です。
いわゆる無限リストを表現する場合などによく引き合いに出されることでも知られています。
この遅延リストを用いると、コードのパフォーマンス向上に大きく役立ちます。
書籍「計算機プログラムの構造と解釈」などで学習した人や、Haskellの利用経験者であれば、これを利用するメリットについて理解できるでしょう。

さっそくLazyList<'T>を使ってみよう

Module Microsoft.FSharp.Collections.LazyList
http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/fsharp.powerpack/microsoft.fsharp.collections.lazylist.html

上記リンク先を読みつつ、フィボナッチ数列および素数について遅延リストってみました。
以下、サンプルです。

open System
open Microsoft.FSharp.Collections
open Microsoft.FSharp.Core 


(* F# PowerPackが必要です *)
let rec fibs = fun _ -> 
  LazyList.consDelayed 0
    (fun () -> (LazyList.cons 1 (LazyList.map2 (+) fibs' (LazyList.tail fibs'))))
and fibs' = () |> fibs


fibs () |> LazyList.take 10
        |> LazyList.iter (fun x -> printfn "%d" x |> ignore)
        |> Console.WriteLine

let rec primes = fun _ ->
  LazyList.consDelayed 2 
    (fun () -> LazyList.unfold (fun n -> Some(n, n+1)) 3 |> LazyList.filter isPrime)
and isPrime n = Seq.takeWhile (fun x -> x*x <= n) primes' |> Seq.forall (fun x -> n%x > 0)
and primes' = () |> primes

primes () |> LazyList.take 10
          |> LazyList.iter (fun x -> printfn "%d" x |> ignore)
          |> Console.ReadLine 
          |> ignore

実行結果

遅延リストとは言うけど、LazyList<'T>って結局のところどんなことしてくれているの？

で、遅延リストなんですが。LazyList<'T>の中では一体どんなことをしてくれているのだろうか。
こういう場合、実際にそれを実現するためのコードを考えて書いてみるといいです。
お勉強のための車輪の再発明はよくやります。ということで遅延リストっぽい何かを自作してみました。
今回書いた遅延リストなスニペットのクラス名はLazyStream<'T>としました。

open System
open Microsoft.FSharp.Collections
open Microsoft.FSharp.Core 

type LazyStream<'T> = 
  | Nil
  | Cons of 'T *  Lazy<LazyStream<'T>>

type LazyStream =
  static member toSeq lzys =
    let rec streamToSeq s =
     seq{match s with
          | Cons(a,b) -> yield a
                         for x in streamToSeq (b.Force ())
                           do yield x
          | Nil -> ();}
    streamToSeq lzys

  static member consDelayed n (lzys: unit -> LazyStream<'T>) =
    Cons(n, lazy(lzys ()))    

  static member take n lazys =
    let rec lazyStream n s =
      match (n,s) with
       | (0, Cons(x, _))  -> Nil
       | (_, Nil)         -> Nil
       | (n, Cons(x, xs)) -> Cons(x, lazy(lazyStream (n-1) (() |> xs.Force)))
    lazyStream n lazys 
  static member iter f lzys =
    for x in LazyStream.toSeq lzys 
     do f x

let rec sampleStream n = 
  LazyStream.consDelayed n (fun _ -> sampleStream (n+2))

(sampleStream 1) |> LazyStream.take 5
                 |> LazyStream.iter (fun x -> printfn "%d" x |> ignore)
                 |> Console.WriteLine

実行結果

必要最小限な実装ですが、遅延リストとは概ね上記のような感じかと思います。

ある計算をlazyで遅延評価として、弁別子付き共用体(discriminated union)に再帰的に保持しておく。
そして、実際に必要になったタイミングで遅延計算をForceしていくイメージです。
PowerPackのLazyList<'T>の実装がこのようになっているかどうかはわかりませんが、雰囲気的にはだいたいこんな感じでしょう。
今回は最小限の実装のみでしたが、LazyList<'T>で扱える操作のすべてについてこれを自作するのは
当然のことながら結構大変ですし、それなりのスキルも要求されます。
また、遅延リストについてF#開発者のそれぞれに車輪の再発明を課すのは非常に残念なことです。
そうならないようにと、マイクロソフトF#チームがこのLazyList<'T>をPowerPackとして提供してくれているというわけです。グッジョブ。

はじめはあまりピンと来ませんでしたが、車輪の再発明をすることで遅延リストに対する造詣が深くなったような気がします。
ということで、LazyList<'T>いいね！F#チームいいね！というメモでした。おしまい(・ω・)

F# PowerPackのダウンロードはこちらから
http://fsharppowerpack.codeplex.com/

*1:version 2.0.0.0