Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#13218 closed bug (fixed)

<$ is bad in derived functor instances

Reported by: dfeuer Owned by: dfeuer
Priority: normal Milestone: 8.2.1
Component: Compiler Version: 8.1
Keywords: deriving-perf Cc: RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Functor deriving derives the definition of fmap, leaving the definition of <$ to the default. This is quite bad for recursive types:

data Tree a = Bin !(Tree a) a !(Tree a) | Tip deriving Functor

produces

Replace.$fFunctorTree_$c<$ =
  \ (@ a_aGl) (@ b_aGm) (eta_aGn :: a_aGl) (eta1_B1 :: Tree b_aGm) ->
    Replace.$fFunctorTree_$cfmap
      @ b_aGm @ a_aGl (\ _ [Occ=Dead] -> eta_aGn) eta1_B1

Why is this bad? It fills the tree with thunks keeping the original values (which we never use again) alive. What we want to generate is

x <$ Bin l _ r = Bin (x <$ l) x (x <$ r)

When there are other functor types in the constructor, like

  | Whatever (Tree (Tree a))

we will need to insert fmap (x <$) t. The overall shape should be basically the same as fmap deriving.

Note: there are some types for which we will not realistically be able to derive optimal definitions. In particular, fixed-shape, undecorated types that appear in nested types allow special treatment:

data Pair a = Pair a a deriving Functor
data Tree2 a = Z a | S (Tree2 (Pair a)) deriving Functor

The ideal definition for this type is

  x <$ Z _ = Z x
  x <$ S t = S (Pair x x <$ t)

but that requires cleverness. We should probably settle for

  x <$ Z _ = Z x
  x <$ S t = S (fmap (x <$) t)

Change History (4)

comment:1 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added
Keywords: deriving-perf added

comment:2 Changed 3 years ago by David Feuer <David.Feuer@…>

In 2219c8c/ghc:

Derive <$

Using the default definition of `<$` for derived `Functor`
instance is very bad for recursive data types. Derive
the definition instead.

Fixes #13218

Reviewers: austin, bgamari, RyanGlScott

Reviewed By: RyanGlScott

Subscribers: RyanGlScott, thomie

Differential Revision: https://phabricator.haskell.org/D3072

comment:3 Changed 3 years ago by dfeuer

Resolution: fixed
Status: newclosed

comment:4 Changed 3 years ago by RyanGlScott

Milestone: 8.4.18.2.1

This was originally marked for the 8.4.1 milestone, but happily, it made it in time for 8.2.1.

Note: See TracTickets for help on using tickets.