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