Ryan Ingram wrote:
wren ng thornton wrote:
It should also be noted that the overhead for newtypes is not *always* removed. In particular, if we have the following definitions:
data Z = Z newtype S a = S a
We must keep the tags (i.e. boxes) for S around because (S Z) and (S (S Z)) need to be distinguishable. This only really comes up with polymorphic newtypes (since that enables recursion), and it highlights the difference between strict fields and unpacked strict fields. Typically newtypes are unpacked as well as strict (hence no runtime tag overhead), but it's not guaranteed.
Is this true? (S Z) and (S (S Z)) only need to be distinguished during typechecking.
This would be different if it was some sort of existential type:
newtype N = forall a. Num a => N a but GHC at least disallows existential boxes in newtypes.
From my experiments looking at memory usage, the above declarations take
They only need to be distinguished at type checking time, true; but if you have a function that takes peano integers (i.e. is polymorphic over Z and (S a) from above) then you need to keep around enough type information to know which specialization of the function to take. The problem is that the polymorphism means that you can't do full type erasure because there's a type variable you need to keep track of. the same amount of memory as a pure ADT, which means linear in the value of the peano integer. It may be that I misinterpreted the results, but I see no other way to deal with polymorphic newtypes so I'm pretty sure this is what's going on. -- Live well, ~wren