On Wednesday 29 May 2002 02:58, Hal Daume III wrote: > Is there any particular reason FiniteMap (and hence Set) aren't instances > of Ord? I realize it's "weird" to define a map to be ordered, but even if > the Ord definition were in some sense "nonsensical", being able to have, > for instance, Sets of Sets of things would be really nice.
Check this out. It was working for me last time I used it. Comments welcome, -- Eray Ozkural (exa) <[EMAIL PROTECTED]> Comp. Sci. Dept., Bilkent University, Ankara www: http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://mp3.com/ariza GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C
module Hypergraph where import FiniteMap import Set -- A hypergraph is a family of sets which are subsets of a vertex set X -- This implementation uses an edge list representation that -- directly corresponds to the mathematical definition -- n index type, w weight type -- type Hypergraph n w = Array n [(n,w)] -- show functions for set and finitemap instance (Show a) => Show (Set a) where show set = show (setToList set) instance (Show a, Show b) => Show (FiniteMap a b) where show vs = show (fmToList vs) type HEdges l = FiniteMap l (Set l) data Hypergraph l = Hypergraph (HEdges l) (HEdges l) deriving Show -- hgraph constructor -- takes a list of edges hgraph list = let edges = hEdges list in Hypergraph edges (dualEdges edges) -- hgraph edge_list --hEdges :: [ [a] ] -> HEdges a hEdges el = listToFM (zip [1..length el] (map mkSet el)) -- = Hypergraph (listToFM . mkSet (edge_list)) (listToFM . mkSet (edge_list)) -- compute dual of a given hgraph dualEdge (edgeIx, hEdge) = map (\x->(x, mkSet [edgeIx])) (setToList hEdge) dualEdges hEdges = ( (addListToFM_C union emptyFM) . concat . (map dualEdge) . fmToList ) hEdges --hVertices el = (zip (map mkSet el) [1..length el]) -- hyper vertices are the dual of the hypergraph --hVertices hEdges = (foldFM uni emptyFM). (mapFM dual)) hEdges -- where uni = plusFM_C --dual hEdges = ( listToFM . map (\(x,y)->(y,x)) . fmToList) hEdges