[Haskell-cafe] fast graph algorithms without object identities

Henning Thielemann lemming at henning-thielemann.de
Thu Jan 31 05:39:40 EST 2008

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.

More information about the Haskell-Cafe mailing list