Data/Typeable/Uniplate instances for GHC types
claus.reinke at talk21.com
Wed Jul 16 12:45:12 EDT 2008
> I find Uniplate to be completely the opposite. I always use the
> predefine schemes, and they are nearly always exactly what I want.
> Whether this is a difference in the traversals provided by the
> library, or in the mindset of the user of the library is still up for
Might help if library author and user are related?-) Or that Uniplate
does generalised selectors/modifiers, while SYB tries to do generalised
everything, which is sometimes too general for its own good?
Note that I'm not against Uniplate. I'm just trying to find out whether
there are serious reasons why I should be against SYB for the GHC
So far, I still think that SYB for GHC types is a good and necessary
first step. If adding Uniplate instances as well gives significant
improvements in efficiency or convenience, I won't argue against.
We probably agree on that?
>> touches String. Fortunately, all of the traversal schemes
>> have very short definitions, and we can define a variant that
>> allows us to do something useful with Strings, without traversing them.
> Yuk, much better to have something which just works (TM) without these
no hacks involved, just a minor variation on everywhere and
everywhereS :: GenericT -> GenericT
everywhereS f x
| isString x = f x
| otherwise = f (gmapT (everywhereS f) x)
isString x = typeOf x == typeOf ""
Note that we apply f to Strings (unlike everywhereBut), but
don't traverse them (unlike everywhere). Tracing the
differences shows the extra work done in a naive traversal:
g s = trace "*" (mkT (map toUpper) s)
x = ("there",True)
*Main> everywhere g x
*Main> everywhereBut isString g x
*Main> everywhereS g x
>> Ok, it would be interesting to know how much performance
>> remains lost, once a/b are addressed and only c is left (a factor of 2
>> might not be bad for the added flexibility, and is far lower
>> than the factors reported anecdotically, without details)
> Yes, but that means someone has to go in and tweak SYB. These
> things are not trivial.
Actually, the traversal schemes are fairly trivial, and reading the
source of Data.Generics.Schemes can be enlightening. Only the
underlying gfoldl, etc, and their types, are non-trivial.
>> and it would be good to know whether there are any other
>>performance killers in typical SYB usage.
> I'd guess at no. There are performance overheads (~30%) but no real killers.
I'd be tempted to agree. Just wanted to check whether the
scary anecdotes had anything new to add.
More information about the Cvs-ghc