Slow Typechecking (Followup of #14987)

Summary

Type Checking consumes an exponential amount of memory and is consequently very slow in the presence of complicated pattern matching. This is a followup of #14987 (closed)

The attached files have been generated with Template Haskell and are essentially a self-contained version of a stack build --ghc-options="-ddump-splices -ddump-to-file" of this repository.

Steps to reproduce

Compile the attached files. Might be a good idea to ulimit -m the shell before calling the compiler to prevent the machine from freezing.

Go-hdiff-900744.hs

Python-hdiff-e009013.hs

Structure of Attached Files

The structure of the attached files is simple, but very long and mechanical (hence why we are using TH!). It consists of a generic instance for mutually recursive types using the generics-mrsop library. For example,

data A = A0 Int | A1 B
data B = B0 Char | B1 A

-- Now, call the TH to generate the monstrous code
deriveFamily ''Singl [t| A |]

would yield something in the lines of

type FamA   = [ A , B ]
type CodesA = [  [ [ Int ] , [I (S Z)] ]
               , [ [ Char ], [I Z] ] ]

instance Family Singl FamA CodesA where
  sfrom SZ (A0 c) = Rep (Here (c :* Nil))
  sfrom SZ (A1 b) = Rep (There (Here (b :* Nil))
  sfrom (SS SZ) (B0 c) = Rep (Here (c :* Nil))
  sfrom (SS SZ) (B1 a) = Rep (Here (There (a :* Nil))
 
  sto ... -- inverse of sfrom

The attached files are the versions we get from attempting to use language-go or language-python with generics-mrsop.

Environment

• GHC version used: 8.4.2, 8.6.5