PR

 前回はStream Fusionを使った融合変換の基礎を説明しました。これだけでもStream Fusionは十分に強力な仕組みですが,Stream Fusionの真骨頂は「fold/buildよりも広範な融合変換がStream Fusionだけでできる点」にあります。fold/buildでは新たに別の融合変換規則を導入する必要がある処理でも,Stream Fusionではそのまま融合変換が可能です。今回は,Stream Fusionの詳細な特徴を説明します。

foldrだけではなくfoldlも融合変換の対象に

 第37回で説明したように,fold/buildではfoldrを使って「データ構造を使用する消費者」を定義することで,融合変換可能な優良消費者を用意します。しかし,融合変換の対象を様々な処理に広げていこうとすると,「foldrを使って消費者を定義する」という点が問題になります。

 データ構造を対象にする処理の中には,foldrよりもfoldlや別の再帰関数を使って定義したほうが効率の良い処理もあります。しかし,fold/buildでは優良消費者を定義するのにfoldrを使用するという制約があるため,「ある処理にとっての効率的な定義」と「融合変換によって効率化できる定義」の二つがうまく両立しない可能性があります。

 foldrを使って定義された関数の処理の効率が悪かったとしても,その関数が使うリストが「buildを使って定義された優良生産者」によって作成される場合には,fold/buildでfoldrが削除されるため,特に問題にはなりません。しかし,リストが「buildを使わずに定義された生産者」によって作成される場合には,foldrを使って定義された効率の悪い消費者の定義がそのまま残ってしまいます。foldlを使って関数を定義すれば効率の良い消費者を定義できますが,今度は消費者が融合変換の対象にならず,中間データ構造を作成するため,別の部分で性能の劣化が起こってしまいます。

 これは性能に関する問題なので,第34回で説明したfoldrからfoldlを作成する方法,つまり「foldrを使って別の再帰構造を定義する方法」では解決できません。なぜなら,foldrを使って別の再帰構造を定義する方法そのものが非効率である可能性があるからです。

 foldrを使ったfoldlの定義には「データ構造から要素を逆順に取り出す」という操作が含まれています。リストなどのランダム・アクセスできないデータ構造では,データ構造から要素を逆順に取り出すには,データ構造を先頭から末尾までたどっていかなければなりません。これには少なくともO(n)の処理が必要になります。つまり,データ構造から要素を逆順に取り出す操作はとても効率の悪い処理です。

 このように,リストなどのランダム・アクセスできないデータ構造では,foldrを使って定義された「データ構造から要素を逆順に取り出す操作」を含むfoldlはとても非効率になります。このような性能の問題が発生すると,処理の効率を上げるという本来の目的を果たせなくなってしまいます。

 「foldrという再帰構造を使うことで発生する効率性の問題」と「foldr以外の再帰構造を使うことで発生する中間データ構造の問題」を同時に解決するには,foldrとbuildを融合変換するfold/build以外に,foldlとbuildを融合変換するfoldl/buildのような規則を追加する必要があります(参考リンク)。しかし,foldr以外の再帰構造を融合変換可能にするためにアドホックに融合変換規則を加えていくと,融合変換規則の数が爆発してしまいます。fold/buildの本来の目的は,関数ごとにアドホックに融合変換規則を加えることで起こる融合変換規則の爆発を防ぐことなので,このような方針は間違っています。

 一方,Stream Fusionでは,優良消費者の定義に必要な再帰構造を特に規定しません。Stream Fusionで優良消費者の定義に使われるstream関数は,あくまで消費者本体にStream型のデータを渡すものであって,消費者が行う再帰処理に必要な再帰構造を与えるものではないからです。このため,foldrやfoldlなどの任意の再帰構造を使った関数を,Stream Fusionという統一的な仕組みで融合変換できるように定義できます。

 例として,Stream Fusionを使用したstream-fusionパッケージにおけるfoldr関数とfoldl関数の定義を見てみましょう。

 foldr関数の定義は以下の通りです(前回説明したように,stream-fusionでのStreamという名前修飾はData.Streamモジュールを指しています)。

-- Data.List.Stream モジュールでの定義
foldr :: (a -> b -> b) -> b -> [a] -> b
~ 略 ~
{-# RULES
"foldr -> fusible"  [~1] forall f z xs.
    foldr f z xs = Stream.foldr f z (stream xs)
--"foldr -> unfused" [1] forall f z xs.
--    Stream.foldr f z (stream xs) = foldr f z xs
  #-}

 Data.Streamモジュールのfoldr関数の定義は以下の通りです。

-- Data.Stream モジュールでの定義
foldr :: (a -> b -> b) -> b -> Stream a -> b
foldr f z (Stream next s0) = loop_foldr s0
  where
    loop_foldr !s = case next s of
      Done       -> z
      Skip    s' -> expose s' $ loop_foldr s'
      Yield x s' -> expose s' $ f x (loop_foldr s')
{-# INLINE [0] foldr #-}

 foldl関数の定義は以下の通りです。

-- Data.List.Stream モジュールでの定義
foldl :: (a -> b -> a) -> a -> [b] -> a
~ 略 ~
{-# RULES
"foldl -> fusible"  [~1] forall f z xs.
    foldl f z xs = Stream.foldl f z (stream xs)
--"foldl -> unfused" [1] forall f z xs.
--    Stream.foldl f z (stream xs) = foldl f z xs
  #-}

-- Data.Stream モジュールでの定義
-- * Reducing streams (folds)

foldl :: (b -> a -> b) -> b -> Stream a -> b
foldl f z0 (Stream next s0) = loop_foldl z0 s0
  where
    loop_foldl z !s = case next s of
      Done       -> z
      Skip    s' -> expose s' $ loop_foldl z s'
      Yield x s' -> expose s' $ loop_foldl (f z x) s'
{-# INLINE [0] foldl #-}

 foldr内部のloop_foldr関数では,「next s」の結果が「Yield x s'」であるときに「f x (loop_foldr s')」を再帰的に呼び出しています。「next s」の結果が連続して「Yield x s'」になれば「f x1 (f x2 (f x3 ...))」の形になります。このことから,この定義がfoldrの再帰構造を記述していることがわかります。

 一方,foldl内部のloop_foldl関数では,「next s」の結果が「Yield x s'」であるときに「loop_foldl (f z x) s'」を再帰的に呼び出しています。「next s」の結果が連続して「Yield x s'」になれば「... f (f (f z x1) x2) x3) ...」の形になります。このことから,この定義がfoldlの再帰構造を記述していることがわかります。

 こうして定義されたfoldr関数は,"foldr -> fusible"規則によって,stream関数を使用する優良消費者になります。同様にfoldl関数も,"foldl -> fusible"規則によって,stream関数を使用する優良消費者になります。したがって,foldrやfoldlに渡すリストがunstream関数を使用した優良生産者によって作成されていれば,foldrやfoldlと「リストを作成する関数」の間に発生する中間データ構造を除去するよう融合変換できます。

 このように,Stream Fusionでは融合変換可能な優良消費者の定義が特定の再帰構造に依存していません。Stream Fusionでは,Data.Streamモジュールのfoldr関数やfoldl関数のような「Stream型を引数として取り,Stream型を返す関数」を使って,優良消費者の再帰構造を自由に定義できます。その結果,Stream Fusionではアドホックに融合変換規則を加えなくても,その処理に最適な融合変換を提供できます。