The values Z, S Z, and S (S Z) all have the same runtime
representation and there is no linear increase in size when you add a
extra S.
BUT, if you make something overloaded and there is a dictionary
associated with the type (Z, S Z, or S (S Z)) then the dictionary
takes up space, and that space is linear in the number of S
constructors.
-- Lennart
On Tue, Aug 26, 2008 at 6:39 PM, wren ng thornton
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.
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.
From my experiments looking at memory usage, the above declarations take 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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe