3 ms·

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 s

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

natte 12y ago
O(2^2^n) = O(4^n) = O(c^n) ; O(2^3^n) = O(8^n) = O(c^n) ; ...
- deleted 12y ago
  [deleted]
- deleted 12y ago
  [deleted]
- cousin_it 12y ago
  I think grandparent meant 2^(2^n), not (2^2)^n.
  - chengsun 12y ago
    Even so, O(4^n) != O(8^n); there is no constant k such that k * 4^n >= 8^n.
emillon 12y ago
I wrote an article on this example: http://blog.emillon.org/posts/2014-05-21-making-type-inference-explode.html 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.