Graphs

[Jan-Willem Maessen]

David Feuer <dfeuer@cs.brown.edu> writes:
> I seem to remember an article about functional graph algorithms using
> extra-lazy arrays.  Anyone know if these arrays have appeared in any
> mainstream implementation?

I assume you're referring to this paper by Thomas Johnsson:

@Article{lazyArray,
  author = 	 {Johnsson, Thomas},
  title = 	 {Efficient Graph Algorithms Using Lazy Monolithic Arrays},
  journal = 	 JFP,
  year = 	 1998,
  volume =	 8,
  number =	 4,
  pages =	 {323--333},
  month =	 {July}
}

He uses similar techniques to do whole-program flow analysis of
Haskell programs, a clever bit of coding described in the following
paper:

@inproceedings{grinHeap,
  AUTHOR = "Johnsson, Thomas",
  TITLE = "Analysing Heap Contents in a Graph Reduction Intermediate Language.",
  booktitle = Proc # "Glasgow Functional Programming Workshop",
  address = "Ullapool 1990",
  MONTH = "August",
  YEAR = 1991
}

The LazyArray library is part of the standard hbc distribution.  The
Eager Haskell compiler depends on it (you can get very nice static
hash tables this way, among other things).  As a result, I've done a
port of the library to GHC (and, I think, hugs).  I should note that
most of the hints required to pull off the implementation were found
in the "State in Haskell" paper by Simon PJ and John Launchbury.  The
library is available (along with a few other useful snippets, like
universal splittable supplies) here:

http://www.csg.lcs.mit.edu/~earwig/haskell-lib/

-Jan-Willem Maessen