Graphs

[Simon Peyton-Jones]

Jan-Willem

Maybe you might consider proposing some of these
useful libraries to populate the new libraries structure for
Haskell?
http://www.haskell.org/~simonmar/libraries/libraries.html

Simon

| -----Original Message-----
| From: Jan-Willem Maessen [mailto:jmaessen@alum.mit.edu]=20
| Sent: 23 February 2002 17:54
| To: haskell-cafe@haskell.org
| Cc: David Feuer
| Subject: Re: Graphs
|=20
|=20
| David Feuer <dfeuer@cs.brown.edu> writes:
| > I seem to remember an article about functional graph=20
| algorithms using=20
| > extra-lazy arrays.  Anyone know if these arrays have=20
| appeared in any=20
| > mainstream implementation?
|=20
| I assume you're referring to this paper by Thomas Johnsson:
|=20
| @Article{lazyArray,
|   author =3D 	 {Johnsson, Thomas},
|   title =3D 	 {Efficient Graph Algorithms Using Lazy=20
| Monolithic Arrays},
|   journal =3D 	 JFP,
|   year =3D 	 1998,
|   volume =3D	 8,
|   number =3D	 4,
|   pages =3D	 {323--333},
|   month =3D	 {July}
| }
|=20
| He uses similar techniques to do whole-program flow analysis=20
| of Haskell programs, a clever bit of coding described in the following
| paper:
|=20
| @inproceedings{grinHeap,
|   AUTHOR =3D "Johnsson, Thomas",
|   TITLE =3D "Analysing Heap Contents in a Graph Reduction=20
| Intermediate Language.",
|   booktitle =3D Proc # "Glasgow Functional Programming Workshop",
|   address =3D "Ullapool 1990",
|   MONTH =3D "August",
|   YEAR =3D 1991
| }
|=20
| The LazyArray library is part of the standard hbc=20
| distribution.  The Eager Haskell compiler depends on it (you=20
| can get very nice static hash tables this way, among other=20
| things).  As a result, I've done a port of the library to GHC=20
| (and, I think, hugs).  I should note that most of the hints=20
| required to pull off the implementation were found in the=20
| "State in Haskell" paper by Simon PJ and John Launchbury. =20
| The library is available (along with a few other useful=20
| snippets, like universal splittable supplies) here:
|=20
http://www.csg.lcs.mit.edu/~earwig/haskell-lib/

-Jan-Willem Maessen _______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe