Hi, Am Montag, den 30.01.2017, 16:41 -0500 schrieb David Feuer:
Here's an example:
data Tree a = Bin (Tree a) a (Tree a) | Tip deriving Functor
{-# NOINLINE replace #-} replace :: a -> Tree b -> Tree a replace x t = x <$ t
When I compile this with -O2, I get
Rec { -- RHS size: {terms: 18, types: 21, coercions: 0} $fFunctorTree_$cfmap :: forall a_ar2 b_ar3. (a_ar2 -> b_ar3) -> Tree a_ar2 -> Tree b_ar3 $fFunctorTree_$cfmap = \ (@ a_aGb) (@ b_aGc) (f_aFH :: a_aGb -> b_aGc) (ds_dGN :: Tree a_aGb) -> case ds_dGN of _ { Bin a1_aFI a2_aFJ a3_aFK -> Bin ($fFunctorTree_$cfmap f_aFH a1_aFI) (f_aFH a2_aFJ) ($fFunctorTree_$cfmap f_aFH a3_aFK); Tip -> Tip } end Rec }
$fFunctorTree_$c<$ :: forall a_ar4 b_ar5. a_ar4 -> Tree b_ar5 -> Tree a_ar4 $fFunctorTree_$c<$ = \ (@ a_aGQ) (@ b_aGR) (eta_aGS :: a_aGQ) (eta1_B1 :: Tree b_aGR) -> $fFunctorTree_$cfmap (\ _ -> eta_aGS) eta1_B1
replace :: forall a_aqt b_aqu. a_aqt -> Tree b_aqu -> Tree a_aqt replace = $fFunctorTree_$c<$
This is no good at all, because replacing the values in the same tree over and over will build up a giant chain of thunks in each node carrying all the previous values. I suppose that inlining per se may not be quite enough to fix this problem, but I suspect there's some way to fix it. Fixing it in Functor deriving would be a start (I can look into that), but fixing it in user code would be quite good too.
as far as I can tell, this would require * static argument transformation, which would make $fFunctorTree_$cfmap non-recursive (with a recursive local function which would *not* take f_aFH as an argument). * hen you’d have to inline that into $fFunctorTree_$c<$. This would duplicate the local recursive function, so not sure how eager GHC would do that. * And then finally inline (\ _ -> eta_aGS) into the duplicated local recursive function, which will then yield great code. https://ghc.haskell.org/trac/ghc/ticket/9374 is relevant. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org