無限リスト - Note

↑とは直接関係ないのですが、私は何年かに1度は無限リストが無いと死ぬ病にかかります。今更感炸裂ですので耳タコの方は戻るボタンをお押しください。

所謂(「ハンドル」または「OOP」風の)ストリームに対する無限リストのメリットはいろいろあると思われるのですが

キューとかバッファいらない
スレッド使わなくても生成側も処理側もどちらも自分がmainのつもり風に書ける
ungetcまたはシーク操作あるいは破棄操作の類いがいらない(O'CamlでいえばStream.junk)
- のでデータを共有したままのバックトラックが容易
読み込む要素数を数えなくていい(O'CamlでいえばStream.npeekの引数)
etc...

欠点は、個々の要素がcharぐらいに小さい値ですと、オーバーヘッドが気にかかるぐらいでしょうか。O'CamlのStreamも操作の度に毎回要素ごとにoptionで包んだりする酷い作りですので、気にすることはないと思います。

とにかくO'Camlで無限リストを使うにはどうすればスマートか試行錯誤して早幾年、私の中ではこんな形になりました。

type 'a t = 'a prim lazy_t
and 'a prim = [
  | `nil
  | `cons of 'a * 'a t];;

リストはこんな風に作ります。

lazy (`cons (1, lazy (`cons (2, lazy `nil))))

lazyの優先順位は関数適用よりも弱くするべきと思います！

関数はこんな感じになります。

let append (xs: 'a t) (ys: 'a t): 'a t = (
  let rec loop (xs: 'a t) (ys: 'a t): 'a prim = (
    begin match xs with
    | lazy (`cons (x, xr)) ->
      `cons (x, lazy (loop xr ys))
    | lazy `nil ->
      Lazy.force ys
    end
  ) in
  lazy (loop xs ys)
);;

3.11の新機能、パターンマッチ式中でのlazyの展開！このお陰でO'Camlでの無限リストがぐっと実用的になりました。

中でわざわざ返値型からlazyを外してループしている理由は一応あります。こうしなかった場合を考えてみてください。

1. lazyを一番外に持ってくる

let rec append (xs: 'a t) (ys: 'a t): 'a t = lazy (
  begin match xs with
  | lazy (`cons (x, xr)) ->
    `cons (x, append xr ys)
  | lazy `nil ->
    Lazy.force ys
  end
);;

この場合、後続部分にあたる「append xr ys」の引数部分が正格評価されてしまいます。ここに書く式によっては遅延にならねーということになりかねません。ま、この例では受け取った値を渡しているだけですのでどうでもいいですが、原則でいえば後続部分はlazyで囲う必要があります。

2. 値を作るところでlazyを書く

let rec append (xs: 'a t) (ys: 'a t): 'a t = (
  begin match xs with
  | lazy (`cons (x, xr)) ->
    lazy (`cons (x, append xr ys))
  | lazy `nil ->
    ys
  end
);;

なんだか余計なforceも消えてすっきりしてそうです。しかし、このコードが実際に走るとどうなるか考えてみましょう。append関数が返した無限リストの先頭だけを取り出したいのに、先頭要素と一緒に後続部分を求めるappend関数の再帰呼び出しが起きて関数中のmatchを通り越して次の要素を作成するlazyの直前まで実行されてしまいます。……要するに、実際に必要な要素よりも1要素先まで計算されてしまいます。それにより「1.」と同じ問題も丸々抱え込んでしまいます。

ループの中でlazyを外しておくと、lazy (`cons (..., ...))ではなく`cons (..., lazy (...))の形になりますので、これらの問題をクリアした上で、必要とされている先頭1要素についてはいつもの正格評価で作ることができます。めでたしめでたし。

引数はlazy付き、返値はlazy無し、呼び出し側でlazyを付けてもらう、というルールでもいいかなあとも思います。