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

[Lennart Augustsson]

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 <wren at freegeek.org> 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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>