Type (class) recursion + families = exponential compile time?

[Ben Lippmeier]

Here's the reference
http://portal.acm.org/citation.cfm?id=96748

"Deciding ML typability is complete for deterministic exponential  
time" -- Harry G. Mairson.

Ben.


On 27/02/2009, at 10:12 AM, Ben Franksen wrote:

> Hi
>
> the attached module is a much reduced version of some type-level  
> assurance
> stuff (inspired by the Lightweight Monadic Regions paper) I am  
> trying to
> do. I am almost certain that it could be reduced further but it is  
> late and
> I want to get this off my desk.
>
> Note the 4 test functions, test11 .. test14. The following are  
> timings for
> compiling the module only with all test functions commented out,  
> except
> respectively, test11, test12, test13, and test14:
>
> ben at sarun[1] > time ghc -c Bug2.hs
> ghc -c Bug2.hs  1,79s user 0,04s system 99% cpu 1,836 total
>
> ben at sarun[1] > time ghc -c Bug2.hs
> ghc -c Bug2.hs  5,87s user 0,14s system 99% cpu 6,028 total
>
> ben at sarun[1] > time ghc -c Bug2.hs
> ghc -c Bug2.hs  23,52s user 0,36s system 99% cpu 23,899 total
>
> ben at sarun[1] > time ghc -c Bug2.hs
> ghc -c Bug2.hs  102,20s user 1,32s system 97% cpu 1:45,89 total
>
> It seems something is scaling very badly. You really don't want to  
> wait for
> a version with 20 levels of nesting to compile...
>
> If anyone has a good explanation for this, I'd be grateful.
>
> BTW, I am not at all certain that this is ghc's fault, it may well  
> be my
> program, i.e. the constraints are too complex, whatever. I have no  
> idea how
> hard it is for the compiler to do all the unification. Also, the  
> problem is
> not of much practical relevance, as no sensible program will use  
> more than
> a handfull levels of nesting.
>
> Cheers
> Ben
> <Bug2.hs>_______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users