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

[wren ng thornton]

Lennart Augustsson wrote:
> 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.

Ah yes, that makes more sense. Since your instance would look like:

     instance Foo a => Foo (S a) where
         foo :: a -> Int

a dictionary for Foo (S(S Z)) would have entries for foo@(S(S Z)) and 
also the dictionary for Foo (S Z) which has foo@(S Z) and a dictionary 
for Foo Z which has...

It's still something to watch out for if you're really worrying about 
performance. I wonder if this is documented on the wiki's section about 
performance anywhere, the overhead for inductive type class instances I 
mean.

-- 
Live well,
~wren