[Haskell-cafe] Re: ANN: First Monad Tutorial of the Season

[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