GHC를 변형 (catamorphisms)과 같은 일반 함수 (deforest)로 최적화 할 수 있습니까?

Question

정말 일반적인 방법으로 catamorphisms/anamorphisms 작업의 생각처럼,하지만 그것은 상당한 성능 단점이있다 나에게 보인다

가정 해 우리는 무조건적인 방법으로 트리 구조 작업 할이 - 설명하는 사용하여 다른 접이식 일반적인 catamorphism function :

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의 새 인스턴스가 g에 의해 즉시 사용되도록 fmap의 모든 레벨에서 생성됩니다. 고전적인 정의

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

에 비해 우리의 depth1 GC의에 불필요한 부담을 항상 느립니다. 한 가지 해결책은 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이 방법입니다.