यह इस तरह के रूप में catamorphisms GHC अनुकूलन (डीफॉरेस्ट) सामान्य कार्यों बनाने के लिए संभव है?

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 

दुर्भाग्य से, इस दृष्टिकोण एक महत्वपूर्ण दोष यह है: Dur गणना ing, TreeT Int के नए उदाहरणों सिर्फ तुरंत g से भस्म किया जाना fmap में हर स्तर पर बनाया जाता है। शास्त्रीय परिभाषा

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

की तुलना में हमारे depth1 हमेशा धीमी जीसी पर अनावश्यक तनाव बना रही हो जाएगा। एक समाधान hylomorphisms का उपयोग करना होगा और एक साथ सृजन और तह पेड़ को जोड़ना होगा। लेकिन अक्सर हम देखते हैं कि, हम चाहते हो सकता है एक पेड़ एक ही स्थान पर पर बनाया जाना है और फिर कहीं और से पारित कर दिया बाद में तह किया जा करने के लिए नहीं करना चाहती। या, विभिन्न catamorphisms के साथ कई बार फ़ोल्डर होने के लिए।

वहाँ 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.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 अंदर है। इस तरह GHC inlines depth1 के g साथ depth1 की परिभाषा में catam और फ़्यूज़ fmap - बस हम क्या चाहते हैं:

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 के डंप के रूप में सिर्फ एक ही है।