Commits

Doug Burke committed 4a76688

Switched from [a] to Set a for NSGraph/LDGraph

  • Participants
  • Parent commits 398eccc
  • Branches graph-conversion-set

Comments (0)

Files changed (30)

+0.8.0.0:
+
+  The LDGraph class now uses Set (Arc lb), rather than [Arc lb], for
+  setArcs, getArcs, and update. The NSGraph instance now uses a set
+  rather than a list internally. There are a number of API tweaks -
+  e.g. the addition of Ord constraints and the removal of Functor,
+  Foldable, and Traversable instances. Not all list of Arcs have been
+  converted since a review is needed to see where it makes sense and
+  where it does not. This definitely speeds up some operations but
+  a full analysis has not been attempted.
+
+  A few other minor changes have been made: the removal of subset from
+  Swish.Utils.ListHelpers; the ordering used for RDFLabel values has
+  changed; added a Monoid instance for VarBinding; added Ord instances
+  for a number of containers.
+
 0.7.0.2:
 
   Swish.QName.LName now requires all characters to be ASCII. This

src/Data/LookupMap.hs

 data LookupMap a = LookupMap [a]
   deriving (Functor, F.Foldable, T.Traversable)
 
+instance (Ord a) => Ord (LookupMap a) where
+    compare = compare `on` gLM
+
 {-
 
 To allow this Monoid instance, we would need UndecidableInstances.

src/Swish/Commands.hs

 import Control.Monad.State (modify, gets)
 import Control.Monad (liftM, when)
 
+import qualified Data.Set as S
 import qualified Data.Text.Lazy as T
 import qualified Data.Text.Lazy.IO as IO
 
 diffGraph :: RDFGraph -> SwishStateIO ()
 diffGraph gr = do
   oldGr <- gets graph
-  let p1 = partitionGraph (getArcs oldGr)
-      p2 = partitionGraph (getArcs gr)
+  let p1 = partitionGraph (S.toList $ getArcs oldGr)
+      p2 = partitionGraph (S.toList $ getArcs gr)
       diffs = comparePartitions p1 p2
       
   swishWriteFile (swishOutputDiffs diffs) Nothing

src/Swish/GraphClass.hs

     , Selector
     , arc, arcToTriple, arcFromTriple
     , hasLabel, arcLabels -- , arcNodes
+    , getComponents
     )
 where
 
 import Data.Hashable (Hashable(..))
-import Data.List (foldl', union, (\\))
+import Data.List (foldl')
 
 import qualified Data.Foldable as F
 import qualified Data.Set as S
 Minimum required implementation: 
 'emptyGraph', 'setArcs', and 'getArcs'.
 -}
--- We do not need the Eq (lg lb) constraint to compile this module,
--- but if we take it out then need to add if to the Expression (lg lb)
--- instance in Swish.RDF.Proof.
---
--- class (Eq (lg lb), Eq lb ) => LDGraph lg lb where
-class (Eq lb) => LDGraph lg lb where
+
+class LDGraph lg lb where
 
     -- | Create the empty graph.
     emptyGraph  :: lg lb
       
     -- | Replace the existing arcs in the graph.
-    -- setArcs     :: lg lb -> S.Set (Arc lb) -> lg lb
-    setArcs     :: lg lb -> [Arc lb] -> lg lb
+    setArcs     :: lg lb -> S.Set (Arc lb) -> lg lb
     
     -- | Extract all the arcs from a graph
-    -- getArcs     :: lg lb -> S.Set (Arc lb)
-    getArcs     :: lg lb -> [Arc lb]
+    getArcs     :: lg lb -> S.Set (Arc lb)
     
     -- | Extract those arcs that match the given `Selector`.
-    extract     :: Selector lb -> lg lb -> lg lb
-    extract sel = update (filter sel)
+    extract     :: (Ord lb) => Selector lb -> lg lb -> lg lb
+    extract sel = update (S.filter sel)
     
     -- | Add the two graphs
-    addGraphs         :: lg lb -> lg lb -> lg lb
-    addGraphs    addg = update (union (getArcs addg))
+    addGraphs         :: (Ord lb) => lg lb -> lg lb -> lg lb
+    addGraphs    addg = update (S.union (getArcs addg))
     
     -- | Remove those arcs in the first graph from the second
     -- graph
-    delete :: lg lb  -- ^ g1
-              -> lg lb -- ^ g2
-              -> lg lb -- ^ g2 - g1 -> g3
-    delete delg = update (\\ getArcs delg)
+    delete :: 
+        (Ord lb) =>
+        lg lb    -- ^ g1
+        -> lg lb -- ^ g2
+        -> lg lb -- ^ g2 - g1 -> g3
+    delete g1 g2 = setArcs g2 (getArcs g2 `S.difference` getArcs g1)
     
     -- | Enumerate the distinct labels contained in a graph;
     -- that is, any label that appears in the subject,
     -- predicate or object position of an `Arc`.
-    labels      :: lg lb -> [lb]
-    labels g    = foldl' union [] (map arcLabels (getArcs g))
+    labels      :: (Ord lb) => lg lb -> S.Set lb
+    labels = getComponents arcLabels . getArcs
     
     -- | Enumerate the distinct nodes contained in a graph;
     -- that is, any label that appears in the subject
     -- or object position of an `Arc`.
-    nodes       :: lg lb -> [lb]
-    nodes g     = foldl' union [] (map arcNodes (getArcs g))
+    nodes       :: (Ord lb) => lg lb -> S.Set lb
+    nodes = getComponents arcNodes . getArcs
     
     -- | Update the arcs in a graph using a supplied function.
-    update      :: ([Arc lb] -> [Arc lb]) -> lg lb -> lg lb
+    update      :: (S.Set (Arc lb) -> S.Set (Arc lb)) -> lg lb -> lg lb
     update f g  = setArcs g ( f (getArcs g) )
 
+-- | Extract components from a set.
+getComponents :: (Ord a, Ord b) => (a -> [b]) -> S.Set a -> S.Set b
+getComponents f = 
+    let ins sgr = foldl' (flip S.insert) sgr . f
+    in S.foldl' ins S.empty 
+
 -- | Label class
 --
 --  A label may have a fixed binding, which means that the label identifies (is) a
   -- | Make a label value from a local id.  
   makeLabel   :: String -> lb
     
-  -- compare     :: lb -> lb -> Ordering
-  -- compare l1 l2 = compare (show l1) (show l2)
-
 -- | Arc type.
 --
 -- Prior to @0.7.0.0@ you could also use @asubj@, @apred@ and @aobj@

src/Swish/GraphMatch.hs

       ) where
 
 import Swish.GraphClass (Arc(..), Label(..))
-import Swish.GraphClass (arcLabels, hasLabel, arcToTriple)
+import Swish.GraphClass (getComponents, arcLabels, hasLabel, arcToTriple)
 
 import Swish.Utils.ListHelpers (equiv)
 
 import Control.Arrow (second)
 
 import Data.Ord (comparing)
-import Data.List (foldl', nub, sortBy, groupBy, partition)
+import Data.List (foldl', sortBy, groupBy, partition)
 import Data.LookupMap (LookupEntryClass(..), LookupMap(..))
 import Data.LookupMap (makeLookupMap, listLookupMap, mapFind, mapReplaceAll,
                        mapAddIfNew, mapReplaceMap, mapMerge)
 import Data.Word
 
 import qualified Data.List as L
+import qualified Data.Set as S
 
 --------------------------
 --  Label index value type
 
 -- QUS: why doesn't this return Maybe (LabelMap (ScopedLabel lb)) ?
 
+-- TODO: Should this use Set (Arc lb) instead of [Arc lb]?
+
 -- | Graph matching function accepting two lists of arcs and
 --  returning a node map if successful
 --
                   newGenerationMap $
                   assignLabelMap ls1 $
                   assignLabelMap ls2 emptyMap
-        ec1     = {- traceShow "ec1 " $ -} equivalenceClasses lmap ls1
-        ec2     = {- traceShow "ec2 " $ -} equivalenceClasses lmap ls2
+        ec1     = {- traceShow "ec1 " $ -} equivalenceClasses lmap $ S.toList ls1 -- TODO: use sets rather than lists
+        ec2     = {- traceShow "ec2 " $ -} equivalenceClasses lmap $ S.toList ls2
         ecpairs = zip (pairSort ec1) (pairSort ec2)
         matchableScoped (ScopedLabel _ l1) (ScopedLabel _ l2) = matchable l1 l2
         match   = graphMatch1 False matchableScoped sgs1 sgs2 lmap ecpairs
 --  All variable node labels are assigned the same initial
 --  value, as they may be matched with each other.
 --
-assignLabelMap :: (Label lb) => [lb] -> LabelMap lb -> LabelMap lb
-assignLabelMap ns lmap = foldl' (flip assignLabelMap1) lmap ns
+assignLabelMap :: (Label lb) => S.Set lb -> LabelMap lb -> LabelMap lb
+assignLabelMap ns lmap = S.foldl' (flip assignLabelMap1) lmap ns
 
 assignLabelMap1 :: (Label lb) => lb -> LabelMap lb -> LabelMap lb
 assignLabelMap1 lab (LabelMap g lvs) = LabelMap g lvs'
     | otherwise = select f l1 l2
 select _ _ _    = error "select supplied with different length lists"
 
+-- | Return the set of distinct labels used in the graph.
 
--- | Return list of distinct labels used in a graph
-
-graphLabels :: (Label lb) => [Arc lb] -> [lb]
-graphLabels = nub . concatMap arcLabels
+graphLabels :: (Label lb) => [Arc lb] -> S.Set lb
+graphLabels = getComponents arcLabels . S.fromList
 
 -- TODO: worry about overflow?
 

src/Swish/GraphMem.hs

-{-# LANGUAGE DeriveFoldable #-}
-{-# LANGUAGE DeriveFunctor #-}
-{-# LANGUAGE DeriveTraversable #-}
 {-# LANGUAGE FlexibleInstances #-}
 {-# LANGUAGE MultiParamTypeClasses #-}
 
 --
 --  Maintainer  :  Douglas Burke
 --  Stability   :  experimental
---  Portability :  DeriveFoldable, DeriveFunctor, DeriveTraversable, FlexibleInstances, MultiParamTypeClasses
+--  Portability :  FlexibleInstances, MultiParamTypeClasses
 --
 --  This module defines a simple memory-based graph instance.
 --
 import Data.Monoid (Monoid(..))
 import Data.Ord (comparing)
 
-import qualified Data.Foldable as F
-import qualified Data.Traversable as T
+import qualified Data.Set as S
 
 -- | Simple memory-based graph type. 
 
-data GraphMem lb = GraphMem { arcs :: [Arc lb] }
-                   deriving (Functor, F.Foldable, T.Traversable)
-                            
+data GraphMem lb = GraphMem { arcs :: S.Set (Arc lb) }
+
 instance (Label lb) => LDGraph GraphMem lb where
-    emptyGraph   = GraphMem []
+    emptyGraph   = GraphMem S.empty
     getArcs      = arcs
     setArcs g as = g { arcs=as }
 
     mappend = addGraphs
 
 graphShow   :: (Label lb) => GraphMem lb -> String
-graphShow g = "Graph:" ++ foldr ((++) . ("\n    " ++) . show) "" (arcs g)
+graphShow g = "Graph:" ++ S.foldr ((++) . ("\n    " ++) . show) "" (arcs g)
 
 {-
 toGraph :: (Label lb) => [Arc lb] -> GraphMem lb
   --
 matchGraphMem g1 g2 =
     let
-        gs1     = arcs g1
-        gs2     = arcs g2
+        gs1     = S.toList $ arcs g1
+        gs2     = S.toList $ arcs g2
         matchable l1 l2
             | labelIsVar l1 && labelIsVar l2 = True
             | labelIsVar l1 || labelIsVar l2 = False

src/Swish/Namespace.hs

 --
 
 data Namespace = Namespace (Maybe T.Text) URI
+
 -- data Namespace = Namespace (Maybe T.Text) !URI
 -- TODO: look at interning the URI
                  
 instance Eq Namespace where
   (Namespace _ u1) == (Namespace _ u2) = u1 == u2
 
+instance Ord Namespace where
+    -- using show for the URI is wasteful
+    (Namespace a1 b1) `compare` (Namespace a2 b2) =
+        (a1, show b1) `compare` (a2, show b2)
+
 instance Show Namespace where
     show (Namespace (Just p) u) = show p ++ ":<" ++ show u ++ ">"
     show (Namespace _ u)        = "<" ++ show u ++ ">"

src/Swish/Proof.hs

 import Swish.Rule (showsFormula, showsFormulae)
 import Swish.Ruleset (Ruleset(..))
 
-import Swish.Utils.ListHelpers (subset)
-
 import Data.List (union, intersect, intercalate, foldl')
 import Data.Maybe (catMaybes, isNothing)
 import Data.String.ShowLines (ShowLines(..))
 
+import qualified Data.Set as S
+
 ------------------------------------------------------------
 --  Proof framework
 ------------------------------------------------------------
 
 -- |Check consistency of given proof.
 --  The supplied rules and axioms are assumed to be correct.
-checkProof :: (Expression ex) => Proof ex -> Bool
+checkProof :: 
+    (Expression ex, Ord ex) 
+    => Proof ex -> Bool
 checkProof pr =
     checkProof1 (proofRules pr) initExpr (proofChain pr) goalExpr
     where
         initExpr = formExpr (proofInput pr) : map formExpr (proofAxioms pr)
         goalExpr = formExpr $ proofResult pr
 
-checkProof1 :: (Expression ex) => [Rule ex] -> [ex] -> [Step ex] -> ex -> Bool
+checkProof1 :: 
+    (Expression ex, Ord ex) 
+    => [Rule ex] -> [ex] -> [Step ex] -> ex -> Bool
 checkProof1 _     prev []       res = res `elem` prev
 checkProof1 rules prev (st:steps) res =
     checkStep rules prev st &&
 --  being in correspondence with the name of one of the indicated
 --  valid rules of inference.
 checkStep :: 
-  (Expression ex) 
+  (Expression ex, Ord ex) 
   => [Rule ex]   -- ^ rules
   -> [ex]        -- ^ antecedants
   -> Step ex     -- ^ the step to validate
 -- |Check proof. If there is an error then return information
 -- about the failing step.
 explainProof ::
-    (Expression ex) => Proof ex -> Maybe String
+    (Expression ex, Ord ex) => Proof ex -> Maybe String
 explainProof pr =
     explainProof1 (proofRules pr) initExpr (proofChain pr) goalExpr
     where
         goalExpr = formExpr $ proofResult pr
 
 explainProof1 ::
-    (Expression ex) => [Rule ex] -> [ex] -> [Step ex] -> ex -> Maybe String
+    (Expression ex, Ord ex) 
+    => [Rule ex] -> [ex] -> [Step ex] -> ex -> Maybe String
 explainProof1 _     prev []       res   =
     if res `elem` prev then Nothing else Just "Result not demonstrated"
 explainProof1 rules prev (st:steps) res =
 --  valid rules of inference.
 --
 explainStep :: 
-  (Expression ex) 
+  (Expression ex, Ord ex) 
   => [Rule ex]  -- ^ rules
   -> [ex]       -- ^ previous
   -> Step ex    -- ^ step
             [ require (ruleName srul `elem` map ruleName rules)
                       ("rule "++show (ruleName srul)++" not present")
             -- Antecedent expressions are all previously accepted expressions
-            , require (sant `subset` prev)
+            , require (S.fromList sant `S.isSubsetOf` S.fromList prev) -- (sant `subset` prev)
                       "antecedent not axiom or previous result"
             -- Inference rule yields consequence from antecedents
             , require (checkInference srul sant scon)

src/Swish/RDF/ClassRestrictionRule.hs

 
 import Control.Monad (liftM)
 
-import Data.List (delete, nub, (\\), subsequences)
+import Data.List (delete, nub, subsequences)
 import Data.LookupMap (LookupEntryClass(..), LookupMap(..),mapFindMaybe)
 import Data.Maybe (fromJust, fromMaybe, mapMaybe)
 import Data.Monoid (Monoid (..))
 import Data.Ord.Partial (minima, maxima, partCompareEq, partComparePair, partCompareListMaybe, partCompareListSubset)
 
+import qualified Data.Set as S
 import qualified Data.Text.Lazy.Builder as B
 
 ------------------------------------------------------------
         nts :: [[RDFLabel]]
         nts = mapMaybe sequence sts
         --  Make new graph from results, including only newly generated arcs
-        newarcs = nub [Arc ci p v | vs <- nts, (p,v) <- zip props vs ]
-                  \\ getArcs antgr
-        newgrs  = if null newarcs then [] else [toRDFGraph newarcs]
+        newarcs = S.fromList [Arc ci p v | vs <- nts, (p,v) <- zip props vs ]
+                  `S.difference` getArcs antgr
+        newgrs  = if S.null newarcs then [] else [toRDFGraph newarcs]
 
 --  Backward apply class restriction.
 --
         --  Make new graphs for all alternatives
         grss :: [[RDFGraph]]
         grss = map ( makeGraphs . newArcs ) ftss
+
         --  Collect arcs for one alternative
         newArcs dts =
             [ Arc ci p v | mvs <- dts, (p,Just v) <- zip props mvs ]
+
         --  Make graphs for one alternative
-        makeGraphs = map (toRDFGraph . (:[])) . (Arc ci resRdfType cls :)
+        --  TODO: convert to sets
+        makeGraphs = map (toRDFGraph . S.fromList . (:[])) . (Arc ci resRdfType cls :)
 
 --  Helper function to select sub-tuples from which some of a set of
 --  values can be derived using a class restriction.

src/Swish/RDF/Formatter/N3.hs

 import Control.Monad.State (State, modify, get, put, runState)
 
 import Data.Char (isDigit)
-import Data.List (foldl', delete, groupBy, partition, sort, intersperse)
+import Data.List (foldl', delete, groupBy, partition, intersperse)
 import Data.LookupMap (LookupEntryClass(..), LookupMap)
 import Data.LookupMap (emptyLookupMap, reverseLookupMap, listLookupMap
                       , mapFind, mapFindMaybe, mapAdd, mapDelete, mapMerge)
 import Data.Monoid (Monoid(..))
 import Data.Word (Word32)
 
+import qualified Data.Set as S
+
 -- it strikes me that using Lazy Text here is likely to be
 -- wrong; however I have done no profiling to back this
 -- assumption up!
 
 newtype SortedArcs lb = SA [Arc lb]
 
-sortArcs :: (Ord lb) => [Arc lb] -> SortedArcs lb
-sortArcs = SA . sort
+sortArcs :: (Ord lb) => S.Set (Arc lb) -> SortedArcs lb
+sortArcs = SA . S.toAscList
 
 --  Rearrange a list of arcs into a tree of pairs which group together
 --  all statements for a single subject, and similarly for multiple
 
 
 findMaxBnode :: RDFGraph -> Word32
-findMaxBnode = maximum . map getAutoBnodeIndex . labels
+findMaxBnode = S.findMax . S.map getAutoBnodeIndex . labels
 
 getAutoBnodeIndex   :: RDFLabel -> Word32
 getAutoBnodeIndex (Blank ('_':lns)) = res where

src/Swish/RDF/Formatter/NTriples.hs

 import Data.LookupMap (LookupMap, emptyLookupMap, mapFind, mapAdd)
 import Data.Monoid
 
+import qualified Data.Set as S
+
 -- it strikes me that using Lazy Text here is likely to be
 -- wrong; however I have done no profiling to back this
 -- assumption up!
 ----------------------------------------------------------------------
 
 formatGraph :: RDFGraph -> Formatter B.Builder
-formatGraph gr = mconcat <$> mapM formatArc (getArcs gr)
+formatGraph gr = mconcat <$> mapM formatArc (S.toList (getArcs gr))
 
 -- TODO: this reverses the contents but may be faster?
 --       that is if I've got the order right in the mappend call

src/Swish/RDF/Formatter/Turtle.hs

 import Control.Monad.State (State, modify, get, put, runState)
 
 import Data.Char (isDigit)
-import Data.List (foldl', delete, groupBy, partition, sort, intersperse)
+import Data.List (foldl', delete, groupBy, partition, intersperse)
 import Data.LookupMap (LookupEntryClass(..), LookupMap)
 import Data.LookupMap (emptyLookupMap, reverseLookupMap, listLookupMap, mapFind, mapFindMaybe, mapAdd, mapMerge)
 import Data.Monoid (Monoid(..))
 import Data.Word (Word32)
 
+import qualified Data.Set as S
+
 -- it strikes me that using Lazy Text here is likely to be
 -- wrong; however I have done no profiling to back this
 -- assumption up!
 
 newtype SortedArcs lb = SA [Arc lb]
 
-sortArcs :: (Ord lb) => [Arc lb] -> SortedArcs lb
-sortArcs = SA . sort
+sortArcs :: S.Set (Arc lb) -> SortedArcs lb
+sortArcs = SA . S.toAscList
 
 --  Rearrange a list of arcs into a tree of pairs which group together
 --  all statements for a single subject, and similarly for multiple
         fstEq (f1,_) (f2,_) = f1 == f2
 
 findMaxBnode :: RDFGraph -> Word32
-findMaxBnode = maximum . map getAutoBnodeIndex . labels
+findMaxBnode = S.findMax . S.map getAutoBnodeIndex . labels
 
 getAutoBnodeIndex   :: RDFLabel -> Word32
 getAutoBnodeIndex (Blank ('_':lns)) = res where

src/Swish/RDF/Graph.hs

     , newNode, newNodes
     , setNamespaces, getNamespaces
     , setFormulae, getFormulae, setFormula, getFormula
+    , fmapNSGraph
+    , traverseNSGraph
       
     -- * Re-export from GraphClass
     --
     , nullScopedName
     )
 
-import Swish.RDF.Vocabulary
-{-    
-    ( namespaceRDF
-    , langTag, isLang
-    , rdfType
-    , rdfFirst, rdfRest, rdfNil, rdfXMLLiteral
-    , rdfsMember
-    , rdfdGeneralRestriction
-    , rdfdOnProperties, rdfdConstraint, rdfdMaxCardinality
-    , owlSameAs, logImplies
-    , xsdBoolean, xsdDecimal, xsdFloat, xsdDouble, xsdInteger
-    , xsdDateTime, xsdDate                                                
-    )
--}
+import Swish.RDF.Vocabulary (LanguageTag)
+import Swish.RDF.Vocabulary (fromLangTag, xsdBoolean, xsdDate, xsdDateTime, xsdDecimal, xsdDouble, xsdFloat, xsdInteger
+                            , rdfType, rdfList, rdfFirst, rdfRest, rdfNil
+                            , rdfsMember, rdfdGeneralRestriction, rdfdOnProperties, rdfdConstraint, rdfdMaxCardinality
+                            , rdfsSeeAlso, rdfValue, rdfsLabel, rdfsComment, rdfProperty
+                            , rdfsSubPropertyOf, rdfsSubClassOf, rdfsClass, rdfsLiteral
+                            , rdfsDatatype, rdfXMLLiteral, rdfsRange, rdfsDomain, rdfsContainer
+                            , rdfBag, rdfSeq, rdfAlt
+                            , rdfsContainerMembershipProperty, rdfsIsDefinedBy
+                            , rdfsResource, rdfStatement, rdfSubject, rdfPredicate, rdfObject
+                            , rdfRDF, rdfDescription, rdfID, rdfAbout, rdfParseType
+                            , rdfResource, rdfLi, rdfNodeID, rdfDatatype, rdfXMLLiteral
+                            , rdf1, rdf2, rdfn
+                            , owlSameAs, logImplies, namespaceRDF
+                            )
 
 import Swish.GraphClass (LDGraph(..), Label (..), Arc(..), Selector)
-import Swish.GraphClass (arc, arcLabels)
+import Swish.GraphClass (arc, arcLabels, getComponents)
 import Swish.GraphMatch (LabelMap, ScopedLabel(..))
 import Swish.GraphMatch (graphMatch)
 import Swish.QName (QName, getLName)
 
-import Control.Applicative (Applicative, liftA, (<$>), (<*>))
+import Control.Applicative (Applicative(pure), (<$>), (<*>))
 
 import Network.URI (URI)
 
 import Data.List (intersect, union, foldl')
 import Data.LookupMap (LookupMap(..), LookupEntryClass(..))
 import Data.LookupMap (listLookupMap, mapFind, mapFindMaybe, mapReplace, mapAddIfNew, mapVals, mapKeys )
-import Data.Ord (comparing)
+-- import Data.Ord (comparing)
 import Data.Word (Word32)
 
 import Data.String (IsString(..))
 
 import Text.Printf
 
-import qualified Data.Foldable as Foldable
-import qualified Data.Traversable as Traversable
+import qualified Data.Set as S
 
 import qualified Data.Text as T
 import qualified Data.Text.Read as T
--- import qualified Data.Text.Lazy as L
--- import Data.Text.Format (format)
--- import Data.Text.Buildable
--- import Data.Text.Format.Types (Only(..))
+import qualified Data.Traversable as Traversable
 
 #if defined(__GLASGOW_HASKELL__) && (__GLASGOW_HASKELL__ >= 701)
 import Data.Tuple (swap)
     show NoNode             = "<NoNode>"
 
 instance Ord RDFLabel where
-    -- Optimize some common cases..
-    compare (Res sn1)      (Res sn2)      = compare sn1 sn2
-    compare (Blank ln1)    (Blank ln2)    = compare ln1 ln2
-    compare (Res _)        (Blank _)      = LT
-    compare (Blank _)      (Res _)        = GT
+    -- Order, from lowest to highest is
+    --    Res, Lit, LangLit, TypedLit, Blank, Var, NoNode
+    --
+    compare (Res sn1)        (Res sn2)        = compare sn1 sn2
+    compare (Res _)          _                = LT
+    compare _                (Res _)          = GT
 
-    compare (Lit s1)       (Lit s2)       = compare s1 s2
+    compare (Lit s1)         (Lit s2)         = compare s1 s2
+    compare (Lit _)          _                = LT
+    compare _                (Lit _)          = GT
 
-    -- .. else use show string comparison
-    compare l1 l2 = comparing show l1 l2
-    
-    {- <= is not used if compare is provided
-    -- Similarly for <=
-    (Res qn1)   <= (Res qn2)      = qn1 <= qn2
-    (Blank ln1) <= (Blank ln2)    = ln1 <= ln2
-    (Res _)     <= (Blank _)      = True
-    (Blank _)   <= (Res _)        = False
-    l1 <= l2                      = show l1 <= show l2
-    -}
-    
+    compare (LangLit s1 l1)  (LangLit s2 l2)  = compare (s1,l1) (s2,l2)
+    compare (LangLit _ _)    _                = LT
+    compare _                (LangLit _ _)    = GT
+
+    compare (TypedLit s1 t1) (TypedLit s2 t2) = compare (s1,t1) (s2,t2)
+    compare (TypedLit _ _)   _                = LT
+    compare _                (TypedLit _ _)   = GT
+
+    compare (Blank ln1)      (Blank ln2)      = compare ln1 ln2
+    compare (Blank _)        _                = LT
+    compare _                (Blank _)        = GT
+
+    compare (Var ln1)        (Var ln2)        = compare ln1 ln2
+    compare (Var _)          NoNode           = LT
+    compare _                (Var _)          = GT
+
+    compare NoNode           NoNode           = EQ
+
 instance Label RDFLabel where
     labelIsVar (Blank _)    = True
     labelIsVar (Var _)      = True
     f1 == f2 = formLabel f1 == formLabel f2 &&
                formGraph f1 == formGraph f2
 
+instance (Ord lb, Ord gr) => Ord (LookupFormula lb gr) where
+    (Formula a1 b1) `compare` (Formula a2 b2) =
+        (a1,b1) `compare` (a2,b2)
+
 instance (Label lb)
     => LookupEntryClass (LookupFormula lb (NSGraph lb)) lb (NSGraph lb)
     where
 emptyFormulaMap :: FormulaMap RDFLabel
 emptyFormulaMap = LookupMap []
 
-{-  given up on trying to do Functor for formulae...
-instance Functor (LookupFormula (NSGraph lb)) where
-    fmap f fm = mapTranslateEntries (mapFormulaEntry f) fm
--}
+fmapFormulaMap :: (Ord a, Ord b) => (a -> b) -> FormulaMap a -> FormulaMap b
+fmapFormulaMap f = fmap (fmapFormula f)
 
-formulaeMap :: (lb -> l2) -> FormulaMap lb -> FormulaMap l2
-formulaeMap f = fmap (formulaEntryMap f) 
+fmapFormula :: (Ord a, Ord b) => (a -> b) -> Formula a -> Formula b
+fmapFormula f (Formula k gr) = Formula (f k) (fmapNSGraph f gr)
 
-formulaEntryMap ::
-    (lb -> l2)
-    -> Formula lb
-    -> Formula l2
-formulaEntryMap f (Formula k gr) = Formula (f k) (fmap f gr)
+traverseFormulaMap :: 
+    (Applicative f, Ord a, Ord b) 
+    => (a -> f b) -> FormulaMap a -> f (FormulaMap b)
+traverseFormulaMap f = Traversable.traverse (traverseFormula f)
 
-formulaeMapA :: Applicative f => (lb -> f l2) -> 
-                FormulaMap lb -> f (FormulaMap l2)
-formulaeMapA f = Traversable.traverse (formulaEntryMapA f)
-
-formulaEntryMapA ::
-  (Applicative f) => 
-  (lb -> f l2)
-  -> Formula lb
-  -> f (Formula l2)
-formulaEntryMapA f (Formula k gr) = Formula `liftA` f k <*> Traversable.traverse f gr
+traverseFormula :: 
+    (Applicative f, Ord a, Ord b)
+    => (a -> f b) -> Formula a -> f (Formula b)
+traverseFormula f (Formula k gr) = Formula <$> f k <*> traverseNSGraph f gr
 
 {-
 formulaeMapM ::
 
 -}
 data NSGraph lb = NSGraph
-    { namespaces :: NamespaceMap    -- ^ the namespaces to use
-    , formulae   :: FormulaMap lb   -- ^ any associated formulae (a.k.a. sub- or named- graps)
-    , statements :: [Arc lb]        -- ^ the statements in the graph
+    { namespaces :: NamespaceMap      -- ^ the namespaces to use
+    , formulae   :: FormulaMap lb     -- ^ any associated formulae (a.k.a. sub- or named- graps)
+    , statements :: S.Set (Arc lb)    -- ^ the statements in the graph
     }
 
 instance (Label lb) => LDGraph NSGraph lb where
-    emptyGraph   = NSGraph emptyNamespaceMap (LookupMap []) []
+    emptyGraph   = NSGraph emptyNamespaceMap (LookupMap []) S.empty
     getArcs      = statements 
     setArcs g as = g { statements=as }
 
     mempty  = emptyGraph
     mappend = merge
   
-instance Functor NSGraph where
-  fmap f (NSGraph ns fml stmts) =
-    NSGraph ns (formulaeMap f fml) ((map $ fmap f) stmts)
+fmapNSGraph :: (Ord lb1, Ord lb2) => (lb1 -> lb2) -> NSGraph lb1 -> NSGraph lb2
+fmapNSGraph f (NSGraph ns fml stmts) = 
+    NSGraph ns (fmapFormulaMap f fml) ((S.map $ fmap f) stmts)
 
-instance Foldable.Foldable NSGraph where
-  foldMap = Traversable.foldMapDefault
+traverseNSGraph :: 
+    (Applicative f, Ord a, Ord b) 
+    => (a -> f b) -> NSGraph a -> f (NSGraph b)
+traverseNSGraph f (NSGraph ns fml stmts) = 
+    NSGraph ns <$> traverseFormulaMap f fml <*> (traverseSet $ Traversable.traverse f) stmts
 
-instance Traversable.Traversable NSGraph where
-  traverse f (NSGraph ns fml stmts) = 
-    NSGraph ns <$> formulaeMapA f fml <*> (Traversable.traverse $ Traversable.traverse f) stmts
-  
+traverseSet ::
+    (Applicative f, Ord a, Ord b)
+    => (a -> f b) -> S.Set a -> f (S.Set b)
+traverseSet f = S.foldr cons (pure S.empty)
+    where
+      cons x s = S.insert <$> f x <*> s
+
 instance (Label lb) => Eq (NSGraph lb) where
     (==) = grEq
 
+instance (Label lb) => Ord (NSGraph lb) where
+    (NSGraph ns1 fml1 stmts1) `compare` (NSGraph ns2 fml2 stmts2) =
+        (ns1,fml1,stmts1) `compare` (ns2,fml2,stmts2)
+
 instance (Label lb) => Show (NSGraph lb) where
     show     = grShow ""
     showList = grShowList ""
 but it does ensure that the arc is unknown before adding it.
 -}
 addArc :: (Label lb) => Arc lb -> NSGraph lb -> NSGraph lb
-addArc ar gr = gr { statements=addSetElem ar (statements gr) }
-
--- |Add element to the set.
-
-addSetElem :: (Eq a) => a -> [a] -> [a]
-addSetElem e es = if e `elem` es then es else e:es
+addArc ar = update (S.insert ar)
 
 grShowList :: (Label lb) => String -> [NSGraph lb] -> String -> String
 grShowList _ []     = showString "[no graphs]"
         pp = "\n    " ++ p
 
 showArcs :: (Label lb) => String -> NSGraph lb -> String
-showArcs p g = foldr ((++) . (pp ++) . show) "" (getArcs g)
+showArcs p g = S.foldr ((++) . (pp ++) . show) "" (getArcs g)
     where
         pp = "\n    " ++ p
 
 grMatchMap :: (Label lb) =>
     NSGraph lb -> NSGraph lb -> (Bool, LabelMap (ScopedLabel lb))
 grMatchMap g1 g2 =
-    graphMatch matchable (getArcs g1) (getArcs g2)
+    graphMatch matchable (ga g1) (ga g2)
     where
+        ga = S.toList . getArcs
         matchable l1 l2 = mapFormula g1 l1 == mapFormula g2 l2
         mapFormula g l  = mapFindMaybe l (getFormulae g)
 
 --        
 merge :: (Label lb) => NSGraph lb -> NSGraph lb -> NSGraph lb
 merge gr1 gr2 =
-    let bn1   = allLabels labelIsVar gr1
-        bn2   = allLabels labelIsVar gr2
+    let bn1   = S.toList $ allLabels labelIsVar gr1
+        bn2   = S.toList $ allLabels labelIsVar gr2
         dupbn = intersect bn1 bn2
         allbn = union bn1 bn2
     in addGraphs gr1 (remapLabels dupbn allbn id gr2)
 -- |Return list of all labels (including properties) in the graph
 --  satisfying a supplied filter predicate. This routine
 --  includes the labels in any formulae.
-allLabels :: (Label lb) => (lb -> Bool) -> NSGraph lb -> [lb]
-allLabels p gr = filter p (unionNodes p (formulaNodes p gr) (labels gr) ) 
+allLabels :: (Label lb) => (lb -> Bool) -> NSGraph lb -> S.Set lb
+allLabels p gr = S.filter p (unionNodes p (formulaNodes p gr) (labels gr) ) 
                  
 {- TODO: is the leading 'filter p' needed in allLabels?
 -}
 
 -- |Return list of all subjects and objects in the graph
 --  satisfying a supplied filter predicate.
-allNodes :: (Label lb) => (lb -> Bool) -> NSGraph lb -> [lb]
-allNodes p = unionNodes p [] . nodes
+allNodes :: (Label lb) => (lb -> Bool) -> NSGraph lb -> S.Set lb
+allNodes p = unionNodes p S.empty . nodes
 
 -- | List all nodes in graph formulae satisfying a supplied predicate
-formulaNodes :: (Label lb) => (lb -> Bool) -> NSGraph lb -> [lb]
+formulaNodes :: (Label lb) => (lb -> Bool) -> NSGraph lb -> S.Set lb
 formulaNodes p gr = foldl' (unionNodes p) fkeys (map (allLabels p) fvals)
     where
         -- fm :: (Label lb) => FormulaMap lb
         -- fvals :: (Label lb) => [NSGraph lb]
         fvals = mapVals fm
         -- fkeys :: (Label lb) => [lb]
-        fkeys = filter p $ mapKeys fm
+        fkeys = S.filter p $ S.fromList $ mapKeys fm
 
 -- | Helper to filter variable nodes and merge with those found so far
-unionNodes :: (Label lb) => (lb -> Bool) -> [lb] -> [lb] -> [lb]
-unionNodes p ls1 ls2 = ls1 `union` filter p ls2
+unionNodes :: (Label lb) => (lb -> Bool) -> S.Set lb -> S.Set lb -> S.Set lb
+unionNodes p ls1 ls2 = ls1 `S.union` S.filter p ls2
+
+-- TODO: use S.Set lb rather than [lb] in the following
 
 -- |Remap selected nodes in graph.
 --
     -- RDF query nodes into RDF blank nodes.
     -> NSGraph lb -- ^ graph in which nodes are to be renamed
     -> NSGraph lb
-remapLabels dupbn allbn cnvbn = fmap (mapnode dupbn allbn cnvbn)
+
+remapLabels dupbn allbn cnvbn =
+    fmapNSGraph (mapnode dupbn allbn cnvbn)
 
 -- |Externally callable function to construct a list of (old,new)
 --  values to be used for graph label remapping.
 
 type RDFGraph = NSGraph RDFLabel
 
--- |Create a new RDF graph from a supplied list of arcs.
+-- |Create a new RDF graph from a supplied set of arcs.
 --
 -- This version will attempt to fill up the namespace map
 -- of the graph based on the input labels (including datatypes
 -- and earlier.
 --
 toRDFGraph :: 
-    [RDFTriple] -- ^ There is no check to remove repeated statements in this list,
-                -- so it is suggested that you use 'Data.List.nub', or convert via 'Data.Set.Set',
-                -- if your input may contain such elements.
+    S.Set RDFTriple
     -> RDFGraph
 toRDFGraph arcs = 
-  let lbls = concatMap arcLabels arcs
+  let lbls = getComponents arcLabels arcs
       
       getNS (Res s) = Just s
       getNS (TypedLit _ dt) = Just dt
       getNS _ = Nothing
 
-      ns = mapMaybe (fmap getScopeNamespace . getNS) lbls
+      ns = mapMaybe (fmap getScopeNamespace . getNS) $ S.toList lbls
       nsmap = foldl' mapAddIfNew emptyNamespaceMap ns
   
   in mempty { namespaces = nsmap, statements = arcs }

src/Swish/RDF/Proof.hs

 import Swish.Rule (Expression(..), Rule(..))
 import Swish.VarBinding (makeVarBinding)
 
-import Swish.RDF.Graph (RDFLabel(..), RDFGraph)
+import Swish.RDF.Graph (RDFLabel(..), RDFGraph, fmapNSGraph)
 import Swish.RDF.Graph (merge, allLabels, remapLabelList)
 import Swish.RDF.Query (rdfQueryInstance, rdfQuerySubs)
 import Swish.RDF.Ruleset (RDFFormula, RDFRule, RDFRuleset)
 
-import Swish.Utils.ListHelpers (subset, flist)
+import Swish.Utils.ListHelpers (flist)
 
 import Data.List (subsequences)
 import Data.LookupMap (makeLookupMap, mapFind)
 import Data.Monoid (Monoid(..))
 
+import qualified Data.Set as S
+
 ------------------------------------------------------------
 --  Type instantiation of Proof framework for RDFGraph data
 ------------------------------------------------------------
 --  @Expression@ class, for which proofs can be constructed.
 --  The empty RDF graph is always @True@ (other enduring
 --  truths are asserted as axioms).
--- instance (Label lb, LDGraph lg lb) => Expression (lg lb) where
+
 instance (Label lb, LDGraph lg lb, Eq (lg lb)) => Expression (lg lb) where
-    isValid = null . getArcs 
+    isValid = S.null . getArcs 
 
 ------------------------------------------------------------
 --  Define RDF-specific types for proof framework
         --  Obtain lists of variable and non-variable nodes
         --  (was: nonvarNodes = allLabels (not . labelIsVar) mergeGraph)
         nonvarNodes = vocab
-        varNodes    = allLabels labelIsVar mergeGraph
+        varNodes    = S.toList $ allLabels labelIsVar mergeGraph
         --  Obtain list of possible remappings for non-variable nodes
         mapList     = remapLabelList nonvarNodes varNodes
         mapSubLists = (tail . subsequences) mapList
-        mapGr ls = fmap (\l -> mapFind l l (makeLookupMap ls))
+        mapGr ls = fmapNSGraph (\l -> mapFind l l (makeLookupMap ls))
     in
         --  Return all remappings of the original merged graph
         flist (map mapGr mapSubLists) mergeGraph
 rdfInstanceEntailBwdApply vocab cons =
     let
         --  Obtain list of variable nodes
-        varNodes     = allLabels labelIsVar cons
+        varNodes     = S.toList $ allLabels labelIsVar cons
         --  Generate a substitution for each combination of variable
         --  and vocabulary node.
         varBindings  = map (makeVarBinding . zip varNodes) vocSequences
                         else foldl1 merge ante
     in
         --  Return all subgraphs of the full graph constructed above
-        map (setArcs mergeGraph) (init $ tail $ subsequences $ getArcs mergeGraph)
+        -- TODO: update to use sets as appropriate
+        map (setArcs mergeGraph . S.fromList) (init $ tail $ subsequences $ S.toList $ getArcs mergeGraph)
 
 --  Subgraph entailment inference checker
 --
                         else foldl1 addGraphs ante
     in
         --  Check each consequent graph arc is in the antecedent graph
-        getArcs cons `subset` getArcs fullGraph
+        getArcs cons `S.isSubsetOf` getArcs fullGraph
 
 ------------------------------------------------------------
 --  RDF simple entailment inference rule

src/Swish/RDF/Query.hs

     , resRdfFirst
     , resRdfRest
     , resRdfNil
+    , traverseNSGraph
     )
 
 import Swish.RDF.VarBinding (RDFVarBinding, RDFVarBindingFilter)
 import Data.Monoid (Monoid(..))
 
 import qualified Data.Set as S
-import qualified Data.Traversable as Traversable
 
 ------------------------------------------------------------
 --  Primitive RDF graph queries
 ------------------------------------------------------------
 
+-- Get a list of arcs from a graph.
+-- 
+-- Can we update the routines to work with sets instead?
+
+getTriples :: RDFGraph -> [RDFTriple]
+getTriples = S.toList . getArcs
+
 -- | Basic graph-query function.
 --
 --  The triples of the query graph are matched sequentially
   -- ^ Each element represents a set of variable bindings that make the query graph a
   -- subgraph of the target graph. The list can be empty.
 rdfQueryFind =
-    rdfQueryPrim1 matchQueryVariable nullRDFVarBinding . getArcs
+    rdfQueryPrim1 matchQueryVariable nullRDFVarBinding . getTriples
 
 --  Helper function to match query against a graph.
 --  A node-query function is supplied to determine how query nodes
     -> [RDFVarBinding]
 rdfQueryPrim1 _     initv []       _  = [initv]
 rdfQueryPrim1 nodeq initv (qa:qas) tg =
-    let
-        qam  = fmap (applyVarBinding initv) qa      -- subst vars already bound
+    let qam  = fmap (applyVarBinding initv) qa      -- subst vars already bound
         newv = rdfQueryPrim2 nodeq qam tg           -- new bindings, or null
-    in
-        concat
-            [ rdfQueryPrim1 nodeq v2 qas tg
-            | v1 <- newv
-            , let v2 = joinVarBindings initv v1
-            ]
+    in concat
+           [ rdfQueryPrim1 nodeq v2 qas tg
+             | v1 <- newv
+           , let v2 = joinVarBindings initv v1
+           ]
 
 --  Match single query term against graph, and return any new sets
 --  of variable bindings thus defined, or [] if the query term
     -> RDFGraph
     -> [RDFVarBinding]
 rdfQueryPrim2 nodeq qa tg =
-        mapMaybe (getBinding nodeq qa) (getArcs tg)
+        mapMaybe (getBinding nodeq qa) (S.toList $ getArcs tg)
 
 -- |RDF query filter.
 --
 --  An empty outer list is returned if no combination of
 --  substitutions can infer the supplied target.
 --
-rdfQueryBack :: RDFGraph -> RDFGraph -> [[RDFVarBinding]]
+rdfQueryBack :: 
+    RDFGraph    -- ^ Query graph
+    -> RDFGraph -- ^ Target graph
+    -> [[RDFVarBinding]]
 rdfQueryBack qg tg =
-    rdfQueryBack1 matchQueryVariable [] (getArcs qg) (getArcs tg)
+    let ga = getTriples
+    in rdfQueryBack1 matchQueryVariable [] (ga qg) (ga tg)
 
 rdfQueryBack1 ::
     NodeQuery RDFLabel -> [RDFVarBinding] -> [Arc RDFLabel] -> [Arc RDFLabel]
 --  has been concluded.
 rdfQueryInstance :: RDFGraph -> RDFGraph -> [RDFVarBinding]
 rdfQueryInstance =
-    rdfQueryPrim1 matchQueryBnode nullRDFVarBinding . getArcs
+    rdfQueryPrim1 matchQueryBnode nullRDFVarBinding . getTriples
 
 ------------------------------------------------------------
 --  Primitive RDF graph query support functions
     [ remapLabels vs bs makeBlank g
     | v <- vars
     , let (g,vs) = rdfQuerySubs2 v gr
-    , let bs     = allLabels isBlank g
+    , let bs     = S.toList $ allLabels isBlank g
     ]
 
 -- |Graph back-substitution function, replacing variables with bnodes.
 --  unbound variables.
 --
 --  Adding an empty graph forces elimination of duplicate arcs.
-rdfQuerySubs2 :: RDFVarBinding -> RDFGraph -> (RDFGraph,[RDFLabel])
-rdfQuerySubs2 varb gr = (addGraphs mempty g, S.toList vs)
+rdfQuerySubs2 :: RDFVarBinding -> RDFGraph -> (RDFGraph, [RDFLabel])
+rdfQuerySubs2 varb gr = (addGraphs mempty g, S.toList vs) -- the addgraphs part is important, possibly just to remove duplicated entries
     where
-        (g,vs) = runState ( Traversable.traverse (mapNode varb) gr ) S.empty
+        (g,vs) = runState (traverseNSGraph (mapNode varb) gr) S.empty
 
 --  Auxiliary monad function for rdfQuerySubs2.
 --  This returns a state transformer Monad which in turn returns the
 --  Custom predicates can also be used.
 --
 rdfFindArcs :: (RDFTriple -> Bool) -> RDFGraph -> [RDFTriple]
-rdfFindArcs p = filter p . getArcs
+rdfFindArcs p = S.toList . S.filter p . getArcs
 
 -- |Test if statement has given subject
 rdfSubjEq :: RDFLabel -> RDFTriple -> Bool

src/Swish/RDF/Ruleset.hs

     )
 
 import Swish.RDF.Graph
-    ( RDFLabel(..), RDFGraph
+    ( RDFLabel(..), RDFGraph, RDFTriple
     , makeBlank, newNodes
     , merge, allLabels
     , toRDFGraph)
 import Data.Maybe (fromMaybe)
 import Data.Monoid (Monoid(..))
 
+import qualified Data.Set as S
 import qualified Data.Text.Lazy.Builder as B
 
 ------------------------------------------------------------
 --  RDF graph query and substitution support functions
 ------------------------------------------------------------
 
-queryFind :: [Arc RDFLabel] -> RDFGraph -> [RDFVarBinding]
-queryFind qas = rdfQueryFind (toRDFGraph qas)
+toGr :: [RDFTriple] -> RDFGraph
+toGr = toRDFGraph . S.fromList
 
-queryBack :: [Arc RDFLabel] -> RDFGraph -> [[RDFVarBinding]]
-queryBack qas = rdfQueryBack (toRDFGraph qas)
+queryFind :: [RDFTriple] -> RDFGraph -> [RDFVarBinding]
+queryFind qas = rdfQueryFind (toGr qas)
 
-querySubs :: [RDFVarBinding] -> [Arc RDFLabel] -> [RDFGraph]
-querySubs vars = rdfQuerySubs vars . toRDFGraph
+queryBack :: [RDFTriple] -> RDFGraph -> [[RDFVarBinding]]
+queryBack qas = rdfQueryBack (toGr qas)
 
-querySubsBlank :: [RDFVarBinding] -> [Arc RDFLabel] -> [RDFGraph]
-querySubsBlank vars = rdfQuerySubsBlank vars . toRDFGraph
+querySubs :: [RDFVarBinding] -> [RDFTriple] -> [RDFGraph]
+querySubs vars = rdfQuerySubs vars . toGr
+
+querySubsBlank :: [RDFVarBinding] -> [RDFTriple] -> [RDFGraph]
+querySubsBlank vars = rdfQuerySubsBlank vars . toGr
 
 ------------------------------------------------------------
 --  Method for creating an RDF formula value from N3 text
 makeRDFClosureRule sname antgrs congr vmod = makeGraphClosureRule
     GraphClosure
         { nameGraphRule = sname
-        , ruleAnt       = concatMap getArcs antgrs
-        , ruleCon       = getArcs congr
+        , ruleAnt       = concatMap (S.toList . getArcs) antgrs -- TODO: improve
+        , ruleCon       = S.toList $ getArcs congr
         , ruleModify    = vmod
         }
 
     where
         antgr = makeRDFGraphFromN3Builder ant
         congr = makeRDFGraphFromN3Builder con
-        vmod  = aloc (allLabels labelIsVar antgr)
+        vmod  = aloc $ S.toList (allLabels labelIsVar antgr)
         modc  = fromMaybe varBindingId $ vbmCompose vmod vflt
 
 ------------------------------------------------------------

src/Swish/RDF/Vocabulary.hs

 instance Eq LanguageTag where
     LanguageTag _ t1 == LanguageTag _ t2 = t1 == t2
 
+instance Ord LanguageTag where
+    LanguageTag _ t1 `compare` LanguageTag _ t2 = t1 `compare` t2
+
 -- | Create a 'LanguageTag' element from the label.
 -- 
 -- Valid tags follow the ABNF from RCF 3066, which is

src/Swish/Utils/ListHelpers.hs

 
 module Swish.Utils.ListHelpers
        ( -- list of modules the routine is used in
-         subset -- Proof, RDF.Proof, VarBinding [also defined in Data.Ord.Partial]
-       , equiv -- GraphMatch, RDF.Ruleset, Script, VarBinding, Data.LookupMap
+         equiv -- GraphMatch, RDF.Ruleset, Script, VarBinding, Data.LookupMap
+               -- tests: GraphPartitionTest, RDFGraphTest, TestHelpers
        , flist -- Datatype, RDF.Proof, RDF.Ruleset, Script, VarBinding, ...
         
       )

src/Swish/VarBinding.hs

 
 import Swish.RDF.Vocabulary (swishName)
 
-import Swish.Utils.ListHelpers (equiv, subset, flist)
+import Swish.Utils.ListHelpers (flist)
 
+import Data.Function (on)
 import Data.List (find, intersect, union, (\\), foldl', permutations)
 import Data.LookupMap (LookupEntryClass(..), makeLookupMap, mapFindMaybe)
 import Data.Maybe (mapMaybe, fromMaybe, isJust, fromJust, listToMaybe)
-import Data.Monoid (mconcat)
+import Data.Monoid (Monoid(..), mconcat)
+
+import qualified Data.Set as S
 
 ------------------------------------------------------------
 --  Query variable bindings
 ------------------------------------------------------------
 
--- TODO: is it worth making a Monoid instance of VarBinding?
-
 -- |VarBinding is the type of an arbitrary variable bindings
 --  value, where the type of the bound values is not specified.
 --
     , vbNull :: Bool
     }
 
--- |VarBinding is an instance of class Eq, so that variable
---  bindings can be compared for equivalence
+-- | The Eq instance is defined as the set equivalence of the
+--   pairs of variables in the binding.
 --
-instance (Eq a, Eq b) => Eq (VarBinding a b) where
-    vb1 == vb2 = vbEnum vb1 `equiv` vbEnum vb2
+instance (Ord a, Ord b) => Eq (VarBinding a b) where
+    (==) = (==) `on` (S.fromList . vbEnum)
 
--- |VarBinding is an instance of class Show, so that variable
---  bindings can be displayed
+-- | The Ord instance is defined only on the pairs of
+--   variables in the binding.
+instance (Ord a, Ord b) => Ord (VarBinding a b) where
+    compare = compare `on` vbEnum
+
+-- | When combining instances, if there is an overlapping binding then
+--   the  value from the first instance is used.
+instance (Eq a) => Monoid (VarBinding a b) where
+    mempty = nullVarBinding
+    mappend = joinVarBindings
+
+-- | The Show instance only displays the pairs of variables
+--    in the binding.
 --
 instance (Show a, Show b) => Show (VarBinding a b) where
     show = show . vbEnum
 
--- | maps no query variables.
+-- | The null, or empry, binding maps no query variables.
+--   This is the 'mempty' instance of the Monoid.
 --
 nullVarBinding :: VarBinding a b
 nullVarBinding = VarBinding
 --  is a subset of another;  i.e. every query variable mapping defined
 --  by one is also defined by the other.
 --
-subBinding :: (Eq a, Eq b) => VarBinding a b -> VarBinding a b -> Bool
-subBinding vb1 vb2 = vbEnum vb1 `subset` vbEnum vb2
+subBinding :: (Ord a, Ord b) => VarBinding a b -> VarBinding a b -> Bool
+subBinding = S.isSubsetOf `on` (S.fromList . vbEnum)
 
 -- |Function to make a variable binding from a list of
 --  pairs of variable and corresponding assigned value.
 -- |Join a pair of query bindings, returning a new binding that
 --  maps all variables recognized by either of the input bindings.
 --  If the bindings should overlap, such overlap is not detected and
---  the value from the first binding provided is used arbitrarily.
+--  the value from the first binding provided is used.
 --
 joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b
 joinVarBindings vb1 vb2
 Name:               swish
-Version:            0.7.0.3
+Version:            0.8.0.0
 Stability:          experimental
 License:            LGPL
 License-file:       LICENSE 
   .
   * Complete, ready-to-run, command-line and script-driven programs.
   .
-  Changes in version @0.7.0.2@:
+  Changes in version @0.8.0.0@:
   .
-  * The @Swish.QName.LName@ type now requires all characters to be
-  ASCII. This avoids downstream errors when trying to convert a
-  @QName@ to a @URI@.
+  * The @LDGraph@ class now uses @Set (Arc lb)@, rather than @[Arc lb]@,
+  for @setArcs@, @getArcs@, and @update@. The @NSGraph@ instance now uses
+  a set rather than a list internally. There are a number of API tweaks -
+  e.g. the addition of Ord constraints and the removal of Functor, Foldable,
+  and Traversable instances. Not all list of Arcs have been converted
+  since a review is needed to see where it makes sense and where it does not.
+  This definitely speeds up some operations but
+  a full analysis has not been attempted.
   .
-  Changes in version @0.7.0.1@:
-  .
-  * Internal changes to parsing of URI values for NTriples, Turtle, and N3
-  parsers (error messages will be slightly different when IRIs are used).
-  Unfortunately IRIs are still not supported. 
-  .
-  Changes in version @0.7.0.0@:
-  .
-  For code that uses the Swish script language, the main change is to import @Swish@ rather
-  than @Swish.RDF.SwishMain@, and to note that the other @Swish.RDF.Swish*@ modules are
-  now called @Swish.*@.
-  .
-  For code that uses the graph library, the main changes are that @Swish.RDF.RDFGraph@
-  is now called @Swish.RDF.Graph@, the @Lit@ constructor of the @RDFLabel@ has been split
-  into three (@Lit@, @LangLit@, and @TypedLit@) and a new @LanguageTag@ type introduced,
-  local names now use the @LName@ type (previously they were just @Text@ values), and the
-  parsers and formatters have renamed to
-  @Swish.RDF.Parser.*@ and @Swish.RDF.Formatter.*@.
-  .
-  * Moved a number of modules around: generic code directly into @Swish@
-  and the @Swish.RDF.RDF*@ forms renamed to @Swish.RDF.*@. Some modules
-  have been moved out of the @Swish.Utils.*@ namespace. Generic modules
-  have been placed into the @Data.*@ namespace. The @Swish.RDF.Swish*@
-  modules have been moved to @Swish.*@ and @Swish.RDF.SwishMain@ has
-  been removed; use @Swish@ instead.
-  .
-  * Parsing modules are now in the @Swish.RDF.Parser@ hierarchy and
-  @Swish.RDF.RDFParser@ has been renamed to @Swish.RDF.Parser.Utils@.
-  .
-  * Formatting modules are now in the @Swish.RDF.Formatter@ hierarchy.
-  .
-  * RDF literals are now stored using the @Lit@, @LangLit@, or @TypedLit@ constructors
-  (@RDFLabel@) rather than using just @Lit@. Language codes are now represented
-  by @Swish.RDF.Vocabulary.LanguageTag@ rather than as a @ScopedName@.
-  .
-  * Local names are now represented by the @Swish.QName.LName@ type 
-  rather than as a @Text@ value. A few routines now return a @Maybe@ value
-  rather than error-ing out on invalid input.
-  .
-  * Make use of @Data.List.NonEmpty@ in a few cases.
-  .
-  * Removed @mkTypedLit@ from @Swish.RDF.RDFParser@; use
-  @Swish.RDF.RDFDatatype.makeDataTypedLiteral@ instead.
-  .
-  * Removed @asubj@, @apred@ and @aobj@ from @Swish.RDF.GraphClass@ and
-  @Swish.RDF.RDFGraph@; use @arcSubj@, @arcPred@ or @arcObj@ instead.
-  .
-  * Removed un-used @containedIn@ element of the @LDGraph@ type class.
-  The arguments to @setArcs@ have been flipped, @replaceArcs@ removed,
-  @add@ renamed to @addGraphs@, and @emptyGraph@ added.
-  .
-  * Removed un-used exports from @Swish.Utils.PartOrderedCollection@: 
-  @partCompareOrd@, @partCompareMaybe@, @partCompareListOrd@, and
-  @partCompareListPartOrd@.
-  .
-  * Removed the @Swish.Utils.MiscHelpers@ module and moved single-use functionality
-  out of @Swish.Utils.ListHelpers@.
-  .
-  * Removed various exported symbols from a range of modules as they were
-  unused.
-  .
-  * Use @Word32@ rather than @Int@ for label indexes (@Swish.GraphMatch.LabelIndex@)
-  and in the bnode counts when formatting to N3/Turtle.
-  .
-  * Minor clean up of the @LookupMap@ module: @mergeReplaceOrAdd@ and @mergeReplace@
-  are now combined into @mergeReplace@; @mapSelect@, @mapApplyToAll@, and
-  @mapTranslate*@ have been removed; documentation slightly improved;
-  and a few minor internal clean ups.
-  .
-  * Clarified that @Swish.RDF.RDFDatatypeXsdDecimal@ is for @xsd:decimal@ rather
-  than @xsd:double@.
-  .
-  * Support using versions 0.8 or 0.9 of the @intern@ package and version 0.5 of
-  @containers@.
-  .
-  * Switch to @Control.Exception.try@ to avoid deprecation warnings from @System.IO.Error.try@.
+  * A few other minor changes have been made: the removal of subset from
+  @Swish.Utils.ListHelpers@; the ordering used for @RDFLabel@ values has
+  changed; added a @Monoid@ instance for @VarBinding@; added @Ord@
+  instances for a number of containers.
   .
   Changes in previous versions can be found at <https://bitbucket.org/doug_burke/swish/src/tip/CHANGES>.
   .
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
       swish
 
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
-      semigroups >= 0.5 && < 0.9,
+      semigroups,
       swish
 
 Test-Suite test-graph
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers, 
       HUnit == 1.2.*,
       swish
 
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers,
       HUnit == 1.2.*,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-n3parser
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-n3formatter
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-rdfdatatypexsdinteger
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-rdfgraph
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
-      old-locale == 1.0.*,
+      network,
+      old-locale,
       swish,
-      text == 0.11.*,
-      time >= 1.1 && < 1.5
+      text,
+      time
 
 Test-Suite test-rdfproofcontext
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-rdfproof
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-rdfquery
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-rdfruleset
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
+      containers,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
 Test-Suite test-varbinding
    type:       exitcode-stdio-1.0
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
       swish
 
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
       swish
 
       -Wall -fno-warn-orphans
 
    Build-Depends:
-      base >=3 && < 5,
+      base,
       HUnit == 1.2.*,
-      network >= 2.2 && < 2.4,
+      network,
       swish,
-      text == 0.11.*
+      text
 
  -- we do not have the data files to run this test
  Executable         SwishTest

tests/GraphTest.hs

 --
 --------------------------------------------------------------------------------
 
-{- 
-
-Note: after changing the hash module the order and values of some
-of the tests; I have not checked that the new ordering makes sense.
-
--}
-
 module Main where
 
 import qualified Data.Foldable as F
 	, equivalenceClasses
       )
 
-import Swish.Utils.ListHelpers (subset)
+-- import Swish.Utils.ListHelpers (subset)
 
 import Data.LookupMap (LookupEntryClass(..), makeLookupMap)
 
-import TestHelpers (runTestSuite, testEq, testEqv)
+import TestHelpers (runTestSuite, testEq)
 
 import Data.List (sort, elemIndex)
 import Data.Maybe (fromJust)
 import Data.Ord (comparing)
 import Data.Word (Word32)
 
+import qualified Data.Set as S
+
 default ( Int )
 
 ------------------------------------------------------------
 base4 = "http://id.ninebynine.org/wip/2003/test/graph3/nodebase"
 
 ------------------------------------------------------------
---  Set, get graph arcs as lists of triples
+--  Set, get graph arcs as sets of triples
 ------------------------------------------------------------
 
-setArcsT :: (LDGraph lg lb) =>
-            [(lb, lb, lb)] -> lg lb -> lg lb
-setArcsT a g = setArcs g $ map arcFromTriple a
+setArcsT :: (Ord lb, LDGraph lg lb) =>
+            S.Set (lb, lb, lb) -> lg lb -> lg lb
+setArcsT a g = setArcs g $ S.map arcFromTriple a
 
-getArcsT :: (LDGraph lg lb) =>
-            lg lb -> [(lb, lb, lb)]
-getArcsT g = map arcToTriple $ getArcs g
-
-------------------------------------------------------------
---  Test class helper
-------------------------------------------------------------
-
-testeq :: (Show a, Eq a) => String -> a -> a -> Test
-testeq = testEq
-{-
-testeq lab req got =
-    TestCase ( assertEqual ("test"++lab) req got )
--}
-
-testeqv :: (Show a, Eq a) => String -> [a] -> [a] -> Test
-testeqv = testEqv
-{-
-testeqv lab req got =
-    TestCase ( assertEqual ("test"++lab) True (req `equiv` got) )
--}
+getArcsT :: (Ord lb, LDGraph lg lb) =>
+            lg lb -> S.Set (lb, lb, lb)
+getArcsT g = S.map arcToTriple $ getArcs g
 
 ------------------------------------------------------------
 --  Label map and entry creation helpers
 -- other tests still test this routine
 
 testSelect :: String -> String -> String -> Test
-testSelect lab = testeq ("Select"++lab )
+testSelect lab = testEq ("Select"++lab )
 
 isOne :: Int -> Bool
 isOne = (1 ==)
 
 -}
 
--- subset
+-- subset: hopefully can remove soon
+
+{-
 
 testSubset :: String -> Bool -> [Int] -> [Int] -> Test
-testSubset lab res l1s l2s = testeq ("Mapset"++lab ) res (l1s `subset` l2s)
+testSubset lab res l1s l2s = testEq ("Mapset"++lab ) res (l1s `subset` l2s)
 
 testSubsetSuite :: Test
 testSubsetSuite = TestList
     , testSubset "08" False [1,2,3]       []
     ]
 
+-}
+
 ------------------------------------------------------------
 --  Simple graph label tests
 ------------------------------------------------------------
 
 testLabSuite :: Test
 testLabSuite = TestList
-    [ testeq "Lab01" False (labelIsVar lab1f)
-    , testeq "Lab02" True  (labelIsVar lab1v)
-    , testeq "Lab03" False (labelIsVar lab2f)
-    , testeq "Lab04" True  (labelIsVar lab2v)
+    [ testEq "Lab01" False (labelIsVar lab1f)
+    , testEq "Lab02" True  (labelIsVar lab1v)
+    , testEq "Lab03" False (labelIsVar lab2f)
+    , testEq "Lab04" True  (labelIsVar lab2v)
 
-    , testeq "Lab05" 39495998 (labelHash 1 lab1f)
-    , testeq "Lab06" 45349309 (labelHash 1 lab1v)
-    , testeq "Lab07" 39495997 (labelHash 1 lab2f)
-    , testeq "Lab08" 45349310 (labelHash 1 lab2v)
+    , testEq "Lab05" 39495998 (labelHash 1 lab1f)
+    , testEq "Lab06" 45349309 (labelHash 1 lab1v)
+    , testEq "Lab07" 39495997 (labelHash 1 lab2f)
+    , testEq "Lab08" 45349310 (labelHash 1 lab2v)
     
 
-    , testeq "Lab09" "!lab1" (show lab1f)
-    , testeq "Lab10" "?lab1" (show lab1v)
-    , testeq "Lab11" "!lab2" (show lab2f)
-    , testeq "Lab12" "?lab2" (show lab2v)
+    , testEq "Lab09" "!lab1" (show lab1f)
+    , testEq "Lab10" "?lab1" (show lab1v)
+    , testEq "Lab11" "!lab2" (show lab2f)
+    , testEq "Lab12" "?lab2" (show lab2v)
 
-    , testeq "Lab13" "lab1" (getLocal lab1v)
-    , testeq "Lab14" "lab2" (getLocal lab2v)
-    , testeq "Lab15" lab1v  (makeLabel "lab1")
-    , testeq "Lab16" lab2v  (makeLabel "lab2")
+    , testEq "Lab13" "lab1" (getLocal lab1v)
+    , testEq "Lab14" "lab2" (getLocal lab2v)
+    , testEq "Lab15" lab1v  (makeLabel "lab1")
+    , testEq "Lab16" lab2v  (makeLabel "lab2")
     ]
 
 ------------------------------------------------------------
 lab2f = LF "lab2"
 lab2v = LV "lab2"
 
-gr1 :: GraphMem LabelMem
-gr1 = GraphMem { arcs=[]::[Statement] }
-
-ga1 :: [(LabelMem, LabelMem, LabelMem)]
-ga1 =
+ga1 :: S.Set (LabelMem, LabelMem, LabelMem)
+ga1 = S.fromList
     [
     (lab1f,lab1f,lab1f),
     (lab1v,lab1v,lab1v),
 
 gs4 :: Statement -> Bool
 gs4 (Arc _ _ (LV "lab2")) = True
-gs4 (Arc _ _  _         ) = False
+gs4 _                     = False
 
-ga4 :: [(LabelMem, LabelMem, LabelMem)]
-ga4 =
+ga4 :: S.Set (LabelMem, LabelMem, LabelMem)
+ga4 = S.fromList
     [
     (lab2v,lab2v,lab2v),
     (lab1f,lab1f,lab2v),
     (lab1v,lab2f,lab2v)
     ]
 
-gr2 :: GraphMem LabelMem
-gr2 = GraphMem { arcs=[]::[Statement] }
-
-ga2 :: [(LabelMem, LabelMem, LabelMem)]
-ga2 =
+ga2 :: S.Set (LabelMem, LabelMem, LabelMem)
+ga2 = S.fromList
     [
     (lab1f,lab1f,lab1f),
     (lab1v,lab1v,lab1v),
     (lab2v,lab2v,lab2v)
     ]
 
-gr3 :: GraphMem LabelMem
-gr3 = GraphMem { arcs=[]::[Statement] }
-
-ga3 :: [(LabelMem, LabelMem, LabelMem)]
-ga3 =
+ga3 :: S.Set (LabelMem, LabelMem, LabelMem)
+ga3 = S.fromList
     [
     (lab1f,lab1f,lab1v),
     (lab1f,lab1f,lab2f),
     (lab1v,lab2f,lab2v)
     ]
 
-gl4 :: [LabelMem]
-gl4 = [lab1f,lab1v,lab2f,lab2v]
+gl4 :: S.Set LabelMem
+gl4 = S.fromList [lab1f,lab1v,lab2f,lab2v]
 
 gr1a, gr2a, gr3a, gr4a, gr4b, gr4c, gr4d, gr4e,
   gr4g :: GraphMem LabelMem
-gr1a = setArcsT ga1 gr1
-gr2a = setArcsT ga2 gr2
-gr3a = setArcsT ga3 gr3
+gr1a = setArcsT ga1 (GraphMem S.empty)
+gr2a = setArcsT ga2 emptyGraph
+gr3a = setArcsT ga3 emptyGraph
 gr4a = addGraphs gr2a gr3a
 gr4b = addGraphs gr3a gr2a
 gr4c = delete gr2a gr4a
 gr4e = extract gs4 gr4a
 gr4g = addGraphs gr2a gr4a
 
-gl4f :: [LabelMem]
+gl4f :: S.Set LabelMem
 gl4f = labels gr4a
 
+{-
 gr4ee :: [Bool]
-gr4ee = map gs4 (getArcs gr4a)
+gr4ee = map gs4 $ S.toList (getArcs gr4a)
+-}
 
 testGraphSuite :: Test
 testGraphSuite = TestList
-    [ testeq "Graph01" ga1 (getArcsT gr1a)
-    , testeq "Graph01" ga2 (getArcsT gr2a)
-    , testeq "Graph03" ga3 (getArcsT gr3a)
-    , testeqv "Graph04" ga1 (getArcsT gr4a)
-    , testeqv "Graph05" ga1 (getArcsT gr4b)
-    , testeqv "Graph06" ga3 (getArcsT gr4c)
-    , testeqv "Graph07" ga2 (getArcsT gr4d)
-    , testeqv "Graph08" ga4 (getArcsT gr4e)
-    , testeqv "Graph09" gl4 gl4f
-    , testeq "Graph10" ga1 (getArcsT gr4g)
+    [ testEq "Graph01" ga1 (getArcsT gr1a)
+    , testEq "Graph01" ga2 (getArcsT gr2a)
+    , testEq "Graph03" ga3 (getArcsT gr3a)
+    , testEq "Graph04" ga1 (getArcsT gr4a)
+    , testEq "Graph05" ga1 (getArcsT gr4b)
+    , testEq "Graph06" ga3 (getArcsT gr4c)
+    , testEq "Graph07" ga2 (getArcsT gr4d)
+    , testEq "Graph08" ga4 (getArcsT gr4e)
+    , testEq "Graph09" gl4 gl4f
+    , testEq "Graph10" ga1 (getArcsT gr4g)
     ]
 
 ------------------------------------------------------------
 -- showLabelMap :: (Label lb) => LabelMap lb -> String
 
 testShowLabelMap :: Test
-testShowLabelMap = testeq "showLabelMap" showMap (show lmap)
+testShowLabelMap = testEq "showLabelMap" showMap (show lmap)
     where
         showMap = "LabelMap gen=5, map=\n"++
                   "    !s1:(1,1)\n"++
                   "    !o3:(3,3)"
 
 testMapLabelHash00 :: Test
-testMapLabelHash00 = testeq "mapLabelHash00" showMap (show lmap1)
+testMapLabelHash00 = testEq "mapLabelHash00" showMap (show lmap1)
     where
         showMap = "LabelMap gen=5, map=\n"++
                   "    !s1:(1,1)\n"++
   [ testShowLabelMap
   , testMapLabelHash00
 
-  , testeq "testMapLabelIndex01" (1,1) (mapLabelIndex lmap s1 )
-  , testeq "testMapLabelIndex02" (2,2) (mapLabelIndex lmap s2 )
-  , testeq "testMapLabelIndex03" (3,3) (mapLabelIndex lmap s3 )
-  , testeq "testMapLabelIndex04" (4,4) (mapLabelIndex lmap s4 )
-  , testeq "testMapLabelIndex05" (1,1) (mapLabelIndex lmap o1 )
-  , testeq "testMapLabelIndex06" (4,4) (mapLabelIndex lmap o4 )
-  , testeq "testMapLabelIndex07" nullLabelVal (mapLabelIndex lmap o5 )
-  , testeq "testMapLabelIndex08" nullLabelVal (mapLabelIndex lmap o6 )
+  , testEq "testMapLabelIndex01" (1,1) (mapLabelIndex lmap s1 )
+  , testEq "testMapLabelIndex02" (2,2) (mapLabelIndex lmap s2 )
+  , testEq "testMapLabelIndex03" (3,3) (mapLabelIndex lmap s3 )
+  , testEq "testMapLabelIndex04" (4,4) (mapLabelIndex lmap s4 )
+  , testEq "testMapLabelIndex05" (1,1) (mapLabelIndex lmap o1 )
+  , testEq "testMapLabelIndex06" (4,4) (mapLabelIndex lmap o4 )
+  , testEq "testMapLabelIndex07" nullLabelVal (mapLabelIndex lmap o5 )
+  , testEq "testMapLabelIndex08" nullLabelVal (mapLabelIndex lmap o6 )
 
-  , testeq "MapLabelHash01" (1,1)  (mapLabelIndex lmap1 s1 )
-  , testeq "MapLabelHash02" (5,22) (mapLabelIndex lmap1 s2 )
-  , testeq "MapLabelHash03" (3,3)  (mapLabelIndex lmap1 s3 )
-  , testeq "MapLabelHash04" (4,4)  (mapLabelIndex lmap1 s4 )
-  , testeq "MapLabelHash05" (1,1)  (mapLabelIndex lmap1 o1 )
-  , testeq "MapLabelHash06" (4,4)  (mapLabelIndex lmap1 o4 )
-  , testeq "MapLabelHash07" nullLabelVal (mapLabelIndex lmap1 o5 )
-  , testeq "MapLabelHash08" nullLabelVal (mapLabelIndex lmap1 o6 )
+  , testEq "MapLabelHash01" (1,1)  (mapLabelIndex lmap1 s1 )
+  , testEq "MapLabelHash02" (5,22) (mapLabelIndex lmap1 s2 )
+  , testEq "MapLabelHash03" (3,3)  (mapLabelIndex lmap1 s3 )
+  , testEq "MapLabelHash04" (4,4)  (mapLabelIndex lmap1 s4 )
+  , testEq "MapLabelHash05" (1,1)  (mapLabelIndex lmap1 o1 )
+  , testEq "MapLabelHash06" (4,4)  (mapLabelIndex lmap1 o4 )
+  , testEq "MapLabelHash07" nullLabelVal (mapLabelIndex lmap1 o5 )
+  , testEq "MapLabelHash08" nullLabelVal (mapLabelIndex lmap1 o6 )
 
-  , testeq "MapLabelHash11" (1,1)  (mapLabelIndex lmap2b s1 )
-  , testeq "MapLabelHash12" (5,22) (mapLabelIndex lmap2b s2 )
-  , testeq "MapLabelHash13" (3,3)  (mapLabelIndex lmap2b s3 )
-  , testeq "MapLabelHash14" (4,4)  (mapLabelIndex lmap2b s4 )
-  , testeq "MapLabelHash15" (5,66) (mapLabelIndex lmap2b o1 )
-  , testeq "MapLabelHash16" (2,2)  (mapLabelIndex lmap2b o2 )
-  , testeq "MapLabelHash17" (4,4)  (mapLabelIndex lmap2b o4 )
-  , testeq "MapLabelHash18" nullLabelVal (mapLabelIndex lmap1 o5 )
+  , testEq "MapLabelHash11" (1,1)  (mapLabelIndex lmap2b s1 )
+  , testEq "MapLabelHash12" (5,22) (mapLabelIndex lmap2b s2 )
+  , testEq "MapLabelHash13" (3,3)  (mapLabelIndex lmap2b s3 )
+  , testEq "MapLabelHash14" (4,4)  (mapLabelIndex lmap2b s4 )
+  , testEq "MapLabelHash15" (5,66) (mapLabelIndex lmap2b o1 )
+  , testEq "MapLabelHash16" (2,2)  (mapLabelIndex lmap2b o2 )
+  , testEq "MapLabelHash17" (4,4)  (mapLabelIndex lmap2b o4 )
+  , testEq "MapLabelHash18" nullLabelVal (mapLabelIndex lmap1 o5 )
     
-  , testeq "LabelMap01" (6,61) (mapLabelIndex lmap3 s1 )
-  , testeq "LabelMap02" (2,2)  (mapLabelIndex lmap3 s2 )
-  , testeq "LabelMap03" (6,63) (mapLabelIndex lmap3 s3 )
-  , testeq "LabelMap04" (4,4)  (mapLabelIndex lmap3 s4 )
-  , testeq "LabelMap05" (1,1)  (mapLabelIndex lmap3 o1 )
-  , testeq "LabelMap06" (6,66) (mapLabelIndex lmap3 o2 )
+  , testEq "LabelMap01" (6,61) (mapLabelIndex lmap3 s1 )
+  , testEq "LabelMap02" (2,2)  (mapLabelIndex lmap3 s2 )
+  , testEq "LabelMap03" (6,63) (mapLabelIndex lmap3 s3 )
+  , testEq "LabelMap04" (4,4)  (mapLabelIndex lmap3 s4 )
+  , testEq "LabelMap05" (1,1)  (mapLabelIndex lmap3 o1 )
+  , testEq "LabelMap06" (6,66) (mapLabelIndex lmap3 o2 )
     
   ]
 
 as5 = [t01,t02,t03,t04,t05,t06,t20,t21,t22]
 as6 = [t01,t02,t03,t04,t05,t06,t10,t11,t12,t20,t21,t22]
 
--- graphLabels :: (Label lb) => [Arc lb] -> [lb]
+-- graphLabels :: (Label lb) => [Arc lb] -> S.Set lb
 
-ls4 :: [LabelMem]
-ls4 = [s1,s2,s3,p1,p2,p3,o1,o2,o3,l1,l4,l10,b1,b2]
+-- not clear both the 'raw' and 'string' versions are still needed.
+
+ls4, glas4 :: S.Set LabelMem
+ls4   = S.fromList [s1,s2,s3,p1,p2,p3,o1,o2,o3,l1,l4,l10,b1,b2]
+glas4 = graphLabels as4
 
 testGraphLabels04, testGraphLabels14 :: Test
-testGraphLabels04 = testeqv "GraphLabels04" ls4 (graphLabels as4)
-testGraphLabels14 = testeq  "GraphLabels14" str (show (graphLabels as4))
+testGraphLabels04 = testEq "GraphLabels04" ls4 glas4
+testGraphLabels14 = testEq "GraphLabels14" str (show glas4)
     where
-        str = "[!s1,!p1,!o1,!s2,!o2,!s3,!o3,!l1,!l4-type1,!l10-xml,?b1,!p2,?b2,!p3]"
-        -- str = "[!p3,?b2,!p2,?b1,!l10-xml,!l4-type1,!l1,!o3,!s3,!o2,!s2,!o1,!p1,!s1]"
+      -- str = "[!s1,!p1,!o1,!s2,!o2,!s3,!o3,!l1,!l4-type1,!l10-xml,?b1,!p2,?b2,!p3]"
+      str = "fromList [!l1,!l10-xml,!l4-type1,!o1,!o2,!o3,!p1,!p2,!p3,!s1,!s2,!s3,?b1,?b2]"
+      -- str = show ls4
 
-ls5 :: [LabelMem]
-ls5 = [s1,s2,s3,p1,p2,p3,o1,o2,o3,l1,l4,l10,b3,b4]
+ls5, glas5 :: S.Set LabelMem
+ls5   = S.fromList [s1,s2,s3,p1,p2,p3,o1,o2,o3,l1,l4,l10,b3,b4]
+glas5 = graphLabels as5
 
 testGraphLabels05, testGraphLabels15 :: Test
-testGraphLabels05 = testeqv "GraphLabels05" ls5 (graphLabels as5)
-testGraphLabels15 = testeq  "GraphLabels15" str (show (graphLabels as5))
+testGraphLabels05 = testEq "GraphLabels05" ls5 glas5
+testGraphLabels15 = testEq "GraphLabels15" str (show glas5)
     where
-        str = "[!s1,!p1,!o1,!s2,!o2,!s3,!o3,!l1,!l4-type1,!l10-xml,?b3,!p2,?b4,!p3]"
-        -- str = "[!p3,?b4,!p2,?b3,!l10-xml,!l4-type1,!l1,!o3,!s3,!o2,!s2,!o1,!p1,!s1]"
+      -- str = "[!s1,!p1,!o1,!s2,!o2,!s3,!o3,!l1,!l4-type1,!l10-xml,?b3,!p2,?b4,!p3]"
+      str = "fromList [!l1,!l10-xml,!l4-type1,!o1,!o2,!o3,!p1,!p2,!p3,!s1,!s2,!s3,?b3,?b4]"
+      -- str = show ls5
 
-ls6 :: [LabelMem]
-ls6 = [s1,s2,s3,p1,p2,p3,o1,o2,o3,l1,l4,l10,b1,b2,b3,b4]
+ls6, glas6 :: S.Set LabelMem
+ls6   = S.fromList [s1,s2,s3,p1,p2,p3,o1,o2,o3,l1,l4,l10,b1,b2,b3,b4]
+glas6 = graphLabels as6
 
 testGraphLabels06, testGraphLabels16 :: Test
-testGraphLabels06 = testeqv "GraphLabels05" ls6 (graphLabels as6)
-testGraphLabels16 = testeq  "GraphLabels16" str (show (graphLabels as6))
+testGraphLabels06 = testEq "GraphLabels05" ls6 glas6
+testGraphLabels16 = testEq "GraphLabels16" str (show glas6)
     where
-        str = "[!s1,!p1,!o1,!s2,!o2,!s3,!o3"++
-              ",!l1,!l4-type1,!l10-xml,?b1,!p2,?b2,!p3,?b3,?b4]"
-        -- str = "[?b4,?b3,!p3,?b2,!p2,?b1,!l10-xml,!l4-type1,!l1"++
-        --       ",!o3,!s3,!o2,!s2,!o1,!p1,!s1]"
+      -- str = "[!s1,!p1,!o1,!s2,!o2,!s3,!o3"++
+      --       ",!l1,!l4-type1,!l10-xml,?b1,!p2,?b2,!p3,?b3,?b4]"
+      str = "fromList [!l1,!l10-xml,!l4-type1,!o1,!o2,!o3,!p1,!p2,!p3,!s1,!s2,!s3,?b1,?b2,?b3,?b4]"
+      -- str = show ls6
 
 -- assignLabels :: (Label lb) => [lb] -> LabelMap lb -> LabelMap lb
 
-lmap5 :: LabelMap LabelMem
-{-
-lmap5 = tstLabelMap 2 [(s1,(1,142577)),(s2,(1,142578)),(s3,(1,142579)),
-                       (p1,(1,142385)),(p2,(1,142386)),(p3,(1,142387)),
-                       (o1,(1,142321)),(o2,(1,142322)),(o3,(1,142323)),
-                       (l1,(1,142129)),(l4,(1,1709580)),(l10,(1,3766582)),
-                       (b3,(1,262143)),(b4,(1,262143))]
--}
-
 bhash :: Word32
 bhash = 23
 
 s2hash = 2720
 s3hash = 2721
 
+lmap5 :: LabelMap LabelMem
 lmap5 = tstLabelMap 2 
         [
           (b4,(1,bhash)),
         ]
 
 testAssignLabelMap05 :: Test        
-testAssignLabelMap05 = testeq "AssignLabels05" lmap5