Data/Typeable/Uniplate instances for GHC types
claus.reinke at talk21.com
Wed Jul 16 11:14:31 EDT 2008
>> 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
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
>(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.
More information about the Cvs-ghc