GHCは、異型性などの一般的な機能を最適化（デフォレスト）することは可能ですか？

Question

私は本当に一般的な方法でcatamorphisms/anamorphismsでの作業のアイデアのように、それはパフォーマンスの大幅な欠点を持っている私には思える：

我々は、カテゴリのようにツリー構造で作業したいとしましょう - 記述するためにジェネリックcatamorphism functionを使用して、異なる折りたたみ：時間：残念ながら、このアプローチは重大な欠点を持っている

depth1 :: Tree -> Int 
depth1 = catam g 
    where 
    g Leaf  = 0 
    g (Tree l r) = max l r 

：

newtype Fix f = Fix { unfix :: f (Fix f) } 

data TreeT r = Leaf | Tree r r 
instance Functor TreeT where 
    fmap f Leaf   = Leaf 
    fmap f (Tree l r) = Tree (f l) (f r) 

type Tree = Fix TreeT 

catam :: (Functor f) => (f a -> a) -> (Fix f -> a) 
catam f = f . fmap (catam f) . unfix 

今、私たちは以下のように関数を記述することができます新しいレベルのTreeT Intがfmapのすべてのレベルで作成され、ただちにgが消費されます。古典定義

depth2 :: Tree -> Int 
depth2 (Fix Leaf) = 0 
depth2 (Fix (Tree l r)) = max (depth1 l) (depth1 r) 

と比較すると、当社のdepth1 GC上の不要な歪みを作る常に遅くなります。 1つの解決策は、hylomorphismsを使用し、作成ツリーと折り畳みツリーを結合することです。しかし、しばしば私たちはそのことを望んでいません。ツリーをある場所に作成し、後に折り畳まれるように別の場所を通過させたいことがあります。または、異なる異型性を持つフォルダを数回作成することもできます。

GHCを最適化する方法はありますかdepth1？インライン化のようなものcatam gそしてfusing/deforestingg . fmap ...の内部に？

Answer 1

私は答えを見つけたと信じています。私はWhy does GHC make fix so confounding?という読者を思い出してくれました。

catamの前の定義の問題は、それが再帰的であることです。したがって、INLINEへの任意の試みは無視されます。 -ddump-simpl -ddump-to-fileで元のバージョンをコンパイルし、core読み：

Main.depth2 = 
    \ (w_s1Rz :: Main.Tree) -> 
    case Main.$wdepth2 w_s1Rz of ww_s1RC { __DEFAULT -> 
    GHC.Types.I# ww_s1RC 
    } 

Rec { 
Main.$wdepth2 [Occ=LoopBreaker] :: Main.Tree -> GHC.Prim.Int# 
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType S] 
Main.$wdepth2 = 
    \ (w_s1Rz :: Main.Tree) -> 
    case w_s1Rz 
     `cast` (Main.NTCo:Fix <Main.TreeT> 
       :: Main.Fix Main.TreeT ~# Main.TreeT (Main.Fix Main.TreeT)) 
    of _ { 
     Main.Leaf -> 0; 
     Main.Tree l_aaj r_aak -> 
     case Main.$wdepth2 l_aaj of ww_s1RC { __DEFAULT -> 
     case Main.$wdepth2 r_aak of ww1_X1Sh { __DEFAULT -> 
     case GHC.Prim.<=# ww_s1RC ww1_X1Sh of _ { 
      GHC.Types.False -> ww_s1RC; 
      GHC.Types.True -> ww1_X1Sh 
     } 
     } 
     } 
    } 
end Rec } 

に比べ

Main.depth1 = Main.catam_$scatam @ GHC.Types.Int Main.depth3 

Main.depth3 = 
    \ (ds_dyI :: Main.TreeT GHC.Types.Int) -> 
    case ds_dyI of _ { 
     Main.Leaf -> Main.depth4; 
     Main.Tree l_aah r_aai -> GHC.Classes.$fOrdInt_$cmax l_aah r_aai 
    } 

Main.depth4 = GHC.Types.I# 0 

Rec { 
Main.catam_$scatam = 
    \ (@ a_ajB) 
    (eta_B1 :: Main.TreeT a_ajB -> a_ajB) 
    (eta1_X2 :: Main.Fix Main.TreeT) -> 
    eta_B1 
     (case eta1_X2 
      `cast` (Main.NTCo:Fix <Main.TreeT> 
        :: Main.Fix Main.TreeT ~# Main.TreeT (Main.Fix Main.TreeT)) 
     of _ { 
     Main.Leaf -> Main.Leaf @ a_ajB; 
     Main.Tree l_aan r_aao -> 
      Main.Tree 
      @ a_ajB 
      (Main.catam_$scatam @ a_ajB eta_B1 l_aan) 
      (Main.catam_$scatam @ a_ajB eta_B1 r_aao) 
     }) 
end Rec } 

は明らかに悪化している（catam_$scatamでコンストラクタの作成/削除、より多くの関数呼び出しを）しかし、我々は定義した場合catamとして

{-# INLINE catam #-} 
catam :: (Functor f) => (f a -> a) -> (Fix f -> a) 
catam f = let u = f . fmap u . unfix 
      in u 

これはもはや再帰的ではなく、uの内部のみです。

Main.depth1 = 
    \ (w_s1RJ :: Main.Tree) -> 
    case Main.$wdepth1 w_s1RJ of ww_s1RM { __DEFAULT -> 
    GHC.Types.I# ww_s1RM 
    } 

Rec { 
Main.$wdepth1 [Occ=LoopBreaker] :: Main.Tree -> GHC.Prim.Int# 
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType S] 
Main.$wdepth1 = 
    \ (w_s1RJ :: Main.Tree) -> 
    case w_s1RJ 
     `cast` (Main.NTCo:Fix <Main.TreeT> 
       :: Main.Fix Main.TreeT ~# Main.TreeT (Main.Fix Main.TreeT)) 
    of _ { 
     Main.Leaf -> 0; 
     Main.Tree l_aar r_aas -> 
     case Main.$wdepth1 l_aar of ww_s1RM { __DEFAULT -> 
     case Main.$wdepth1 r_aas of ww1_X1So { __DEFAULT -> 
     case GHC.Prim.<=# ww_s1RM ww1_X1So of _ { 
      GHC.Types.False -> ww_s1RM; 
      GHC.Types.True -> ww1_X1So 
     } 
     } 
     } 
    } 
end Rec } 

今depth2のダンプとしてちょうど同じである：ちょうど私たちが何をしたい - GHCのインラインdepth1のgとdepth1の定義におけるcatamと融合fmapがこの方法です。