日々の流転

λ. “Stream fusion: from lists to streams to nothing at all” by Duncan Coutts, Roman Leshchinskiy, Don Stewart

• <URL:http://dx.doi.org/10.1145/1291220.1291199>
• 著者版

リスト処理を、以下のようなストリーム型*1に対する処理に置き換えることによって、foldl等の最終的にリストを消費する関数以外は非再帰的な定義にする。そして、通常の最適化によって、中間データ構造を削除する。

data Stream a = ∃s. Stream (s -> Step a s) s
data Step a s = Done
              | Yield a s
              | Skip s

例えば、sum (xs ++ ys) は、 sumの定義の展開と書き換え規則の適用によって foldl_s (+) 0 (append_s (stream xs) (stream ys)) となり、 定義を展開することで以下のようになる。

let next_stream xs =
      case xs of
        [] -> Done
        x : xs' -> Yield x xs'
    next_append (Left xs) =
      case next_stream xs of
        Done -> Skip (Right ys)
        Skip xs' -> Skip (Left xs')
        Yield x xs' -> Yield x (Left xs')
    next_append (Right ys) =
      case next_stream ys of
        Done -> Done
        Skip ys' -> Skip (Right ys')
        Yield y ys' -> Yield (Right ys')
    go z s =
      case next_append s of
        Done -> z
        Skip s' -> go z s'
        Yield x s' -> go (z + x) s'
in go 0 (Left xs)

そして、ここからGHCのごく普通の最適化によって以下と同等のプログラムになる。

let go z (Left xs) =
      case xs of
        [] -> go z (Right ys)
        x:xs' -> go (z+x) (Left xs')
    go z (Right ys) =
      case ys of
        [] -> z
        y:ys' -> go (z+y) (Right ys')
in go 0 (Left xs)

さらに、Constructor Specialization (Call-pattern specialisation) と呼ばれる最適化を用いると、以下と同等になる。

let go1 z xs =
      case xs of
        [] -> go2 z ys
        x:xs' -> go1 (z+x) xs'
    go2 z ys =
      case ys of
        [] -> z
        y:ys' -> go2 (z+y) ys'
in go1 0 xs

簡単な書き換え規則とごく普通の最適化機能だけで、中間データ構造を除去できているのが素晴らしい。 また、foldr/build の short-cut fusion と比べても、zipWithのような複数引数のものや、concatMapのようなネストしたリスト構造を扱うものも融合出来ると。