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
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)
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
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?
More information about the Glasgow-haskell-users