[GHC] #8147: Exponential behavior in instance resolution on fixpoint-of-sum

[GHC]

#8147: Exponential behavior in instance resolution on fixpoint-of-sum
-------------------------------------+-------------------------------------
        Reporter:  jkoppel           |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.6.3
      Resolution:                    |             Keywords:  performance,
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Although there's still a bug, it has changed somewhat. We now get a
 context reduction stack overflow:

 {{{
 Test.hs:43:8: error:
     • Reduction stack overflow; size = 201
       When simplifying the following type:
         Functor
           (X201
            :+: (X202
                 :+: (X203
                      :+: (X204
                           :+: (X205

 ...

       Use -freduction-depth=0 to disable this check
       (any upper bound you could choose might fail unpredictably with
        minor updates to GHC, so disabling the check is recommended if
        you're sure that type checking should terminate)
     • In the expression: cata lift'
       In an equation for ‘lift’: lift = cata lift'
    |
 43 | lift = cata lift'
    |        ^^^^^^^^^^
 }}}

 Removing the reduction depth limit brings my machine to its knees. I can
 compile the program with `n=120` and a reduction depth limit of 300.

 One other thing of note: removing the redundant `Functor` constraint on
 the `Lift f g` instance (which for some reason is not detected as
 redundant in 8.2.1, though it was in 8.0.2) improves matters considerably,
 but they're still pretty bad even in that case.

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