You'd probably be interested to read
http://www.cs.chalmers.se/~koen/pubs/entry-asian99-lava.html
On Jan 31, 2008 9:56 PM, Jan-Willem Maessen
On Jan 31, 2008, at 5:39 AM, 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.
If so, I'd love to see this written up; I think it may be publishable if it isn't published already.
Note that even using ST techniques can take more than linear time, given an arbitrary purely-functionally-defined graph as input. We can't (eg) assume that each node contains a reference, or that they are densely numbered, so we end up having to look them up in some fashion (though using a hash table can be reasonably quick if we uniquely number nodes).
-Jan-Willem Maessen
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe