large performance regression in type checker speed in 7.8

it was recently demonstrated on the haskell-cafe mailing list that the following code takes measurably longer to type check in GHC 7.8.2 than in GHC 7.6.

http://www.haskell.org/pipermail/haskell-cafe/2014-June/114562.html

the program example is as follows

begin :: Monad m => (m () -> t) -> t
begin cont = cont (return ())
 
a :: IO a -> (IO () -> t) -> t
a m cont = cont (m >> putStrLn "a")
 
end :: t -> t
end m = m
 
main = begin a a a a a a a a a a a a a a a a a a end

takes about a second to type check in ghc 7.8, and is "instant" in 7.6 ()

each additional a doubles the time to type check the program

main = begin a a a a a a a a a a a a a a a a a a a a a a a a end

takes longer than I have the patience to wait :) (so more than 5 seconds)

the author of the email notes that a related program

  main = id id id id id id id id id id id
         id id id id id id id id id id id (return ())

has the exponential complexity in both 7.8.2 and 7.6.2

This It could very well be that some of the type checker changes between 7.8 and 7.6 enlarged the space of programs that trip up exponential worst case behavior, but one way or another understanding *why* this happened