Ldfs.hs

[Ross Paterson]

On Thu, Aug 28, 2003 at 01:18:31PM +0100, Kevin.Backhouse@arm.com wrote:
> I think there is a typo in the definition of the function "tree", in the
> module "Ldfs.hs", which is in the demos directory of the hugs distribution.
> The original definition is:
> 
> tree              :: Bounds -> Forest Vertex -> Graph
> tree bnds ts       = buildG bnds (concat (map flat ts))
>  where flat (Node v rs) = [ (v, w) | Node w us <- ts ] ++
>                           concat (map flat ts)

Yes, it was an erroneous transcription of the version in the paper,
which has "ts" instead of "rs".

> By the way, I find Ldfs very useful and I think it deserves a place amongst
> the libraries. I have attached a modified version of Ldfs that I often use.

This stuff is in the hierarchical libraries shipped with GHC 6.0 (and
the next release of Hugs) as Data.Graph (and Data.Tree).  The only
exception seems to be the "tree" function, and back, cross and
forward are defined but not exported.

> It is based on FiniteMap and Set, rather than arrays, because I tend to
> find that my graphs do not use integer indices.

In Data.Graph, Vertex = Int.  It's easy enough to enumerate node labels
and retain a mapping, but there's no need for the graph algorithms to
use this mapping.  The function graphFromEdges in Data.Graph builds
graphs this way.  The use of ST does make Data.Graph non-portable, but
I think rank-2 types really should be standard, especially as they
enable such a nifty monad.

You may wish to try out the snapshot of the Hugs sources at

	http://www.soi.city.ac.uk/~ross/hugs98-Aug2003.tar.gz

(Unix only, unfortunately)  For library documentation, see

	http://www.haskell.org/ghc/docs/latest/html/libraries.html