23

一般的な方法でカタモルフィズム/アナモルフィズムを操作するというアイデアは本当に気に入っていますが、パフォーマンスに重大な欠点があるように思えます。

カテゴリカルな方法でツリー構造を操作したいとします。つまり、一般的なカタモルフィズム関数を使用してさまざまな折り畳みを記述します。

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

これで、次のような関数を書くことができます:

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

残念ながら、このアプローチには重大な欠点があります。計算中に、 のTreeT Intすべてのレベルで の新しいインスタンスが作成され、fmapによってすぐに消費されgます。古典的な定義と比較して

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

depth1常に遅くなり、GC に不要な負荷がかかります。解決策の 1 つは、ハイロモーフィズムを使用して、作成ツリーとフォールディング ツリーを組み合わせることです。しかし、多くの場合、それをしたくありません。ツリーをある場所で作成し、後で折り畳むために別の場所に渡したい場合があります。または、異なるカタモルフィズムで数回フォルダーに入れます。

GHC を最適化する方法はありdepth1ますか? インライン化してから内部で融合/伐採するようなものcatam gですか? g . fmap ...

4

1 に答える 1

17

私は答えを見つけたと信じています。なぜGHCは修正をそれほど混乱させるのかを読んだことを思い出しました。そしてそれは私に解決策を提案しました。

以前の の定義の問題は、catam再帰的であるため、INLINEを試みても無視されることです。コアを使用して元のバージョンをコンパイルし -ddump-simpl -ddump-to-file、読み取る:

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、より多くの関数呼び出し）

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 }

しかし、次のように定義するcatamと

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

その場合、再帰的ではなくなり、u内部のみが再帰的になります。このように、GHCcatamは の定義をインライン化し、depth1と融合fmapしdepth1ますg。

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。

于 2012-10-28T05:27:42.927 に答える