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 <[EMAIL PROTECTED]> wrote: > > 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 > > [email protected] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
