Data/Typeable/Uniplate instances for GHC types
claus.reinke at talk21.com
Mon Jul 21 10:17:55 EDT 2008
|if I apply this to the SYB traversal, I get the expected speedup.
|Now I need to clean up the mess I made of the source while
|experimenting, and see how to extract this adaptation of the
|Uniplate trick for general SYB use.
I've slightly cleaned up my code and posted it, with some
explanation of context and ideas, to generics at haskell (which
seemed more on-topic than this list, even though it is often all
too silent to be of much use):
Data.Generics with GPS (using Maps to avoid getting lost in Data)
If there is positive feedback, perhaps Data.Generics.GPS might
be added to Syb, to help reducing the performance overhead of
Syb traversals to that of Uniplate over Data (once Uniplate is fixed).
> Uniplate does one traversal from Company -> Salary, using the Biplate
> mechanism. Once it has reached a salary, it then does a Uniplate
> traversal from Salary -> Salary. Hence it has to do Company/Salary and
> Salary/Salary. I do wonder if the Salary/Salary traversal is
> under-optimised by using a Map when only Float is a child.
> It seems an interesting issue, whatever it is. It also seems to bite
> as data structures get very large, which makes it less of a pressing
> issue at least in my particular uses. Once I've got some more data I'm
> sure I'll track it down.
Please do - I suspect that GHC structures can become quite large,
and though they might not be as big as that benchmark, the penalty
In the trace-instrumented experiments, I noticed that the type map
for Company is built right at the beginning, the type map for Salary
close to the end, with a lot of delay in between, suggesting a large
intermediate data structure between the two traversals might be
to blame. Shouldn't the two traversals be interleaved?
More information about the Cvs-ghc