PR

 このように,"fold/build"規則が適用されず,foldrやbuildを使った形式が非効率になる関数に対しては,buildやfoldrを使わない形式に戻す必要があります。ただし,「foldrやbuildを使う形式からfoldrやbuildを使わない形式への変換」を用意すると,新たな問題が発生する可能性があります。「foldrやbuildを使わない形式からfoldrやbuildを使う形式への変換」がすでに存在していると,「foldrやbuildを使う形式からfoldrやbuildを使わない形式への変換」と「foldrやbuildを使わない形式からfoldrやbuildを使う形式への変換」の間でループが生じてしまう可能性があるのです。この問題も,段階制御を使って解決できます。

 例を見てみましょう。map関数では,"map"規則が「buildやfoldrを使う形式への変換」,"mapList"規則が「buildやfoldrを使わない元のmapへの変換」を行っています。

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

 先ほど見たように,「map f xs」は"map"規則により,「build (\c n -> foldr (mapFB c f) n xs)」というbuildとfoldrを使った式に書き換えられます。この式に出てくるbuildとfoldrが"fold/build"規則によって除去されない場合,フェーズ1でbuild関数をインライン化して「foldr (mapFB (:) f) [] xs」という式にします。

    map f xs
==> { "map"規則の適用 }
    build (\c n -> foldr (mapFB c f) n xs)
==> { build 関数のインライン化 }
    foldr (mapFB (:) f) [] xs

 この式の「foldr (mapFB (:) f) []」という部分が,"mapList"規則の左辺に相当します。段階制御によりfoldrのインライン化はフェーズ0まで延期されるため,"mapList"規則は「foldr (mapFB (:) f) [] xs」を「map f xs」という「foldrとbuildを使っていない形式」に戻すことが可能です。

    foldr (mapFB (:) f) [] xs
==> { "mapList"規則の適用 }
    map f xs

 "mapList"により最初の「map f xs」という式に戻るため,この式に対して再び"map"規則を適用することが可能です。したがって,何も考えずに"map"規則と"mapList"規則を列挙すると,"map"と"mapList"の組み合わせがループ構造になります。単純化器で行なわれるインライン化や書き換え規則の適用は,実際には抽象構文木を走査する形で行なわれます。走査の途中でこのループ構造に遭遇すると,コンパイルが終わらなくなってしまいます。

 そこで段階制御を使って"map"規則と"mapList"規則が同時に適用されないようにします。

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

 RULES指示文に対する段階制御は,INLINE指示文に対する段階制御と同様の意味になっています。[1]はフェーズ1から書き換え規則を許可するという意味です。つまり,[1]と指定した書き換え規則の適用はフェーズ1までは適用されず,フェーズ1に到達した後のフェーズ1とフェーズ0で適用されるようになります。[~1]と指定すると,フェーズ1以降では書き換え規則が適用されなくなります。つまり,[~1]は書き換え規則の適用をフェーズ2までは行いますが,フェーズ1とフェーズ0では行いません。

 書き換え規則とフェーズの関係を以下の表にまとめます。

指示文フェーズ2より前フェーズ2以降
{-# RULES f = g #-}書き換える書き換える
{-# RULES [2] f = g #-}書き換えない書き換える
{-# RULES [~2] f = g #-}書き換える書き換えない

 段階制御を使うことで,"map"規則と"mapList"規則の間のループを取り除くことができます。"map"規則では[~1]と指定しているので,この規則が有効なのはフェーズ1に到達するまでです。一方,"mapList"の指定は[1]なので,フェーズ1に到達してはじめて書き換え規則が有効になります。このように,"map"と"mapList"が同時に適用されることはないので,"map"と"mapList"の間でループが発生することはなくなります。

 この例を「-ddump-simpl-stats」オプションを使ってコンパイルすれば,ここで説明したような最適化が実際に行われているのを確認できます。

module Rewrite where
import Data.List

test = nub . map (+1) . map (+2)

$ ghc -c -O2 Rewrite2.hs -ddump-simpl-stats

~ 略 ~
==================== Grand total simplifier statistics ====================
Total ticks:     114

24 PreInlineUnconditionally
12 PostInlineUnconditionally
12 UnfoldingDone
5 RuleFired
    1 fold/build
    2 map
    1 mapFB
    1 mapList
6 LetFloatFromLet
53 BetaReduction
2 KnownBranch
13 SimplifierDone

 「変換を行う規則と元に戻す規則をペアにし,段階制御でそれぞれの規則を切り替える」という手法は,「一対のルール(pair rules)」というイディオムとして,書き換え規則では多用されます(参考リンク)。書き換え規則を利用する際の便利なテクニックの一つとして覚えておくとよいでしょう。