[GHC] #7542: GHC doesn't optimize (strict) composition with id

[GHC]

#7542: GHC doesn't optimize (strict) composition with id
---------------------------------+------------------------------------------
    Reporter:  shachaf           |       Owner:                         
        Type:  bug               |      Status:  new                    
    Priority:  normal            |   Milestone:                         
   Component:  Compiler          |     Version:  7.6.1                  
    Keywords:                    |          Os:  Unknown/Multiple       
Architecture:  Unknown/Multiple  |     Failure:  Runtime performance bug
  Difficulty:  Unknown           |    Testcase:                         
   Blockedby:                    |    Blocking:                         
     Related:                    |  
---------------------------------+------------------------------------------
Changes (by shachaf):

  * status:  infoneeded => new


Comment:

 Here's an example of the sort of context this comes up in:

 {{{
 module T7542 where

 import Unsafe.Coerce

 newtype Id a = MkId { unId :: a }

 -- Think of `mapped` as `mapM`, but restricted to Id (we could make it
 work
 -- with any Functor, rather than just []). `over` takes the Id wrappers
 back
 -- off. The goal is to make it easy to compose mapped with other functions
 of
 -- the same form. The wrapper should be "free" because it's just newtype
 noise.

 mapped1 :: (a -> Id b) -> [a] -> Id [b]
 mapped1 f = MkId . map (unId . f)

 over1 :: ((a -> Id b) -> s -> Id t) -> (a -> b) -> s -> t
 over1 l f = unId . l (MkId . f)

 map1 :: (a -> b) -> [a] -> [b]
 map1 f xs = over1 mapped1 f xs
 -- Core: map1 = \f xs -> map (\x -> f x) xs

 -- over1 mapped1 = unId . MkId . map (unId . MkId . f)
 --               ~ map
 -- However, if f = ⊥, unId . MkId . f /= f!
 -- Therefore `over1 mapped1` must turn into \f -> map (\x -> f x)
 -- We can't expect GHC to compile it to `map` because it has different
 strictness.

 -- Let's define strict versions of (MkId .) and (unId .):
 mkIdDot2 :: (a -> b) -> a -> Id b
 mkIdDot2 f = f `seq` \x -> MkId (f x)

 unIdDot2 :: (a -> Id b) -> a -> b
 unIdDot2 f = f `seq` \x -> unId (f x)

 mapped2 :: (a -> Id b) -> [a] -> Id [b]
 mapped2 f = mkIdDot2 (map (unIdDot2 f))

 over2 :: ((a -> Id b) -> s -> Id t) -> (a -> b) -> s -> t
 over2 l f = unIdDot2 (l (mkIdDot2 f))

 map2 :: (a -> b) -> [a] -> [b]
 map2 f xs = over2 mapped2 f xs
 -- map2 should have the same semantics as map. But the Core isn't the
 same:
 -- Without -fpedantic-bottoms: map2 = \f xs -> map (\e -> f e) xs
 -- With -fpedantic-bottoms:
 -- map2 = \f xs -> map (case f of g { __DEFAULT -> \x -> g x }) xs
 -- Ideally, (case f of g { __DEFAULT -> \x -> g x }) would simply be f.

 -- Let's try manually telling GHC that our newtype compositions are
 coercions:
 -- (Ideally, this is what mkIdDot2 and unIdDot2 would compile into.)
 mkIdDot3 :: (a -> b) -> a -> Id b
 mkIdDot3 = unsafeCoerce

 unIdDot3 :: (a -> Id b) -> a -> b
 unIdDot3 = unsafeCoerce
 -- (Note: Due to #7398, we couldn't define a strict composition operator
 and
 -- rely on RULES to turn (MkId `dot`) into unsafeCoerce -- the `MkId`
 itself
 -- gets turned into a coercion before any RULES have a chance to fire.)

 mapped3 :: (a -> Id b) -> [a] -> Id [b]
 mapped3 f = mkIdDot3 (map (unIdDot3 f))

 over3 :: ((a -> Id b) -> s -> Id t) -> (a -> b) -> s -> t
 over3 l f = unIdDot3 (l (mkIdDot3 f))

 map3 :: (a -> b) -> [a] -> [b]
 map3 f xs = over3 mapped3 f xs
 -- Core: map3 = map
 }}}

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/7542#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler