On Feb 23, 2008, at 5:48 PM, apfelmus wrote:
Henning Thielemann wrote:
It seems that algorithms on graphs can be implemented particularly
efficient in low-level languages with pointers and in-place
updates. E.g.
topological sort needs only linear time, provided that dereferencing
pointers requires constant time. I could simulate pointer
dereferencings
and pointer updates by Map yielding linear logarithmic time for
topological sort. I wonder if it is possible to write a linear time
topological sort using lazy evaluation, since the runtime system of
Haskell implementations is a graph processor based on pointers.
First of all, topological sorting is only linear time because the 32
or 64 bit used to label nodes aren't counted. Put differently,
random access in constant time to a collection of n elements
doesn't exist.
That being said, we want to use arrays of course. Preferably in a
"whole-meal" way that doesn't involve incremental state updates. A
few minutes ago, I stumbled upon the lazyarray packages which
points to the paper
Thomas Johnsson.
"Efficient Graph Algorithms Using Lazy Monolithic Arrays"
http://citeseer.ist.psu.edu/95126.html
which offers such a way! (Although I currently don't quite
understand why this works, and these ad-hoc unique numbers bother me.)
I have an implementation of this in GHC based on some of the early ST
papers, if anyone is interested. It's rather old and may have bit-
rotted; cabalizing it is at the top of "whenever-I-get-time", along
with generic splittable supplies. Note that getting the laziness
right is somewhat tricky.
-Jan-Willem Maessen
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
