#5622: Out of memory in such a simple case
---------------------------------+------------------------------------------
Reporter: quux | Owner:
Type: bug | Status: closed
Priority: normal | Milestone:
Component: Compiler | Version: 7.2.1
Resolution: invalid | Keywords:
Testcase: | Blockedby:
Difficulty: | Os: Windows
Blocking: | Architecture: x86_64 (amd64)
Failure: Compile-time crash |
---------------------------------+------------------------------------------
Changes (by simonpj):
* status: new => closed
* resolution: => invalid
Comment:
It is well known that Hindley-Milner type inference has worst-case
exponential time and space, and I think this is one such example.
Remember that GHC "fills in" the missing type arguments. So if you write
{{{
id True
}}}
GHC translates it to
{{{
id @Bool True
}}}
because we are instantiating id's type with `Bool`. Even compilers that
don't genreate the elaborated program do something internally in the type
inference engine that is more or less the same thing.
Now consider your example, with the type arguments filled in.
{{{
id id True
==> id @(Bool -> Bool) (id @Bool) True
id id id True
==> id @((Bool->Bool) -> (Bool->Bool)) (id @(Bool -> Bool)) (id @Bool)
True
...and so on
}}}
You can see that the types get big fast. As you add each new `id` the
size of the type doubles; hence the exponential.
Happily type inference is usually fine in practice. But its worst case is
Bad.
Simon
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5622#comment:2>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
