WeakSets

This is a Haskell package which defines sets and maps in a more general way than Data.Set and Data.Map of the containers package.

This package answers three problems :

• how to make sets of types which do not implement the Ord typeclass (which is required by Data.Set), this problem is solved by Data.WeakSet;
• how to make maps of types which do not implement the Ord typeclass, this problem is solved by Data.WeakMap;
• how to make arbitrarily nested sets as set theory allows. This problem is resolved thanks to Math.PureSet.

Data.WeakSet and Data.WeakMap are (almost) backward compatible with Data.Set and Data.Map. Therefore you can replace your imports of Data.Set to Data.WeakSet and Data.Map.Strict to Data.WeakMap safely. There a a few functions which require to add an Eq typeclass as a requirement. Some functions are not implemented as they really need the Ord typeclass, if you use them you should use Data.Set or Data.Map.

General info

A WeakSet is a list where duplicates elements and the order of elements are disregarded. Its stronger counterpart is Data.Set. Most of the functions related to WeakSet require the Eq typeclass.

A WeakMap is an association list where duplicates entries and the order of pairs are disregarded. Its stronger counterpart is Data.Map. Most of the functions related to WeakMap require the Eq typeclass.

A PureSet is a tree-like structure where duplicate branches and the order of branches is disregarded.

Installation

cabal install WeakSets

Usage

Example usage of weak sets :

ghci> import Data.WeakSet.Safe
ghci> data Foo = Foo Int Char deriving (Eq, Show) -- an arbitrary type which is not required to implement Ord typeclass
ghci> s1 = set [Foo 3 'a', Foo 2 'c', Foo 3 'a']
ghci> s2 = set [Foo 2 'c', Foo 3 'a']
ghci> s1 == s2
True
ghci> s3 = set [Foo 2 'c', Foo 3 'a']
ghci> s4 = s1 ||| s3
ghci> s4
(set [Foo 3 'a',Foo 2 'c',Foo 3 'a',Foo 2 'c',Foo 3 'a'])
ghci> cardinal s4
2

Example usage of weak maps :

ghci> import Data.WeakMap.Safe
ghci> data Foo = Foo Int Char deriving (Eq) -- an arbitrary type which is not required to implement Ord typeclass
ghci> m1 = weakMap [(Foo 3 'a',1), (Foo 2 'c',5), (Foo 3 'a',3)]
ghci> m1 |!| (Foo 2 'c')
5

Example usage of pure sets :

ghci> import PureSet
ghci> numberToSet 3
(pureSet [(pureSet []),(pureSet [(pureSet [])]),(pureSet [(pureSet []),(pureSet [(pureSet [])])])])
ghci> putStrLn.prettify $ numberToSet 3
{{}, {{}}, {{}, {{}}}}

Contribution

Any input is appreciated ! Send an email for any remark or question. The git repository : https://gitlab.utc.fr/gsabbagh/sets