Replace Lists with Data.Sequence in edge lists.

[wuerges]

Since it is not really possible to know before hand if a ++ b is faster than b ++ a, it might be better to use Data.Sequence.

This change can improve fgl's (&) performance from O(n) to potentially O(1), without loss of generality or ease of use.

I noticed this when the following change reduced my memory usage by half:
wuerges/vlsi_verification@45e7c30?diff=unified#diff-014d188201674e3d3062b5a764945832

This is due to fastInsEdge being implemented with addLists instead of (++)

I could evaluate this because my particular Graph has a huge amount of inn edges for each node and at most 2 out edges. The change above only made any difference in memory consumption when changing the input edge list, not the output.

[ivan-m]

Is this still the case with #62 merged in?

[wuerges]

Yes, #62 only fixes it if you are adding one edge at a time. If you add n edges at O(1), it gets O(n).

Consider the case where you are merging nodes in a Graph (which is very important in my project):
Ideally, you would do something like this:

let (Just (is1, _, v, os1), g1) = match n1 g0
    (Just (is2, _, _, os2), g2) = match n2 g1
    g3 =  (is1 ++ is2, n1, v, os1 ++ os2)  & g2

Since the Adj use regular lists, currently, it will be O(n). Using Seq it would be O(log(n))

What I'm now wondering is if it is possible to change the inner workings of fgl to work with something like Monoid or Foldable, or some other type class instead of lists.
This way, it would be possible to keep compatibility with the current API.

Anyway, I'll investigate it further in the next week, and provide some evidence if it is something really important.

[wuerges]

It seems #62 fixed my space leaks.
After 120 seconds, my project was using 7GB of memory, and now it is using only 35 MB. Execution time is still an issue, however.

[wuerges]

Ok, I've been working on this problem in my project and my conclusion is that the problem is with my algorithm and lists are more than fine to represent edges.

Therefore, this issue should be closed.