Performance of Data.Graph.{preorderF, postorderF}

The functions can be quite slow in some cases, but it's easy to improve the performance. I've just used Data.Sequence instead of ordinary lists. This makes especially large difference for scc (strongly connected components). In one extreme case I found:

benchmarking extreme case, original: scc
collecting 100 samples, 1 iterations each, in estimated 1.521492 s
bootstrapping with 100000 resamples
mean: 15.38460 ms, lb 15.35417 ms, ub 15.41660 ms, ci 0.950
std dev: 160.7804 us, lb 144.4490 us, ub 184.5445 us, ci 0.950
variance introduced by outliers: 0.990%
variance is unaffected by outliers

benchmarking extreme case, new: scc
collecting 100 samples, 12 iterations each, in estimated 559.8664 ms
bootstrapping with 100000 resamples
mean: 480.0413 us, lb 477.9581 us, ub 483.2204 us, ci 0.950
std dev: 13.01511 us, lb 9.219410 us, ub 22.67802 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
  3 (3.0%) low mild
  1 (1.0%) high severe
variance introduced by outliers: 0.998%
variance is unaffected by outliers

The patch is attached. I've also written some example code to illustrate the performance differences and two small quickcheck tests.

What do you think about it?

Trac metadata

Trac field	Value
Version	7.0.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	libraries (other)
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture