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 <[EMAIL PROTECTED]> wrote: > 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
