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) ;
...
(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).