Ivan Lazar Miljenovic wrote:
> Henning Thielemann writes:
>
>> Recently I wrote cabal-sort using FGL
>> http://hackage.haskell.org/package/cabal-sort
>>
>> It sorts cabal packages topologically according to their
>> dependencies. However, I was neither happy with the way FGL currently
>> works, nor with the way I proposed recently (splitting into unlabelled
>> and labelled graphs). I like to use the package name as node identifier.
>> I do not need any label, but I need a node type different from Int.
>> With current FGL I need to maintain a Map PkgName Int. Would it be
>> sensible to generalize the Node type to any Ord type or does FGL use
>> optimizations specific to Int? In another example I used FGL for
>> finding all topological orderings of a set of database
>> transactions. In this case I used an enumeration type as node
>> type. Are there other applications for alternative Node types?
>
> We're considering doing this.
>
> Pros for allowing you to use a custom node type:
> * Matches your data better
> * No need for extra lookup maps when converting your data to FGL form
>
> Cons:
> * Makes type-sigs uglier/more verbose
> * Restricts the ability to optimise
>
> Using Int gives us a fixed-size data type with known good comparison
> performance and with a range that should suit most purposes.
I have the same gripe as Henning, though I'm not sure I concur with his
proposal.
Here a snippet from a quick & dirty 'make' implementation that I use for
building my website:
data Rule = Rule { ins :: [FilePath], out :: FilePath,
effect :: IO () }
rules2Graph :: [Rule] -> G.Gr (IO ()) ()
rules2Graph rules = G.mkGraph nodes' edges'
where
nodes = [(out r, conditionally (effect r) (ins r) (out r))
| r <- rules]
edges = [(i, out r, ()) | r <- rules, i <- ins r,
i `Map.member` nodeMap]
-- ignore source nodes
nodeMap = Map.fromList nodes
index k = Map.findIndex k nodeMap
nodes' = map (\(a,b) -> (index a, b)) nodes
edges' = map (\(a,b,c) -> (index a, index b, c)) edges
The nodes are file paths, labeled with a corresponding IO action to
create the file. The nodes are created from a list of rules that specify
how to create an output file from several input files.
As you can see, I had to use Data.Map to convert file paths into node
indexes. Ideally, the Data.Graph.Inductive.NodeMap module should be
used for that, but after some frustration, I found it completely
unsuitable for this task because it insists on using the graph label as
node identifier.
I am particularly unhappy about the definitions of nodes' and edges'
, the clever use of Map.findIndex to translate indexes while keeping
track of a label and the need for mapping the indexes myself.
I'm not sure what the right solution is, but I think it definitely
involves catering for different node types. For instance, the library
could operate on a type
newtype Graph node a b = Graph (Gr a b, Data.Map.Map Int node)
or it could offer a more useful NodeMap type and make the Node type
abstract. Some systematic and simple abstractions to manage nodes is
needed anyway.
Also, hard-coding Node = Int feels like the wrong kind of flexibility:
the user is able to do anything with it, just in case the library forgot
some important functionality. Which is exactly what happened in my case
when I used Map.findIndex . I prefer the library to get it right.
PS: While we're at it, I think newNodes should return an infinite list
of Node instead of requiring a fixed number to be specified in advance?
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
