Associativity of the generic representation of sum types
José Pedro Magalhães
jpm at cs.uu.nl
Thu Sep 22 02:33:54 CEST 2011
On Thu, Sep 22, 2011 at 03:55, Bas van Dijk <v.dijk.bas at gmail.com> wrote:
> 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:
> 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 <|>:
> 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
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
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Glasgow-haskell-users