packages feed

sets (empty) → 0.0.1

raw patch · 10 files changed

+981/−0 lines, 10 filesdep +QuickCheckdep +basedep +commutativesetup-changed

Dependencies added: QuickCheck, base, commutative, containers, contravariant, discrimination, hashable, quickcheck-instances, set-with, tasty, tasty-hunit, tasty-quickcheck, unordered-containers

Files

+ LICENSE view
@@ -0,0 +1,21 @@+The MIT License (MIT)++Copyright (c) 2015, The Grid++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in+all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+THE SOFTWARE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ sets.cabal view
@@ -0,0 +1,47 @@+Name:                   sets+Version:                0.0.1+Author:                 Athan Clark <athan.clark@gmail.com>+Maintainer:             Athan Clark <athan.clark@gmail.com>+License:                MIT+License-File:           LICENSE+Synopsis:               Various set designs in Haskell+-- Description:+Cabal-Version:          >= 1.10+Build-Type:             Simple++Library+  Default-Language:     Haskell2010+  HS-Source-Dirs:       src+  GHC-Options:          -Wall+  Exposed-Modules:      Data.Set.Class+                        Data.Set.Class.Types+                        Data.Set.Unordered.Unique+                        Data.Set.Unordered.Many+                        Data.Set.Ordered.Unique+                        Data.Set.Ordered.Many+  Build-Depends:        base >= 4.6 && < 5+                      , containers+                      , unordered-containers+                      , hashable+                      , set-with+                      , commutative+                      , contravariant+                      , discrimination++Test-Suite spec+  Type:                 exitcode-stdio-1.0+  Default-Language:     Haskell2010+  Hs-Source-Dirs:       src+                      , test+  Ghc-Options:          -Wall+  Main-Is:              Spec.hs+  Build-Depends:        base+                      , tasty+                      , tasty-quickcheck+                      , tasty-hunit+                      , QuickCheck+                      , quickcheck-instances++Source-Repository head+  Type:                 git+  Location:              https://github.com/athanclark/sets.git
+ src/Data/Set/Class.hs view
@@ -0,0 +1,469 @@+{-# LANGUAGE+    NoImplicitPrelude+  , MultiParamTypeClasses+  , UndecidableInstances+  , FlexibleInstances+  , FlexibleContexts+  , GeneralizedNewtypeDeriving+  , StandaloneDeriving+  #-}++-- | Convenience operators overloaded for arbitrary use.+-- There are no laws associated with these classes, just duck-typed so+-- we don't have to use the qualified versions of each function.++module Data.Set.Class+  ( module X+  , HasUnion (..)+  , HasDifference (..)+  , HasIntersection (..)+  , HasComplement (..)+  , HasSingleton (..)+  , HasSingletonWith (..)+  , HasEmpty (..)+  , HasEmptyWith (..)+  , HasTotal (..)+  , HasTotalWith (..)+  , HasSize (..)+  , CanBeSubset (..)+  , CanBeProperSubset (..)+  ) where++import Data.Set.Class.Types as X+import Prelude (Eq (..), Ord, Int, Bool (..), (&&), (||), ($), (.), not, const)+import Data.Foldable as Fold+import Data.Monoid as Monoid+import Data.Commutative as Comm++import qualified Data.Set as Set+import qualified Data.Map as Map+import qualified Data.Sequence as Seq+import qualified Data.IntSet as IntSet+import qualified Data.IntMap as IntMap+import qualified Data.List as List+import Data.Hashable (Hashable)+import qualified Data.HashSet as HashSet+import qualified Data.HashMap.Lazy as HashMap+import qualified Data.SetWith as SetWith+import qualified Data.Functor.Contravariant as Pred+import qualified Data.Set.Ordered.Many as OM+import Data.Discrimination as Disc+import qualified Data.Set.Unordered.Many as UM+import qualified Data.Set.Unordered.Unique as UU+import qualified Data.Set.Ordered.Unique.Finite as OUF+++class HasUnion s where+  union :: s -> s -> s++unions :: ( Fold.Foldable f+          , HasUnion s+          , HasEmpty s+          ) => f s -> s+unions = foldr Data.Set.Class.union empty++instance HasUnion s => Commutative (Union s) where+  commute = union++class HasDifference s where+  difference :: s -> s -> s++class HasIntersection s where+  intersection :: s -> s -> s++intersections :: ( Fold.Foldable f+                 , HasIntersection s+                 , HasTotal s+                 ) => f s -> s+intersections = foldr Data.Set.Class.intersection total++instance HasIntersection s => Commutative (Intersection s) where+  commute = intersection++class HasComplement s where+  complement :: s -> s++class HasSingleton s a where+  singleton :: a -> s++class HasSingletonWith s k a where+  singletonWith :: k -> a -> s++class HasEmpty s where+  empty :: s++instance (Commutative (Union s), HasEmpty s) => CommutativeId (Union s) where+  cempty = empty++class HasEmptyWith s k where+  emptyWith :: k -> s++class HasTotal s where+  total :: s++instance (Commutative (Intersection s), HasTotal s) => CommutativeId (Intersection s) where+  cempty = total++class HasTotalWith s k where+  totalWith :: k -> s++class HasSize s where+  size :: s -> Int++class CanBeSubset s where+  isSubsetOf :: s -> s -> Bool++class CanBeProperSubset s where+  isProperSubsetOf :: s -> s -> Bool+++-- Instances++-- Inherit+deriving instance HasUnion a             => HasUnion             (Union a)+deriving instance HasDifference a        => HasDifference        (Union a)+deriving instance HasIntersection a      => HasIntersection      (Union a)+deriving instance HasComplement a        => HasComplement        (Union a)+deriving instance HasSingleton x a       => HasSingleton x       (Union a)+deriving instance HasSingletonWith k x a => HasSingletonWith k x (Union a)+deriving instance HasEmpty a             => HasEmpty             (Union a)+deriving instance HasEmptyWith k a       => HasEmptyWith k       (Union a)+deriving instance HasTotal a             => HasTotal             (Union a)+deriving instance HasTotalWith k a       => HasTotalWith  k      (Union a)+deriving instance HasSize a              => HasSize              (Union a)+deriving instance CanBeSubset a          => CanBeSubset          (Union a)+deriving instance CanBeProperSubset a    => CanBeProperSubset    (Union a)+deriving instance HasUnion a             => HasUnion             (Intersection a)+deriving instance HasDifference a        => HasDifference        (Intersection a)+deriving instance HasIntersection a      => HasIntersection      (Intersection a)+deriving instance HasComplement a        => HasComplement        (Intersection a)+deriving instance HasSingleton x a       => HasSingleton x       (Intersection a)+deriving instance HasSingletonWith k x a => HasSingletonWith k x (Intersection a)+deriving instance HasEmpty a             => HasEmpty             (Intersection a)+deriving instance HasEmptyWith k a       => HasEmptyWith k       (Intersection a)+deriving instance HasTotal a             => HasTotal             (Intersection a)+deriving instance HasTotalWith k a       => HasTotalWith  k      (Intersection a)+deriving instance HasSize a              => HasSize              (Intersection a)+deriving instance CanBeSubset a          => CanBeSubset          (Intersection a)+deriving instance CanBeProperSubset a    => CanBeProperSubset    (Intersection a)+++-- Data.Set+instance Ord a => HasUnion (Set.Set a) where+  union = Set.union++instance Ord a => HasDifference (Set.Set a) where+  difference = Set.difference++instance Ord a => HasIntersection (Set.Set a) where+  intersection = Set.intersection++instance HasSingleton (Set.Set a) a where+  singleton = Set.singleton++instance HasEmpty (Set.Set a) where+  empty = Set.empty++instance HasSize (Set.Set a) where+  size = Set.size++instance Ord a => CanBeSubset (Set.Set a) where+  isSubsetOf = Set.isSubsetOf++instance Ord a => CanBeProperSubset (Set.Set a) where+  isProperSubsetOf = Set.isProperSubsetOf+++-- Data.Map+instance Ord k => HasUnion (Map.Map k a) where+  union = Map.union++instance Ord k => HasDifference (Map.Map k a) where+  difference = Map.difference++instance Ord k => HasIntersection (Map.Map k a) where+  intersection = Map.intersection++instance HasSingletonWith (Map.Map k a) k a where+  singletonWith = Map.singleton++instance HasEmpty (Map.Map k a) where+  empty = Map.empty++instance HasSize (Map.Map k a) where+  size = Map.size++instance (Eq k, Ord k, Eq a) => CanBeSubset (Map.Map k a) where+  isSubsetOf = Map.isSubmapOf++instance (Eq k, Ord k, Eq a) => CanBeProperSubset (Map.Map k a) where+  isProperSubsetOf = Map.isProperSubmapOf+++-- Data.List+instance HasSingleton [a] a where+  singleton = (:[])++instance HasEmpty [a] where+  empty = []++instance HasSize [a] where+  size = List.length++-- Data.Sequence+instance HasSingleton (Seq.Seq a) a where+  singleton = Seq.singleton++instance HasEmpty (Seq.Seq a) where+  empty = Seq.empty++instance HasSize (Seq.Seq a) where+  size = Seq.length++-- Data.IntSet+instance HasUnion IntSet.IntSet where+  union = IntSet.union++instance HasDifference IntSet.IntSet where+  difference = IntSet.difference++instance HasIntersection IntSet.IntSet where+  intersection = IntSet.intersection++instance HasSingleton IntSet.IntSet IntSet.Key where+  singleton = IntSet.singleton++instance HasEmpty IntSet.IntSet where+  empty = IntSet.empty++instance HasSize IntSet.IntSet where+  size = IntSet.size++instance CanBeSubset IntSet.IntSet where+  isSubsetOf = IntSet.isSubsetOf++instance CanBeProperSubset IntSet.IntSet where+  isProperSubsetOf = IntSet.isProperSubsetOf+++-- Data.IntMap+instance HasUnion (IntMap.IntMap a) where+  union = IntMap.union++instance HasDifference (IntMap.IntMap a) where+  difference = IntMap.difference++instance HasIntersection (IntMap.IntMap a) where+  intersection = IntMap.intersection++instance HasSingletonWith (IntMap.IntMap a) IntMap.Key a where+  singletonWith = IntMap.singleton++instance HasEmpty (IntMap.IntMap a) where+  empty = IntMap.empty++instance HasSize (IntMap.IntMap a) where+  size = IntMap.size++instance Eq a => CanBeSubset (IntMap.IntMap a) where+  isSubsetOf = IntMap.isSubmapOf++instance Eq a => CanBeProperSubset (IntMap.IntMap a) where+  isProperSubsetOf = IntMap.isProperSubmapOf+++-- Data.HashSet+instance (Hashable a, Eq a) => HasUnion (HashSet.HashSet a) where+  union = HashSet.union++instance (Hashable a, Eq a) => HasDifference (HashSet.HashSet a) where+  difference = HashSet.difference++instance (Hashable a, Eq a) => HasIntersection (HashSet.HashSet a) where+  intersection = HashSet.intersection++instance Hashable a => HasSingleton (HashSet.HashSet a) a where+  singleton = HashSet.singleton++instance HasEmpty (HashSet.HashSet a) where+  empty = HashSet.empty++instance HasSize (HashSet.HashSet a) where+  size = HashSet.size+++-- Data.HashMap+instance (Hashable k, Eq k) => HasUnion (HashMap.HashMap k a) where+  union = HashMap.union++instance (Hashable k, Eq k) => HasDifference (HashMap.HashMap k a) where+  difference = HashMap.difference++instance (Hashable k, Eq k) => HasIntersection (HashMap.HashMap k a) where+  intersection = HashMap.intersection++instance Hashable k => HasSingletonWith (HashMap.HashMap k a) k a where+  singletonWith = HashMap.singleton++instance HasEmpty (HashMap.HashMap k a) where+  empty = HashMap.empty++instance HasSize (HashMap.HashMap k a) where+  size = HashMap.size++-- Data.SetWith+instance Ord k => HasUnion (SetWith.SetWith k a) where+  union = SetWith.union++instance Ord k => HasDifference (SetWith.SetWith k a) where+  difference = SetWith.difference++instance Ord k => HasIntersection (SetWith.SetWith k a) where+  intersection = SetWith.intersection++instance Ord k => HasSingletonWith (SetWith.SetWith k a) (a -> k) a where+  singletonWith = SetWith.singleton++instance HasEmptyWith (SetWith.SetWith k a) (a -> k) where+  emptyWith = SetWith.empty++instance HasSize (SetWith.SetWith k a) where+  size = SetWith.size++instance (Ord k, Eq a) => CanBeSubset (SetWith.SetWith k a) where+  isSubsetOf = SetWith.isSubsetOf++instance (Ord k, Eq a) => CanBeProperSubset (SetWith.SetWith k a) where+  isProperSubsetOf = SetWith.isProperSubsetOf++-- Data.Functor.Contravariant.Predicate+instance HasUnion (Pred.Predicate a) where+  union (Pred.Predicate f) (Pred.Predicate g) = Pred.Predicate $ \x -> f x || g x++instance HasDifference (Pred.Predicate a) where+  difference (Pred.Predicate f) (Pred.Predicate g) = Pred.Predicate $ \x -> f x && not (g x)++instance HasIntersection (Pred.Predicate a) where+  intersection (Pred.Predicate f) (Pred.Predicate g) = Pred.Predicate $ \x -> f x && g x++instance HasComplement (Pred.Predicate a) where+  complement (Pred.Predicate f) = Pred.Predicate $ not . f++instance Eq a => HasSingleton (Pred.Predicate a) a where+  singleton a = Pred.Predicate $ \x -> a == x++instance HasEmpty (Pred.Predicate a) where+  empty = Pred.Predicate $ const False++instance HasTotal (Pred.Predicate a) where+  total = Pred.Predicate $ const True+++-- Data.Set.Ordered.Many+instance Disc.Sorting a => HasUnion (OM.OMSet a) where+  union = OM.union++instance Eq a => HasDifference (OM.OMSet a) where+  difference = OM.difference++instance Ord a => HasIntersection (OM.OMSet a) where+  intersection = OM.intersection++instance HasSingleton (OM.OMSet a) a where+  singleton = OM.singleton++instance HasEmpty (OM.OMSet a) where+  empty = OM.empty++instance HasSize (OM.OMSet a) where+  size = OM.size++instance Eq a => CanBeSubset (OM.OMSet a) where+  isSubsetOf = OM.isSubsetOf++instance Eq a => CanBeProperSubset (OM.OMSet a) where+  isProperSubsetOf = OM.isProperSubsetOf+++-- Data.Set.Unordered.Many+instance Eq a => HasUnion (UM.UMSet a) where+  union = UM.union++instance Eq a => HasDifference (UM.UMSet a) where+  difference = UM.difference++instance Eq a => HasIntersection (UM.UMSet a) where+  intersection = UM.intersection++instance HasSingleton (UM.UMSet a) a where+  singleton = UM.singleton++instance HasEmpty (UM.UMSet a) where+  empty = UM.empty++instance HasSize (UM.UMSet a) where+  size = UM.size++instance Eq a => CanBeSubset (UM.UMSet a) where+  isSubsetOf = UM.isSubsetOf++instance Eq a => CanBeProperSubset (UM.UMSet a) where+  isProperSubsetOf = UM.isProperSubsetOf+++-- Data.Set.Unordered.Unique+instance Eq a => HasUnion (UU.UUSet a) where+  union = UU.union++instance Eq a => HasDifference (UU.UUSet a) where+  difference = UU.difference++instance Eq a => HasIntersection (UU.UUSet a) where+  intersection = UU.intersection++instance HasSingleton (UU.UUSet a) a where+  singleton = UU.singleton++instance HasEmpty (UU.UUSet a) where+  empty = UU.empty++instance HasSize (UU.UUSet a) where+  size = UU.size++instance Eq a => CanBeSubset (UU.UUSet a) where+  isSubsetOf = UU.isSubsetOf++instance Eq a => CanBeProperSubset (UU.UUSet a) where+  isProperSubsetOf = UU.isProperSubsetOf+++-- Data.Set.Ordered.Unique.Finite+instance Ord a => HasUnion (OUF.FiniteSet a) where+  union = OUF.union++instance Ord a => HasDifference (OUF.FiniteSet a) where+  difference = OUF.difference++instance Ord a => HasIntersection (OUF.FiniteSet a) where+  intersection = OUF.intersection++instance Ord a => HasComplement (OUF.FiniteSet a) where+  complement = OUF.complement++instance HasSingletonWith (OUF.FiniteSet a) (Set.Set a) a where+  singletonWith = OUF.singleton++instance HasEmptyWith (OUF.FiniteSet a) (Set.Set a) where+  emptyWith = OUF.empty++instance HasTotalWith (OUF.FiniteSet a) (OUF.FiniteSet a) where+  totalWith (OUF.FiniteSet (t,_)) = OUF.FiniteSet (t,t)++instance HasSize (OUF.FiniteSet a) where+  size = OUF.size++instance Ord a => CanBeSubset (OUF.FiniteSet a) where+  isSubsetOf = OUF.isSubsetOf++instance Ord a => CanBeProperSubset (OUF.FiniteSet a) where+  isProperSubsetOf = OUF.isProperSubsetOf
+ src/Data/Set/Class/Types.hs view
@@ -0,0 +1,12 @@+{-# LANGUAGE+    GeneralizedNewtypeDeriving+  , StandaloneDeriving+  #-}++module Data.Set.Class.Types where++-- | These types are used for @Monoid@ and @Commutative@ instances for sets.++newtype Union a = Union {fromUnion :: a}++newtype Intersection a = Intersection {fromIntersection :: a}
+ src/Data/Set/Ordered/Many.hs view
@@ -0,0 +1,132 @@+{-# LANGUAGE+    GeneralizedNewtypeDeriving+  , DeriveFunctor+  #-}++module Data.Set.Ordered.Many where++import Data.Mergeable+import Data.List as List hiding (delete)+import Data.Discrimination as Disc+import Data.Maybe (fromJust, isJust, mapMaybe)+++-- | Ordered sets with duplicate elements.+newtype OMSet a = OMSet {unOMSet :: [a]}+  deriving (Functor)++instance Mergeable OMSet where+  mergeMap f (OMSet xs) = mergeMap f xs++-- * Operators++(\\) :: Eq a => OMSet a -> OMSet a -> OMSet a+(\\) = difference++-- * Query++-- | /O(1)/+null :: Eq a => OMSet a -> Bool+null (OMSet xs) = List.null xs++-- | /O(n)/+size :: OMSet a -> Int+size (OMSet xs) = List.length xs++-- | /O(n)/+member :: Eq a => a -> OMSet a -> Bool+member x (OMSet xs) = List.elem x xs++-- | /O(n)/+notMember :: Eq a => a -> OMSet a -> Bool+notMember x = not . member x++-- | /O(n)/+lookup :: Eq a => a -> OMSet a -> Maybe a+lookup x (OMSet xs) = lookup' x xs+  where+    lookup' _ [] = Nothing+    lookup' x (y:ys) | x == y    = Just y+                     | otherwise = lookup' x ys++-- | /O(n*m)/+isSubsetOf :: Eq a => OMSet a -> OMSet a -> Bool+isSubsetOf (OMSet xs) (OMSet ys) = foldr go True xs+  where+    go x b | List.elem x ys = b+           | otherwise      = False++-- | /O(n*(m^3))/+isProperSubsetOf :: Eq a => OMSet a -> OMSet a -> Bool+isProperSubsetOf (OMSet xs) (OMSet ys) = fst $ foldr go (True,ys) xs+  where+    go _ (False,soFar) = (False,soFar)+    go _ (_,[]) = (False,[])+    go x (b,soFar) = if List.elem x soFar+                     then (b,     List.filter (/= x) soFar)+                     else (False, soFar)++-- * Construction++-- | /O(1)/+empty :: OMSet a+empty = OMSet []++-- | /O(1)/+singleton :: a -> OMSet a+singleton x = OMSet [x]++-- | /O(n)/+insert :: Ord a => a -> OMSet a -> OMSet a+insert x (OMSet xs) = OMSet $ insert' x xs+  where+    insert' x [] = [x]+    insert' x (a:as) | x > a = a : insert' x as+                     | otherwise = x:a:as++-- | /O(n)/+delete :: Eq a => a -> OMSet a -> OMSet a+delete x (OMSet xs) = OMSet $ List.filter (== x) xs++-- * Combine++-- | /O(n+m)/+union :: Disc.Sorting a => OMSet a -> OMSet a -> OMSet a+union (OMSet xs) (OMSet ys) = OMSet $ Disc.sort (xs ++ ys) -- TODO: Use descrimonation++-- | /O(n*m)/+difference :: Eq a => OMSet a -> OMSet a -> OMSet a+difference (OMSet xs) (OMSet ys) = OMSet $ foldr go [] xs+ where+   go x soFar | List.elem x ys =   soFar+              | otherwise      = x:soFar++-- | /O(min(n,m))/ - Combines all elements of both+intersection :: Ord a => OMSet a -> OMSet a -> OMSet a+intersection (OMSet xs) (OMSet ys) = OMSet $ go xs ys+  where+    go [] _ = []+    go _ [] = []+    go (x:xs) (y:ys) | x < y = go (x:xs) ys+                     | x == y = x:x:go xs ys+                     | x > y = go xs (y:ys)++-- * Filter++-- | /O(n)/+filter :: (a -> Bool) -> OMSet a -> OMSet a+filter p (OMSet xs) = OMSet $ List.filter p xs++-- | /O(n)/+partition :: (a -> Bool) -> OMSet a -> (OMSet a, OMSet a)+partition p (OMSet xs) = let (l,r) = List.partition p xs in (OMSet l, OMSet r)++-- * Map++-- | /O(n)/+map :: (a -> b) -> OMSet a -> OMSet b+map f (OMSet xs) = OMSet $ List.map f xs++-- | /O(?)/+mapMaybe :: (a -> Maybe b) -> OMSet a -> OMSet b+mapMaybe f (OMSet xs) = OMSet $ Data.Maybe.mapMaybe f xs
+ src/Data/Set/Ordered/Unique.hs view
@@ -0,0 +1,9 @@+module Data.Set.Ordered.Unique+  ( module Set+  , OUSet+  ) where++import Data.Set as Set+++type OUSet = Set.Set
+ src/Data/Set/Unordered/Many.hs view
@@ -0,0 +1,135 @@+{-# LANGUAGE+    GeneralizedNewtypeDeriving+  , DeriveFunctor+  #-}++module Data.Set.Unordered.Many where++import Data.Mergeable+import Data.List as List hiding (delete)+import Data.Maybe (fromJust, isJust, mapMaybe)+++-- | Unordered sets with duplicate elements. The semantics for "unordering" is based on the idea+-- that we will not know what order the elements are in at any point, and we+-- are free to re-order elements in any way.+--+-- Most binary functions are algorithmically heavier on the right arguments.++-- | Pronounced "Unordered Many Set"+newtype UMSet a = UMSet {unUMSet :: [a]}+  deriving (Functor)++instance Mergeable UMSet where+  mergeMap f (UMSet xs) = mergeMap f xs++-- * Operators++(\\) :: Eq a => UMSet a -> UMSet a -> UMSet a+(\\) = difference++-- * Query++-- | /O(1)/+null :: Eq a => UMSet a -> Bool+null (UMSet xs) = List.null xs++-- | /O(n)/+size :: UMSet a -> Int+size (UMSet xs) = List.length xs++-- | /O(n)/+member :: Eq a => a -> UMSet a -> Bool+member x (UMSet xs) = List.elem x xs++-- | /O(n)/+notMember :: Eq a => a -> UMSet a -> Bool+notMember x = not . member x++-- | /O(n)/+lookup :: Eq a => a -> UMSet a -> Maybe a+lookup x (UMSet xs) = lookup' x xs+  where+    lookup' _ [] = Nothing+    lookup' x (y:ys) | x == y    = Just y+                     | otherwise = lookup' x ys++-- | /O(n*m)/+isSubsetOf :: Eq a => UMSet a -> UMSet a -> Bool+isSubsetOf (UMSet xs) (UMSet ys) = foldr go True xs+  where+    go x b | List.elem x ys = b+           | otherwise      = False++-- | /O(n*(m^3))/+isProperSubsetOf :: Eq a => UMSet a -> UMSet a -> Bool+isProperSubsetOf (UMSet xs) (UMSet ys) = fst $ foldr go (True,ys) xs+  where+    go _ (False,soFar) = (False,soFar)+    go _ (_,[]) = (False,[])+    go x (b,soFar) = if List.elem x soFar+                     then (b,     List.filter (/= x) soFar)+                     else (False, soFar)++-- * Construction++-- | /O(1)/+empty :: UMSet a+empty = UMSet []++-- | /O(1)/+singleton :: a -> UMSet a+singleton x = UMSet [x]++-- | /O(1)/+insert :: a -> UMSet a -> UMSet a+insert x (UMSet xs) = UMSet $ x:xs++-- | /O(n)/+delete :: Eq a => a -> UMSet a -> UMSet a+delete x (UMSet xs) = UMSet $ List.filter (== x) xs++-- * Combine++-- | /O(n)/+union :: Eq a => UMSet a -> UMSet a -> UMSet a+union (UMSet xs) (UMSet ys) = UMSet $ xs ++ ys++-- | /O(n*m)/+difference :: Eq a => UMSet a -> UMSet a -> UMSet a+difference (UMSet xs) (UMSet ys) = UMSet $ foldr go [] xs+  where+    go x soFar | List.elem x ys =   soFar+               | otherwise      = x:soFar++-- | /O(n*(m^4))/ - Combines all elements of both+intersection :: Eq a => UMSet a -> UMSet a -> UMSet a+intersection (UMSet xs) (UMSet ys) = UMSet $ fst $ foldr go ([],ys) xs+  where+    go :: Eq a => a -> ([a],[a]) -> ([a],[a])+    go x (soFar,whatsLeft) | List.elem x whatsLeft =+                               ( soFar ++ List.filter (== x) whatsLeft+                               , List.filter (/= x) whatsLeft )+                           | otherwise =+                               ( soFar+                               , whatsLeft )++-- * Filter++-- | /O(n)/+filter :: (a -> Bool) -> UMSet a -> UMSet a+filter p (UMSet xs) = UMSet $ List.filter p xs++-- | /O(n)/+partition :: (a -> Bool) -> UMSet a -> (UMSet a, UMSet a)+partition p (UMSet xs) = let (l,r) = List.partition p xs in (UMSet l, UMSet r)++-- * Map++-- | /O(n)/+map :: (a -> b) -> UMSet a -> UMSet b+map f (UMSet xs) = UMSet $ List.map f xs++-- | /O(?)/+mapMaybe :: (a -> Maybe b) -> UMSet a -> UMSet b+mapMaybe f (UMSet xs) = UMSet $ Data.Maybe.mapMaybe f xs
+ src/Data/Set/Unordered/Unique.hs view
@@ -0,0 +1,141 @@+{-# LANGUAGE+    GeneralizedNewtypeDeriving+  , DeriveFunctor+  #-}++-- | Unique, unordered sets. The semantics for "unordering" is based on the idea+-- that we will not know what order the elements are in at any point, and we+-- are free to re-order elements in any way.++module Data.Set.Unordered.Unique where++import Data.Mergeable+import Data.List as List+import Data.Maybe (fromJust, isJust, mapMaybe)+++-- | Pronounced "Unordered Unique Set"+newtype UUSet a = UUSet {unUUSet :: [a]}+  deriving (Functor)++instance Mergeable UUSet where+  mergeMap f (UUSet xs) = mergeMap f xs++-- * Operators++(\\) :: Eq a => UUSet a -> UUSet a -> UUSet a+(\\) = difference++-- * Query++-- | /O(1)/+null :: Eq a => UUSet a -> Bool+null (UUSet xs) = List.null xs++-- | /O(n)/+size :: UUSet a -> Int+size (UUSet xs) = List.length xs++-- | /O(n)/+member :: Eq a => a -> UUSet a -> Bool+member x (UUSet xs) = List.elem x xs++-- | /O(n)/+notMember :: Eq a => a -> UUSet a -> Bool+notMember x = not . member x++-- | /O(n)/+lookup :: Eq a => a -> UUSet a -> Maybe a+lookup x (UUSet xs) = lookup' x xs+  where+    lookup' _ [] = Nothing+    lookup' x (y:ys) | x == y    = Just y+                     | otherwise = lookup' x ys++-- | /O(n*m)/+isSubsetOf :: Eq a => UUSet a -> UUSet a -> Bool+isSubsetOf (UUSet xs) (UUSet ys) = foldr go True xs+  where+    go x b | List.elem x ys = b+           | otherwise      = False++-- | /O(n*(m^2))/+isProperSubsetOf :: Eq a => UUSet a -> UUSet a -> Bool+isProperSubsetOf (UUSet xs) (UUSet ys) = fst $ foldr go (True,ys) xs+  where+    go _ (False,xs) = (False,xs)+    go _ (_,[]) = (False,[])+    go x (b,soFar) = let midx = List.elemIndex x soFar in+      if isJust midx then (b,     deleteAt (fromJust midx) soFar)+                     else (False, soFar)++    deleteAt n xs = List.take n xs ++ List.drop (n+1) xs++-- * Construction++-- | /O(1)/+empty :: UUSet a+empty = UUSet []++-- | /O(1)/+singleton :: a -> UUSet a+singleton x = UUSet [x]++-- | /O(n)/+insert :: Eq a => a -> UUSet a -> UUSet a+insert x (UUSet xs) = UUSet $ insert' x xs+  where+    insert' x [] = [x]+    insert' x (y:ys) | x == y    = y:ys+                     | otherwise = y:insert' x ys++-- | /O(n)/+delete :: Eq a => a -> UUSet a -> UUSet a+delete x (UUSet xs) = UUSet $ delete' x xs+  where+    delete' x [] = []+    delete' x (y:ys) | x == y    =   ys+                     | otherwise = y:delete' x ys++-- * Combine++-- | /O(n*m)/+union :: Eq a => UUSet a -> UUSet a -> UUSet a+union (UUSet xs) (UUSet ys) = UUSet $ foldr go xs ys+  where+    go y soFar | List.elem y soFar =   soFar+               | otherwise         = y:soFar++-- | /O(n*m)/+difference :: Eq a => UUSet a -> UUSet a -> UUSet a+difference (UUSet xs) (UUSet ys) = UUSet $ foldr go [] xs+  where+    go x soFar | List.elem x ys =   soFar+               | otherwise      = x:soFar++-- | /O(n*m)/+intersection :: Eq a => UUSet a -> UUSet a -> UUSet a+intersection (UUSet xs) (UUSet ys) = UUSet $ foldr go [] xs+  where+    go x soFar | List.elem x ys = x:soFar+               | otherwise      =   soFar++-- * Filter++-- | /O(n)/+filter :: (a -> Bool) -> UUSet a -> UUSet a+filter p (UUSet xs) = UUSet $ List.filter p xs++-- | /O(n)/ - Guaranteed to be disjoint+partition :: (a -> Bool) -> UUSet a -> (UUSet a, UUSet a)+partition p (UUSet xs) = let (l,r) = List.partition p xs in (UUSet l, UUSet r)++-- * Map++-- | /O(n)/+map :: (a -> b) -> UUSet a -> UUSet b+map f (UUSet xs) = UUSet $ List.map f xs++-- | /O(?)/+mapMaybe :: (a -> Maybe b) -> UUSet a -> UUSet b+mapMaybe f (UUSet xs) = UUSet $ Data.Maybe.mapMaybe f xs
+ test/Spec.hs view
@@ -0,0 +1,13 @@+module Spec where++import Data.SetSpec++import Test.Tasty+++main :: IO ()+main = defaultMain tests++tests :: TestTree+tests = testGroup "Testing..."+  [spec]