News for hackers. Stuff that matters.
Re:Look at the humongous type that Hindley-Milner infers for... by throwaway_yy2Di on Monday August 04, 2014 @02:59AM (#8130668)
What about this example?

    f0 x = (x,x)
    f1 x = f0 (f0 x)
    f2 x = f1 (f1 x)
    f3 x = f2 (f2 x)
    f4 x = f3 (f3 x)
This is worse than O(c^n): the size of the last function's type is O(2^2^n).

(In spacemanaki's blog example, each new expression doubles the size of the previous one. Here, each new expression squares the size. f4 builds 2^2^4 = 65,536 copies of 'x', and f5 will crash your compiler if you define it).

Re:Look at the humongous type that Hindley-Milner infers for... by emillon on Monday August 04, 2014 @08:59AM (#8131517)
I wrote an article on this example:

http://blog.emillon.org/posts/2014-05-21-making-type-inferen...

At first I expected something of the form O(2^n) too but DEXPTIME actually contains O(2^p(n)) where p is a polynomial.

Re:Look at the humongous type that Hindley-Milner infers for... by natte on Monday August 04, 2014 @04:27AM (#8130804)
O(2^2^n) = O(4^n) = O(c^n) ; O(2^3^n) = O(8^n) = O(c^n) ; ...
Re:Look at the humongous type that Hindley-Milner infers for... by cousin_it on Monday August 04, 2014 @04:36AM (#8130834)
I think grandparent meant 2^(2^n), not (2^2)^n.
Re:Look at the humongous type that Hindley-Milner infers for... by chengsun on Monday August 04, 2014 @04:46PM (#8133923)
Even so, O(4^n) != O(8^n); there is no constant k such that k * 4^n >= 8^n.