Associativity of the generic representation of sum types

[José Pedro Magalhães]

Hi Bas,

On Thu, Sep 22, 2011 at 03:55, Bas van Dijk <v.dijk.bas at gmail.com> wrote:

> Hello,
>
> I just used the new GHC generics together with the DefaultSignatures
> extension to provide a default generic implementation for toJSON and
> parseJSON in the aeson package:
>
> https://github.com/mailrank/aeson/pull/26
>
> It appears that the generic representation of a sum type has a tree shape
> as in:
>
> (a :+: b) :+: (c :+: d)
>

That is correct.


>
> In my case this tree-shaped representation is problematic when parsing
> a JSON value to this type. My overloaded parsing function is
> parameterized with a key which specifies which of the a, b, c or d
> constructors to parse. When it encounters a constructor it checks if
> it matches the key, if so it is parsed, if not parsing will fail.
> Because of the tree-shaped representation of sum types I have to
> recursively parse the left and right branch and join them using <|>:
>
>
> https://github.com/basvandijk/aeson/blob/d5535817ceb192aa9d7d0d0b291e1901f3fbb899/Data/Aeson/Types/Internal.hs#L1003
>
> I don't know for sure but I suspect that this can cause memory leaks
> since the <|> has to keep the right value in memory when it is parsing
> the left.
>

It is not immediately clear to me why this would cause memory leaks...


>
> Ideally the generic representation of sum types is right associative as in:
>
> a :+: (b :+: (c :+: d))
>
> This way I only have to check if 'a' matches, if it does the right
> branch can be forgotten.
>
> Is there a good reason for not having it right associative?
>

The reason is performance. In particular for large datatypes with many
constructors, a balanced sum-of-products performs better than a right-nested
one. Also, it makes things like writing generic space-efficient
encoders/decoders easier.

But I would be very interested in understanding if/how the balanced view
leads to a space leak, so please let me know if you can provide some more
information.


Thanks,
Pedro


>
> Regards,
>
> Bas
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20110922/5c5b4513/attachment.htm>