Data/Typeable/Uniplate instances for GHC types

[Claus Reinke]

>>  in SYB were (a) traversing irrelevant parts of the structure
>>  (because everything is treated generically)
> 
> Yes, this is a big one. In particular Haskell String's being defined
> as [Char] makes SYB do a lot of redundant work on characters which are
> unlikely to be the target. SYB's types for everything/everywhere are
> too general to allow the Uniplate solution, but it would be easy to
> add universe/transform to SYB and implement them using them much more
> efficiently.

It has been a while, and most of my experience was with 
Strafunski's StrategyLib, but I seem to recall using the predefined
schemes more as patterns for defining my own schemes than as
a directly useable library - in spite of the variety of schemes provided,
often none of them it quite the thing you want. So the SYB API
(the high-level form) is "virtual", in the spirit of the examples 
exhibited in the pre-defined traversal schemes.

In this case, everywhere always traverses String while 
everywhereBut (mkQ (const True::String->Bool)) never
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.
 
>(c) repeated runtime type checks to determine which function to apply.
> 
> Yes, very expensive. The absense of these tests doubles performance in
> Uniplate. I don't see a way to remove them using SYB.
> 
> So, using rough intuition, I'd say a > c > b in terms of the cost. b
> is fairly trivial to fix, a requires an API change, c probably can't
> be eliminated easily.

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), and it 
would be good to know whether there are any other performance
killers in typical SYB usage.
 
Claus