#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I have often wondered if it wouldn't be better to change `Type`s concrete representation to avoid this kind of problem structurally. To wit: {{{#!hs data Type = TyVarTy TyVar | TyConTy TyCon | AppTys Type [Type] -- INVARIANT 1: List is not empty. -- INVARIANT 2: The head type is not an AppTys | ForAllTy ... | LitTy ... | CastTy ... | CoercionTy ... }}} Note that INVARIANT 1 is needed to avoid confusion between, e.g., `AppTys (TyVarTy a) []` and `TyVarTy a`. We could perhaps do even better using `Seq Type` instead of `[Type]` as the container in `AppTys`, given that we sometimes need access to both ends. It might be an interesting experiment to see if performance improves with this change. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler