1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

-----------------------------------------------------------------------------
--- An efficient implementation of set based on finite maps.
-----------------------------------------------------------------------------

module Data.Set
  ( Set, null, size, fromList, empty, singleton, insert, member, delete
  , deleteAll, union, toList, difference
  ) where

import qualified Data.Map as Map

-------------------------------------------------------------------------
--                                                                      -
--   FiniteSets --- a thin veneer                                       -
--                                                                      -
-------------------------------------------------------------------------

--- The type of sets of elements.
type Set key = Map.Map key ()

--- Returns an empty set.
empty :: Set key
empty = Map.empty

--- Construct a set with only a single element.
singleton :: key -> Set key
singleton x = Map.singleton x ()

--- Transforms a list into a set of its elements.
fromList :: Ord key => [key] -> Set key
fromList xs = Map.fromList [ (x, ()) | x <- xs]

--- Test for an empty set.
null :: Set key -> Bool
null = Map.null

--- Inserts an element into a set if it is not already there.
insert :: Ord key => key -> Set key -> Set key
insert k s = Map.insert k () s

--- Deletes an element from a set.
delete :: Ord key => key -> Set key -> Set key
delete k s = Map.delete k s

--- Deletes a list of elements from a set.
deleteAll :: Ord key => [key] -> Set key -> Set key
deleteAll ks s = Map.deleteAll ks s

--- Computes the size of two sets.
size :: Set key -> Int
size = Map.size

--- Returns `True` if an element is contained in a set.
--- @param e - an element to be checked for containment
--- @param s - a set
--- @return `True` if `e` is contained in `s`
member :: Ord key => key -> Set key -> Bool
member = Map.member

--- Computes the difference of two sets.
difference :: Ord key => Set key -> Set key -> Set key
difference = Map.difference

--- Transforms a set into an ordered list of its elements.
toList :: Set key -> [key]
toList = Map.keys

--- Computes the union of two sets.
union :: Ord key => Set key -> Set key -> Set key
union = Map.union