Exponential behaviour with type synonyms

[simonpj]

You're quite right.  GHC has a simple but non-
performant representation of type synonyms in types, so 
as to be able to generate good error messages,  In 
particular, the type

	S t

where S is a type synonym defined by 'type S a = s', is 
represented as

	SynNote (S t) (s [t/a])

That is, (S t) is represented by *both* its un-expanded 
and expanded form.  

The SynNote is ignored by unification, but the un-
expanded form is useful for error messages.  
Unfortunately, t is duplicated, as you can see, and that 
leads to the behaviour you describe.

I don't see myself fixing this soon, at least partly 
because I can't see an obvious way to fix it that doesn't 
lose error message behaviour.

I'm going to open a SourceForge bug for it.  If anyone 
has good ideas, let me know.

Simon

| -----Original Message-----
| From: glasgow-haskell-bugs-bounces@haskell.org 
[mailto:glasgow-haskell-bugs-
| bounces@haskell.org] On Behalf Of Iavor Diatchki
| Sent: 17 February 2005 01:27
| To: glasgow-haskell-bugs@haskell.org
| Subject: 'type' declarations
| 
| hello,
| ghc seems to be having trouble with 'type' declarations.
| while compiling (i guess kind checking is the correct 
word here)
| the following program for a very long time, ghc (6.2) 
runs out of 300Mb of heap.
| 
| module Test where
| 
| type S          = Maybe
| type S2 n       = S  (S  n)
| type S4 n       = S2 (S2 n)
| type S8 n       = S4 (S4 n)
| type S16 n      = S8 (S8 n)
| type S32 n      = S16 (S16 n)
| 
| type N64 n      = S32 (S32 n)
| 
| type N64'       =
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   S ( S ( S ( S ( S ( S ( S ( S (
|   Int
|   ))))))))
|   ))))))))
|   ))))))))
|   ))))))))
|   ))))))))
|   ))))))))
|   ))))))))
|   ))))))))
| 
| if i remove the N64 definition things work.  i guess 
something
| exponential is happening
| (substitution?).
| 
| -iavor

[simonpj]

Logged In: YES 
user_id=50165

I've fixed the exponential behaviour arising from synonyms 
being held in both expanded and unexpanded form.  The test 
is tc199.hs.

However, this SourceForge bug has a type that genuinely is 
exponential in the program size, so it remains un-fixed.

Simon

[simonpj]

Happily, this is fixed in GHC 6.8.

I've enabled the test, which is syn-perf2

(But test tc199 seems unrelated.)

Simon