On Thu, Sep 22, 2011 at 03:55, Bas van Dijk <v.dijk.bas@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@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users