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

[Lennart Augustsson]

Just Hindley-Milner type inference is exponential, making the type
system more complex isn't going to make things better.

2009/2/26 Ben Franksen <ben.franksen at online.de>:
> 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
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
>