3 ms·
As an aside, Hindley–Milner is DEXPTIME-complete, and indeed you can write 5 line programs that exhibit the worst-case behaviour. That's as bad a worst-case beh
by mafribe 11y ago
As an aside, Hindley–Milner is DEXPTIME-complete, and indeed you can write 5 line programs that exhibit the worst-case behaviour. That's as bad a worst-case behaviour as undecidability for all practical purposes.
That said, in practise, HM type inference tends to be very fast, because the worst-case behaviour only shows up in rather artificial programs that human programmers would normally not write. If you bound the depth of let-nesting, HM is polynomial.
- quchen 11y agoYou're correct on the theoretical side, and writing a value whose type makes GHC crash is fairly easy. But in multiple years of Haskell, I did not encounter nor have I heard of a practical case in which type inference time was a performance issue, let alone a bottleneck or problem.