[Haskell-cafe] Re: fast graph algorithms without object identities

[Jan-Willem Maessen]

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