Hi, 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) I think it should be: tree :: Bounds -> Forest Vertex -> Graph tree bnds ts = buildG bnds (concat (map flat ts)) where flat (Node v rs) = [ (v, w) | Node w us <- rs ] ++ concat (map flat rs) The difference is that I have changed "ts" to "rs" in the body of the function "flat". 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. It is based on FiniteMap and Set, rather than arrays, because I tend to find that my graphs do not use integer indices. Of course, this means that my version is less efficient than the original and does not use LazyST, but I have never yet had any problems with its performance. Provided that Professor Launchbury agrees, would it be possible to add it to the libraries? If some work needs to be done to bring it into line with existing style guides, then I am happy to do this. Kevin (See attached file: Ldfs.hs) Kevin Backhouse, Software Engineer ARM Limited 110 Fulbourn Road, Cambridge, CB1 9NJ, UK. Tel: +44 1223 400601 This e-mail message is intended for the addressee(s) only and may contain information that is the property of, and/or subject to a confidentiality agreement between the intended recipient(s), their organisation and/or the ARM Group of Companies. If you are not an intended recipient of this e-mail message, you should not read, copy, forward or otherwise distribute or further disclose the information in it; misuse of the contents of this e-mail message may violate various laws in your state, country or jurisdiction. If you have received this e-mail message in error, please contact the originator of this e-mail message via e-mail and delete all copies of this message from your computer or network, thank you.
On Thu, 28 Aug 2003 Kevin.Backhouse@arm.com wrote:
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. It is based on FiniteMap and Set, rather than arrays, because I tend to find that my graphs do not use integer indices. Of course, this means that my version is less efficient than the original and does not use LazyST, but I have never yet had any problems with its performance. Provided that Professor Launchbury agrees, would it be possible to add it to the libraries? If some work needs to be done to bring it into line with existing style guides, then I am happy to do this.
FWIW, in case the generalised key version is rejected, it would certainly be nice if the version distributed with the hugs sources changed Vertex from being Char to being to being something bigger. (Not sure if larger values can be put into Char's via some unicode mechanism, but I've never managed to do it; consequently I've got a personal version of Ldfs.hs which differs only in that it has Vertex being Int.) ___cheers,_dave_________________________________________________________ www.cs.bris.ac.uk/~tweed/ | `It's no good going home to practise email:tweed@cs.bris.ac.uk | a Special Outdoor Song which Has To Be work tel:(0117) 954-5250 | Sung In The Snow' -- Winnie the Pooh
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
participants (3)
-
D. Tweed -
Kevin.Backhouse＠arm.com -
Ross Paterson