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
_______________________________________________
Cvs-ghc mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/cvs-ghc
