WeakSets 0.3.0.0 → 0.4.0.0

raw patch · 6 files changed

+298/−116 lines, 6 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• WeakSets.cabal +5/−3
• src/Data/WeakSets/HomogeneousFunction.hs +235/−0
• src/Data/WeakSets/HomogeneousSet.hs +24/−99
• test/AllTests.hs +4/−2
• test/TestHomogeneousFunction.hs +30/−0
• test/TestHomogeneousSet.hs +0/−12

@@ -14,7 +14,7 @@ -- PVP summary:      +-+------- breaking API changes
 --                   | | +----- non-breaking API additions
 --                   | | | +--- code changes with no API change
-version:            0.3.0.0
+version:            0.4.0.0
 
 -- A short (one-line) description of the package.
 synopsis:
@@ -52,7 +52,9 @@ 
 library
     -- Modules exported by the library.
-    exposed-modules:  Data.WeakSets.HomogeneousSet, Math.WeakSets.PureSet
+    exposed-modules:    Data.WeakSets.HomogeneousSet,
+                        Math.WeakSets.PureSet,
+                        Data.WeakSets.HomogeneousFunction
 
     -- Modules included in this library but not exported.
     -- other-modules:
@@ -85,4 +87,4 @@     -- Test dependencies.
     build-depends:    base ^>=4.15.0.0, WeakSets
     
-    other-modules:    TestHomogeneousSet, TestPureSet
+    other-modules:    TestHomogeneousSet, TestPureSet, TestHomogeneousFunction

@@ -0,0 +1,235 @@+{-| Module  : WeakSets
+Description : Homogeneous functions are functions between `HomogeneousSet`s. They are more flexible than Data.Map because they do not require the keys to be orderable.
+Copyright   : Guillaume Sabbagh 2022
+License     : LGPL-3.0-or-later
+Maintainer  : guillaumesabbagh@protonmail.com
+Stability   : experimental
+Portability : portable
+
+Homogeneous functions are functions between `HomogeneousSet`s.
+
+They are more flexible than Data.Map because they do not require the keys to be orderable.
+
+The datatype only assumes its keys are equatable, it is therefore slower than the Data.Map datatype.
+
+We use this datatype because most of the datatypes we care about are not orderable.
+
+Inline functions related to homogeneous functions are written between pipes @|@.
+
+Function names should not collide with Prelude but may collide with Data.Map.
+-}
+
+module Data.WeakSets.HomogeneousFunction
+(
+    -- * Function datatype and smart constructor
+    AssociationList(..),
+    Function, -- abstract type, the smart constructor is `function`
+    function, -- the smart constructor for `Function`
+    -- * Function related functions
+    domain,
+    image,
+    idFromSet,
+    (|.|),
+    -- * Query
+    size,
+    member,
+    notMember,
+    (|?|),
+    (|!|),
+    findWithDefault,
+    -- * Construction
+    -- ** Insertion
+    insert,
+    insertWith,
+    insertWithKey,
+    -- ** Delete/Update 
+    delete,
+    adjust,
+    adjustWithKey,
+    alter,
+    -- * Combine
+    -- ** Union
+    union,
+    -- * Traversal
+    mapKeys,
+    -- * Conversion 
+    keys,
+    elems,
+    functionToSet,
+    memorizeFunction,
+)
+where
+    import              Data.WeakSets.HomogeneousSet
+    
+    -- | A function of homogeneous sets. It is a set of pairs (key,value) such that their should only be one pair with a given key.
+    --
+    -- It is an abstract type, the smart constructor is `function`.
+    data Function k v = Function (Set (k,v)) deriving (Eq)
+    
+    instance (Show k, Show v) => Show (Function k v) where
+        show (Function al) = "(function "++show al++")"
+    
+    instance Semigroup (Function k v) where
+        (Function al1) <> (Function al2) = Function $ al1 <> al2
+    
+    instance Monoid (Function k v) where
+        mempty = Function (set [])
+        
+    instance Foldable (Function k) where
+        foldr f d (Function al) = foldr (\(k,v) -> f v) d al
+
+    instance Functor (Function k) where
+        fmap f (Function al) = Function $ (\(k,v) -> (k,f v)) <$> al
+    
+    -- | An association list is a list of pairs (key,value).
+    type AssociationList k v = [(k,v)]
+    
+    -- | /O(1)/. The smart constructor of functions. This is the only way of instantiating a `Function`.
+    --
+    -- Takes an association list and returns a function which maps to each key the value associated.
+    --
+    -- If several pairs have the same keys, they are kept until the user wants an association list back.
+    function :: AssociationList k v -> Function k v
+    function al = Function $ set $ al
+    
+    -- | /O(n)/. Return the domain of a function.
+    domain :: Function k v -> Set k
+    domain (Function al) = fst <$> al
+    
+    -- | /O(n)/. Return the image of a function. The image of a function is the set of values which are reachable by applying the function.
+    image :: Function k v -> Set v
+    image (Function al) = snd <$> al
+    
+    -- | /O(n)/. Return the identity function associated to a `Set`.
+    idFromSet :: Set a -> Function a a
+    idFromSet set = Function $ (\x -> (x,x)) <$> set
+    
+    -- | Compose two functions. If the two functions are not composable, strips the functions until they can compose.
+    (|.|) :: (Eq a, Eq b) => Function b c -> Function a b -> Function a c
+    (|.|) f2 f1 = Function $ set [(k,(f2 |!| (f1 |!| k))) | k <- (setToList.domain $ f1), f1 |!| k `isIn` (domain f2)]
+        
+{--------------------------------------------------------------------
+  Query
+--------------------------------------------------------------------}
+    
+    -- | /O(n)/. The number of entries in the function.
+    size :: (Eq k) => Function k v -> Int
+    size f = length.setToList.keys $ f
+    
+    -- | /O(n)/. Return wether a key is in the function domain or not.
+    member :: (Eq k) => Function k v -> k -> Bool
+    member f k = k `isIn` (domain f)
+    
+    -- | /O(n)/. Negation of member.
+    notMember :: (Eq k) => Function k v -> k -> Bool
+    notMember f k = not $ member f k
+    
+    -- | /O(n)/. Apply a function to a given value. If the function is not defined on the given value returns `Nothing`, otherwise returns `Just` the image.
+    --
+    -- This function is like `lookup` in Data.Map for function (the order of the argument are reversed though).
+    (|?|) :: (Eq k) => Function k v -> k -> Maybe v
+    (|?|) (Function al) key = setToMaybe.catMaybesToSet $ (\(k,v) -> if k == key then Just v else Nothing) <$> al
+    
+    -- | /O(n)/. Unsafe version of `(|?|)`.
+    --
+    -- This function is like `(!)` in Data.Map for function.
+    (|!|) :: (Eq k) => Function k v -> k -> v
+    (|!|) f key
+        | null safeResult = error "Function applied on a value not in the domain."
+        | otherwise = result
+        where
+            safeResult = f |?| key
+            Just result = safeResult
+    
+    -- | /O(n)/. Apply a function to a given value, if the value is in the domain returns the image, otherwise return a default value.
+    --
+    -- This function is like `findWithDefault` in Data.Map for function (the order of the argument are reversed though).
+    findWithDefault :: (Eq k) => Function k v -> v -> k -> v
+    findWithDefault f d key
+        | null safeResult = d
+        | otherwise = result
+        where
+            safeResult = f |?| key
+            Just result = safeResult
+            
+{--------------------------------------------------------------------
+  Insertion
+--------------------------------------------------------------------}
+
+    -- | O(1). Insert a new key and value in the function. If the key is already present in the function, the associated value is replaced with the supplied value. insert is equivalent to insertWith const. 
+    insert :: k -> v -> Function k v -> Function k v
+    insert k v (Function al) = Function $ (set [(k,v)]) ||| al
+    
+    -- | O(n). Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key, f new_value old_value). 
+    insertWith :: (Eq k) => (v -> v -> v) -> k -> v -> Function k v -> Function k v
+    insertWith comb k v f
+        | null prev = insert k v f
+        | otherwise = insert k (comb v prev_value) f
+        where
+            prev = f |?| k
+            Just prev_value = prev
+
+    -- | O(n). Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to insertWithKey. 
+    insertWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Function k a -> Function k a
+    insertWithKey comb k v f
+        | null prev = insert k v f
+        | otherwise = insert k (comb k v prev_value) f
+        where
+            prev = f |?| k
+            Just prev_value = prev
+
+{--------------------------------------------------------------------
+  Conversion
+--------------------------------------------------------------------}
+
+    -- | /O(n)/. Transform a function back into its underlying association list.
+    functionToSet :: (Eq k) => Function k v -> Set (k,v)
+    functionToSet (Function al) = nubSetBy (\x y -> (fst x) == (fst y)) al
+
+    -- | /O(n)/. Alias of domain.
+    keys :: Function k v -> Set k
+    keys = domain
+    
+    -- | /O(n)/. Alias of image.
+    elems :: Function k v -> Set v
+    elems = image
+
+    -- | /O(n)/. Memorize a Haskell function on a given finite domain.
+    memorizeFunction :: (k -> v) -> Set k -> Function k v
+    memorizeFunction f xs = Function $ (\k -> (k, f k)) <$> xs
+    
+{--------------------------------------------------------------------
+  Delete/Update 
+--------------------------------------------------------------------}
+    -- | O(n). Delete a key and its value from the function. When the key is not a member of the function, the original function is returned. 
+    delete :: Eq k => k -> Function k a -> Function k a
+    delete key (Function al) = Function $ filterSet (\(k,v) -> key /= k) al
+    
+    -- | O(n). Update a value at a specific key with the result of the provided function. When the key is not a member of the function, the original function is returned. 
+    adjust :: Eq k => (a -> a) -> k -> Function k a -> Function k a
+    adjust func key (Function al) = Function $ (\(k,v) -> if key == k then (k, func v) else (k,v)) <$> al
+    
+    -- | O(n). Adjust a value at a specific key. When the key is not a member of the function, the original function is returned. 
+    adjustWithKey :: Eq k => (k -> a -> a) -> k -> Function k a -> Function k a
+    adjustWithKey func key (Function al) = Function $ (\(k,v) -> if key == k then (k, func k v) else (k,v)) <$> al
+    
+    -- | O(n). The expression (`alter` f k function) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a `Function`. In short : `lookup` k (`alter` f k m) = f (`lookup` k m). 
+    alter :: Eq k => (Maybe a -> Maybe a) -> k -> Function k a -> Function k a
+    alter func key f
+        | null lookupKey = insert key unpackedImageNothing f
+        | null result = delete key f
+        | otherwise = adjust (const unpackedResult) key f
+        where
+            lookupKey = f |?| key
+            result = func lookupKey
+            Just unpackedResult = result
+            Just unpackedImageNothing = func Nothing
+            
+    -- | /O(n)/. Map a function over the keys of a function.
+    mapKeys :: (k1 -> k2) -> Function k1 v -> Function k2 v
+    mapKeys f (Function al) = Function $ (\(k,v) -> (f k,v)) <$> al
+    
+    
+    -- | /O(n)/. The expression (`union` t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered. 
+    union :: Eq k => Function k a -> Function k a -> Function k a
+    union (Function al1) (Function al2) = Function $ al1 ||| al2

@@ -16,7 +16,7 @@ 
 Inline functions related to homogeneous sets are written between pipes @|@.
 
-Function names should not collide with Prelude but should collide with Data.Set.
+Function names should not collide with Prelude but may collide with Data.Set.
 -}
 
 module Data.WeakSets.HomogeneousSet
@@ -37,24 +37,12 @@     (|^|),
     powerSet,
     filterSet,
+    nubSetBy,
     -- * Functions to work with `Maybe`
     setToMaybe,
     maybeToSet,
     catMaybesToSet,
     mapMaybeToSet,
-    -- * Function datatype and smart constructor
-    AssociationList(..),
-    Function, -- abstract type, the smart constructor is `function`
-    function, -- the smart constructor for `Function`
-    -- * Function related functions
-    functionToSet,
-    domain,
-    image,
-    (|$|),
-    (|!|),
-    findWithDefault,
-    (|.|),
-    memorizeFunction,
 )
 where
     import              Data.List               (intercalate, nub, nubBy, intersect, union, (\\), subsequences)
@@ -67,7 +55,7 @@     -- To force these constraints, the `Set` constructor is abstract and is not exported. The only way to construct a set is to use the smart constructor `set` which ensures the previous conditions.
     data Set a = Set [a]
     
-    -- | The smart constructor of sets. This is the only way of instantiating a `Set`.
+    -- | /O(1)/. The smart constructor of sets. This is the only way of instantiating a `Set`.
     --
     -- If several elements are equal, they are kept until the user wants a list back.
     set :: [a] -> Set a
@@ -76,7 +64,7 @@     instance (Show a) => Show (Set a) where
         show (Set xs) = "(set "++show xs++")"
     
-    -- | Return a boolean indicating if a `Set` is included in another one.
+    -- | /O(n^2)/. Return a boolean indicating if a `Set` is included in another one.
     isIncludedIn :: (Eq a) => Set a -> Set a -> Bool
     (Set []) `isIncludedIn` _ = True
     (Set (x:xs)) `isIncludedIn` (Set ys)
@@ -86,10 +74,10 @@     instance (Eq a) => Eq (Set a) where
         x == y = x `isIncludedIn` y && y `isIncludedIn` x
         
-    instance (Eq a) => Semigroup (Set a) where
+    instance Semigroup (Set a) where
         (Set xs) <> (Set ys) = set $ xs <> ys
         
-    instance (Eq a) => Monoid (Set a) where
+    instance Monoid (Set a) where
         mempty = Set []
     
     instance Foldable Set where
@@ -105,35 +93,35 @@     instance Monad Set where
         (>>=) (Set xs) f = Set $ xs >>= (unsafeSetToList.f)
     
-    -- | Transform a `Set` back into a list, the list returned does not have duplicate elements, the order of the original list holds.
+    -- | /O(n)/. Transform a `Set` back into a list, the list returned does not have duplicate elements, the order of the original list holds.
     setToList :: (Eq a) => Set a -> [a]
     setToList (Set xs) = nub xs
     
-    -- | Gives the underlying list of a set without removing duplicates, this function is not exported.
+    -- | /O(1)/. Gives the underlying list of a set without removing duplicates, this function is not exported.
     unsafeSetToList :: Set a -> [a]
     unsafeSetToList (Set xs) = xs
     
-    -- | Size of a set.
+    -- | /O(n)/. Size of a set.
     cardinal :: (Eq a) => Set a -> Int
     cardinal = length.setToList
     
-    -- | Return wether an element is in a set.
+    -- | /O(n)/. Return wether an element is in a set.
     isIn :: (Eq a) => a -> Set a -> Bool
     isIn x = (elem x).unsafeSetToList
     
-    -- | Return the intersection of two sets.
+    -- | /O(n*m)/. Return the intersection of two sets.
     (|&|) :: (Eq a) => Set a -> Set a -> Set a
     (|&|) (Set xs) (Set ys) = Set $ xs `intersect` ys
     
-    -- | Return the union of two sets.
+    -- | /O(n)/. Return the union of two sets.
     (|||) ::  Set a -> Set a -> Set a
     (|||) (Set xs) (Set ys) = Set $ xs ++ ys
     
-    -- | Return the cartesian product of two sets.
+    -- | /O(n*m)/. Return the cartesian product of two sets.
     (|*|) ::  Set a -> Set b -> Set (a,b)
     (|*|) (Set xs) (Set ys) = Set $ [(x,y) | x <- xs, y <- ys]
     
-    -- | Return the disjoint union of two sets.
+    -- | /O(n)/. Return the disjoint union of two sets.
     (|+|) :: Set a -> Set b -> Set (Either a b)
     (|+|) (Set xs) (Set ys) = Set $ [Left x | x <- xs] ++ [Right y | y <- ys]
     
@@ -142,7 +130,7 @@     (|^|) _ 0 = Set [[]]
     (|^|) s n = (:) <$> s <*> (s |^| (n-1))
     
-    -- | Return the difference of two sets.
+    -- | /O(n*m)/. Return the difference of two sets.
     (|-|) :: (Eq a) => Set a -> Set a -> Set a
     (|-|) (Set xs) (Set ys) = Set $ xs \\ ys
     
@@ -150,89 +138,26 @@     powerSet :: Set a -> Set (Set a)
     powerSet (Set xs) = Set $ Set <$> subsequences xs
     
-    -- | Filter a set according to a condition.
+    -- | /O(n)/. Filter a set according to a condition.
     filterSet :: (a -> Bool) -> Set a -> Set a
     filterSet f (Set xs) = Set $ filter f xs
     
-    -- | Set version of listToMaybe.
+    -- | /O(1)/. Set version of listToMaybe.
     setToMaybe :: Set a -> Maybe a
     setToMaybe = listToMaybe.unsafeSetToList
     
-    -- | Set version of maybeToList.
+    -- | /O(1)/. Set version of maybeToList.
     maybeToSet :: Maybe a -> Set a
     maybeToSet x = Set $ maybeToList x
     
-    -- | Set version of catMaybes.
+    -- | /O(n)/. Set version of catMaybes.
     catMaybesToSet :: Set (Maybe a) -> Set a
     catMaybesToSet = set.catMaybes.unsafeSetToList
     
-    -- | Set version of mapMaybe.
+    -- | /O(n)/. Set version of mapMaybe.
     mapMaybeToSet :: (a -> Maybe b) -> Set a -> Set b
     mapMaybeToSet f = set.(mapMaybe f).unsafeSetToList
-    
-    -- | A function of homogeneous sets. It is a set of pairs (key,value) such that their should only be one pair with a given key.
-    --
-    -- It is an abstract type, the smart constructor is `function`.
-    data Function a b = Function (Set (a,b)) deriving (Eq)
-    
-    instance (Show a, Show b) => Show (Function a b) where
-        show (Function al) = "(function "++show al++")"
-    
-    -- | An association list is a list of pairs (key,value).
-    type AssociationList a b = [(a,b)]
-    
-    -- | The smart constructor of functions. This is the only way of instantiating a `Function`.
-    --
-    -- Takes an association list and returns a function which maps to each key the value associated.
-    --
-    -- If several pairs have the same keys, they are kept until the user wants an association list back.
-    function :: AssociationList a b -> Function a b
-    function al = Function $ Set $ al
-    
-    -- | Transform a function back into its underlying association list.
-    functionToSet :: (Eq a) => Function a b -> Set (a,b)
-    functionToSet (Function (Set al)) = Set $ nubBy (\x y -> (fst x) == (fst y)) al
-    
-    -- | Return the domain of a function.
-    domain :: Function a b -> Set a
-    domain (Function al) = fst <$> al
-    
-    -- | Return the image of a function. The image of a function is the set of values which are reachable by applying the function.
-    image :: Function a b -> Set b
-    image (Function al) = snd <$> al
-        
-    -- | Apply a function to a given value. If the function is not defined on the given value returns `Nothing`, otherwise returns `Just` the image.
-    --
-    -- This function is like `lookup` in Data.Map for function (the order of the argument are reversed though).
-    (|$|) :: (Eq a) => Function a b -> a -> Maybe b
-    (|$|) (Function (Set [])) _ = Nothing
-    (|$|) (Function (Set ((k,v):xs))) x
-        | x == k = Just v
-        | otherwise = (Function (Set xs)) |$| x
-    
-    -- | Unsafe version of `(|$|)`.
-    --
-    -- This function is like `(!)` in Data.Map for function.
-    (|!|) :: (Eq a) => Function a b -> a -> b
-    (|!|) (Function (Set [])) _ = error "Function applied on a value not in the domain."
-    (|!|) (Function (Set ((k,v):xs))) x
-        | x == k = v
-        | otherwise = (Function (Set xs)) |!| x
-    
-    -- | Apply a function to a given value, if the value is in the domain returns the image, otherwise return a default value.
-    --
-    -- This function is like `findWithDefault` in Data.Map for function (the order of the argument are reversed though).
-    findWithDefault :: (Eq a) => Function a b -> b -> a -> b
-    findWithDefault (Function (Set [])) d _ = d
-    findWithDefault (Function (Set ((k,v):xs))) d x
-        | x == k = v
-        | otherwise = findWithDefault (Function (Set xs)) d x
-   
-    -- | Compose two functions. If the two functions are not composable, strips the functions until they can compose.
-    (|.|) :: (Eq a, Eq b) => Function b c -> Function a b -> Function a c
-    (|.|) f2 f1 = Function $ Set [(k,(f2 |!| (f1 |!| k))) | k <- (setToList.domain $ f1), f1 |!| k `isIn` (domain f2)]
-    
-    -- | Memorize a Haskell function on a given finite domain.
-    memorizeFunction :: (a -> b) -> Set a -> Function a b
-    memorizeFunction f (Set xs) = Function $ Set [(k, f k) | k <- xs]
-    +
+    -- | /O(n)/. Remove duplicates in the set using your own equality function.
+    nubSetBy :: (a -> a -> Bool) -> Set a -> Set a
+    nubSetBy f (Set xs) = Set $ nubBy f xs

@@ -1,10 +1,12 @@ module Main (main) where
-    import qualified TestHomogeneousSet as HSET
-    import qualified TestPureSet as PSET
+    import qualified TestHomogeneousSet         as HSET
+    import qualified TestHomogeneousFunction    as HFUNCT
+    import qualified TestPureSet                as PSET
 
     main :: IO ()
     main = do
         putStrLn "Beginning of the test."
         HSET.main
+        HFUNCT.main
         PSET.main
         putStrLn "End of the tests."

@@ -0,0 +1,30 @@+module TestHomogeneousFunction where
+    import Data.WeakSets.HomogeneousSet
+    import Data.WeakSets.HomogeneousFunction
+    
+    -- | Tests all functions related to homogeneous sets.
+    main :: IO ()
+    main = do
+            putStrLn "Beginning of TestHomogeneousSet"
+            let s1 = set [1,2,3] 
+            let s2 = set [3,4,5] 
+            let f = function $ zip (setToList s1) (setToList s2)
+            let g = function $ zip (setToList s2) (setToList s1)
+            putStrLn $ show $ f
+            putStrLn $ show $ g
+            putStrLn $ show $ functionToSet $ f
+            putStrLn $ show $ domain $ f
+            putStrLn $ show $ image $ f
+            putStrLn $ show $ f |?| 1
+            putStrLn $ show $ f |!| 1
+            putStrLn $ show $ f |.| g
+            putStrLn $ show $ g |.| f
+            putStrLn $ show $ memorizeFunction (*3) (set [1..10])
+            putStrLn $ show $ idFromSet (set [1..10])
+            putStrLn $ show $ size (idFromSet (set [1..10]))
+            putStrLn $ show $ delete 3 (idFromSet (set [1..10]))
+            putStrLn $ show $ adjust (+1) 3 (idFromSet (set [1..10]))
+            putStrLn $ show $ adjust (+1) 13 (idFromSet (set [1..10]))
+            putStrLn $ show $ union (idFromSet (set [1..10])) (idFromSet (set [5..15])) 
+            putStrLn "End of TestHomogeneousSet"
+    

@@ -22,17 +22,5 @@             putStrLn $ show $ s1 |-| s2
             putStrLn $ show $ s1 |^| 3
             putStrLn $ show $ powerSet s1
-            let f = function $ zip (setToList s1) (setToList s2)
-            let g = function $ zip (setToList s2) (setToList s1)
-            putStrLn $ show $ f
-            putStrLn $ show $ g
-            putStrLn $ show $ functionToSet $ f
-            putStrLn $ show $ domain $ f
-            putStrLn $ show $ image $ f
-            putStrLn $ show $ f |$| 1
-            putStrLn $ show $ f |!| 1
-            putStrLn $ show $ f |.| g
-            putStrLn $ show $ g |.| f
-            putStrLn $ show $ memorizeFunction (*3) (set [1..10])
             putStrLn "End of TestHomogeneousSet"