Constant functions and selectors make for interesting arguments

[Joachim Breitner]

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 at joachim-breitner.de • https://www.joachim-breitner.de/
  XMPP: nomeata at joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20170130/74905812/attachment.sig>