Associativity of the generic representation of sum types

Bas van Dijk v.dijk.bas at gmail.com
Wed Sep 21 20:55:17 CEST 2011


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)

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.

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?

Regards,

Bas



More information about the Glasgow-haskell-users mailing list