Jan-Willem Maessen
Sat, 23 Feb 2002 12:53:42 -0500

David Feuer <> 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:

  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

  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:

-Jan-Willem Maessen