++演算子をStream Fusionで効率化

 fold/buildでは,単一のfoldr関数と単一のbuild関数を融合変換することしか想定されていません。このためfold/buildでは,++演算子を使った「xs ++ ys」のような「複数個の中間データ構造を使用する関数」を使った処理を,完全な形で融合変換することはできません。「xs ++ ys」の場合には,xsを作成する処理か,ysを作成する処理か,どちらか一方を選んで融合変換を行うことになります。

 この問題を解決するため,第37回では,xs,ys,「xs ++ ys」の結果として作成されるリスト,の三つのリストすべてに対して融合変換を行うために"foldr/augment"規則という新たな融合変換規則を導入しました。

 一方,Stream Fusionでは,Stream型に格納する「s -> Step a s」型の関数の呼び出しパターンを工夫することで,"augment/build"のような融合変換規則を新たに導入しなくても,「複数個の中間データ構造を使用する関数」を使った処理に対して融合変換を提供できます。

 例を見てみましょう。++演算子の定義は以下の通りです。

-- Data.List.Stream モジュールでの定義
(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

-- NOTE: This is quite subtle as we do not want to copy the last list in
--
-- xs1 ++ xs2 ++ ... ++ xsn
--
-- Indeed, we don't really want to fuse the above at all unless at least 
-- one of the arguments has the form (unstream s) or the result of the
-- concatenation is streamed. The rules below do precisely that. Note they
-- really fuse instead of just rewriting things into a fusible form so there
-- is no need to rewrite back.

{-# RULES
"++ -> fused on 1st arg" [~1] forall xs ys.
    unstream xs ++ ys = Stream.append1 xs ys
"++ -> fused on 2nd arg" [~1] forall xs ys.
    Stream.append1 xs (unstream ys) = unstream (Stream.append xs ys)
"++ -> fused (1)" [~1] forall xs ys.
    stream (xs ++ ys) = Stream.append (stream xs) (stream ys)
"++ -> fused (2)" [~1] forall xs ys.
    stream (Stream.append1 xs ys) = Stream.append xs (stream ys)

"++ -> 1st arg empty" forall xs.
    [] ++ xs = xs
"++ -> 2nd arg empty" forall xs.
    xs ++ [] = xs
"++ / :" forall x xs ys.
    (x:xs) ++ ys = x : (xs ++ ys)
 #-}

 ++演算子を融合変換可能な形に変換するための規則は,ずいぶん複雑になっています。これはなぜでしょうか?

 ++演算子を使ったリストの連結は,「xs1 ++ xs2 ++ ... ++ xsn」のようにつないでいくことが可能です。このとき,xs1,x2,... xsnのすべてが融合変換可能であれば問題はありません。しかし,リストの一部またはすべてが優良生産者によって作成されていないため,融合変換不可能である場合もあります。この場合,「xs ++ ys」という式を単純に「unstream (Stream.append (stream xs) (stream ys))」と変換してもあまり意味がありません。むしろ,append関数が二つのStreamを処理しなければならないため,単純にリストxsの要素をリストysの前に並べていく通常の++演算子に比べて非効率になる可能性があります。

 また,「[] ++ xs」や「unstream xs ++ []」のように式に空リストが現れる場合,無理にappend関数を使用する形に書き換えるよりも,単純に空リストを消した「xs」や「unstream xs」に書き換えるほうが効率的です。

 そこで,++演算子を使った式の効率をできる限り上げるため,「xsとysのどちらも空リストではなく,xsとysの両方がunstreamを使った優良生産者である場合」,または「『xs ++ ys』の結果をStreamとして使用する場合」にのみappend関数を使用する形に書き換えるように,複雑な規則を定義しているのです。

 いくつか例を見てみましょう。「xs ++ ys」のxsかysが空リストである場合,append関数を使った形には変換されません。

    unstream xs ++ []
==> { "++ -> 1st arg empty"規則の適用 }
    unstream xs

    [] ++ unstream ys
==> { "++ -> 2nd arg empty"規則の適用 }
    unstream ys

 xsとysの両方がunstreamを使用した優良生産者である場合には,複数の規則を適用してappend関数を使った形に変換されます。

    unstream xs ++ unstream ys
==> { "++ -> fused on 1st arg" 規則の適用 }
    Stream.append1 xs (unstream ys)
==> { "++ -> fused on 2nd arg" 規則の適用 }
    unstream (Stream.append xs ys)

 「xs ++ ys」の結果をStreamとして使用する場合,"++ -> fused (1)"規則によってappend関数を使った形に変換され,その後,xsとysに対して必要に応じて"STREAM stream/unstream fusion"規則が適用されて融合変換が行われます。

    stream (unstream xs ++ unstream ys)
==> { "++ -> fused (1)"規則の適用 }
    Stream.append (stream (unstream xs)) (stream (unstream ys))
==> { "STREAM stream/unstream fusion"規則の適用 }
    Stream.append xs ys

stream (unstream xs ++ ys)
==> { "++ -> fused (1)"規則の適用 }
    Stream.append (stream (unstream xs)) (stream ys)
==> { "STREAM stream/unstream fusion"規則の適用 }
    Stream.append xs (stream ys)

 では,++演算子の定義に使われているappend関数の定義を見てみましょう。

-- Data.Stream モジュールでの定義
-- (++)
append :: Stream a -> Stream a -> Stream a
append (Stream next0 s01) (Stream next1 s02) = Stream next (Left s01)
  where
    {-# INLINE next #-}
    next (Left s1)  = case next0 s1 of
                          Done        -> Skip    (Right s02)
                          Skip s1'    -> Skip    (Left s1')
                          Yield x s1' -> Yield x (Left s1')
    next (Right s2) = case next1 s2 of
                          Done        -> Done
                          Skip s2'    -> Skip    (Right s2')
                          Yield x s2' -> Yield x (Right s2')
{-# INLINE [0] append #-}

 append関数では,Either型のLeftデータ構成子を左側のStream,Rightデータ構成子を右側のStreamの意味で使っています。

 append関数では,第1引数である「Stream next0 s01」の状態s01をLeftデータ構成子に包み,Stream型の初期状態として格納します。next関数では,この状態と第1引数の中のnext0関数を使い,まず第1引数で渡された左Streamに対する処理を行います。

 左Streamに対する処理がすべて終了したとき,左Streamに対する処理「next (Left s1)」の内部にある「next0 s1」の結果はDoneになります。左Streamには処理すべき値はもう存在しないので,第2引数である「Stream next1 s02」の状態s0をRightデータ構成子に包んで新しい状態とします。

 このとき,appendは第2引数で渡される右Streamからまだ値を取得していないので,「++演算子の処理結果を使用する消費者関数」に値を返すことはできません。そこで,next関数はYieldではなくSkipに値を包んで返します。この場合,すなわち「next (Left s1)」の結果が「Skip (Right s02)」である場合,「++演算子の処理結果を使用する消費者関数」は「next (Right s02)」を呼び出します。これにより,右Streamに対する処理が始まります。

 左Streamに対する処理が終了した後に右Streamに対する処理が始まるため,右Streamに対する処理が終了した時点でappend関数全体の処理が終了します。このため,右Streamに対する処理「next (Right s2)」の内部にある「next1 s2」の結果がDoneである場合に,処理の終了を示すDoneを返しています。

 このように,append関数は左Streamと右Streamをつなぎ合わせる処理を行います。このappend関数の定義は,「Stream型を引数として取り,Stream型を返す関数」の再帰構造に依存しません。このため,Stream Fusionで++演算子を問題なく融合変換できるのです。