Safe Haskell | Trustworthy |
---|---|
Language | Haskell2010 |
The Word8Set
type represents a set of elements of type Word8
.
The interface of this module mimics the Data.Set and/or Data.IntSet module interfaces from @containers package.
These module is intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
import Data.Word8Set (Word8Set) import qualified Data.Word8Set as W8S
Implementation
The implementation is based on Word256
type. Word8Set
is 256 bits.
Synopsis
- data Word8Set
- type Key = Word8
- empty :: Word8Set
- full :: Word8Set
- singleton :: Key -> Word8Set
- range :: Key -> Key -> Word8Set
- insert :: Key -> Word8Set -> Word8Set
- delete :: Key -> Word8Set -> Word8Set
- alterF :: Functor f => (Bool -> f Bool) -> Key -> Word8Set -> f Word8Set
- member :: Key -> Word8Set -> Bool
- notMember :: Key -> Word8Set -> Bool
- lookupLT :: Key -> Word8Set -> Maybe Key
- lookupGT :: Key -> Word8Set -> Maybe Key
- lookupLE :: Key -> Word8Set -> Maybe Key
- lookupGE :: Key -> Word8Set -> Maybe Key
- null :: Word8Set -> Bool
- isFull :: Word8Set -> Bool
- isSingleton :: Word8Set -> Maybe Key
- isRange :: Word8Set -> Maybe (Key, Key)
- size :: Word8Set -> Int
- isSubsetOf :: Word8Set -> Word8Set -> Bool
- isProperSubsetOf :: Word8Set -> Word8Set -> Bool
- disjoint :: Word8Set -> Word8Set -> Bool
- union :: Word8Set -> Word8Set -> Word8Set
- unions :: Foldable f => f Word8Set -> Word8Set
- difference :: Word8Set -> Word8Set -> Word8Set
- symmetricDifference :: Word8Set -> Word8Set -> Word8Set
- (\\) :: Word8Set -> Word8Set -> Word8Set
- intersection :: Word8Set -> Word8Set -> Word8Set
- complement :: Word8Set -> Word8Set
- filter :: (Key -> Bool) -> Word8Set -> Word8Set
- partition :: (Key -> Bool) -> Word8Set -> (Word8Set, Word8Set)
- map :: (Key -> Key) -> Word8Set -> Word8Set
- foldr :: (Key -> b -> b) -> b -> Word8Set -> b
- foldl :: (a -> Key -> a) -> a -> Word8Set -> a
- foldr' :: (Key -> b -> b) -> b -> Word8Set -> b
- foldl' :: (a -> Key -> a) -> a -> Word8Set -> a
- findMin :: Word8Set -> Word8
- findMax :: Word8Set -> Word8
- deleteMin :: Word8Set -> Word8Set
- deleteMax :: Word8Set -> Word8Set
- maxView :: Word8Set -> Maybe (Key, Word8Set)
- minView :: Word8Set -> Maybe (Key, Word8Set)
- elems :: Word8Set -> [Key]
- toList :: Word8Set -> [Key]
- fromList :: [Key] -> Word8Set
- fromFoldable :: Foldable f => f Key -> Word8Set
- toWord256 :: Word8Set -> Word256
- fromWord256 :: Word256 -> Word8Set
- toASCII :: Word8Set -> String
- fromASCII :: String -> Word8Set
Set type
Instances
Arbitrary Word8Set Source # | |
CoArbitrary Word8Set Source # | |
Defined in Data.Word8Set coarbitrary :: Word8Set -> Gen b -> Gen b # | |
Function Word8Set Source # | |
IsString Word8Set Source # |
Since: 0.1.1 |
Defined in Data.Word8Set fromString :: String -> Word8Set # | |
Monoid Word8Set Source # | |
Semigroup Word8Set Source # | |
IsList Word8Set Source # | |
Show Word8Set Source # | |
NFData Word8Set Source # | |
Defined in Data.Word8Set | |
Eq Word8Set Source # | |
Ord Word8Set Source # | |
Defined in Data.Word8Set | |
Heyting Word8Set Source # | Since: 0.1.1 |
BoundedJoinSemiLattice Word8Set Source # | |
Defined in Data.Word8Set | |
BoundedMeetSemiLattice Word8Set Source # | |
Defined in Data.Word8Set | |
Lattice Word8Set Source # | |
PartialOrd Word8Set Source # |
Since: 0.1.1 |
Lift Word8Set Source # | |
type Item Word8Set Source # | |
Defined in Data.Word8Set |
Construction
range :: Key -> Key -> Word8Set Source #
A set of inclusive range.
>>>
range 10 20
fromList [10,11,12,13,14,15,16,17,18,19,20]
Insertion
insert :: Key -> Word8Set -> Word8Set Source #
Add a value to the set.
>>>
insert 10 (range 15 20)
fromList [10,15,16,17,18,19,20]
>>>
insert 10 (range 10 15)
fromList [10,11,12,13,14,15]
Deletion
delete :: Key -> Word8Set -> Word8Set Source #
Delete a value in the set. Returns the original set when the value was not present.
>>>
delete 10 (range 5 15)
fromList [5,6,7,8,9,11,12,13,14,15]
>>>
delete 10 (range 1 10)
fromList [1,2,3,4,5,6,7,8,9]
Generalized insertion/deletion
alterF :: Functor f => (Bool -> f Bool) -> Key -> Word8Set -> f Word8Set Source #
Generalized insetion deletion.
Query
member :: Key -> Word8Set -> Bool Source #
Is the value a member of the set?
>>>
member 5 (range 10 20)
False
>>>
member 15 (range 10 20)
True
notMember :: Key -> Word8Set -> Bool Source #
Is the element not in the set?
>>>
notMember 5 (range 10 20)
True
>>>
notMember 15 (range 10 20)
False
lookupLT :: Key -> Word8Set -> Maybe Key Source #
Find largest element smaller than the given one.
>>>
lookupLT 3 (fromList [3, 5])
Nothing>>>
lookupLT 5 (fromList [3, 5])
Just 3
>>>
lookupLT 0 full
Nothing
lookupGT :: Key -> Word8Set -> Maybe Key Source #
Find smallest element greater than the given one.
>>>
lookupGT 4 (fromList [3, 5])
Just 5
>>>
lookupGT 5 (fromList [3, 5])
Nothing
>>>
lookupGT 255 full
Nothing
lookupLE :: Key -> Word8Set -> Maybe Key Source #
Find largest element smaller or equal to the given one.
>>>
lookupLE 2 (fromList [3, 5])
Nothing
>>>
lookupLE 4 (fromList [3, 5])
Just 3
>>>
lookupLE 5 (fromList [3, 5])
Just 5
lookupGE :: Key -> Word8Set -> Maybe Key Source #
Find smallest element greater or equal to the given one.
>>>
lookupGE 3 (fromList [3, 5])
Just 3
>>>
lookupGE 4 (fromList [3, 5])
Just 5
>>>
lookupGE 6 (fromList [3, 5])
Nothing
isFull :: Word8Set -> Bool Source #
Is the set full?
>>>
isFull full
True
>>>
isFull (range 1 255)
False
isSingleton :: Word8Set -> Maybe Key Source #
Is set singleton?
>>>
isSingleton empty
Nothing
>>>
isSingleton full
Nothing
>>>
isSingleton (singleton 5)
Just 5
>>>
isSingleton (fromList [3, 5])
Nothing
isRange :: Word8Set -> Maybe (Key, Key) Source #
Is set of the form
?range
l r
>>>
isRange empty
Nothing
>>>
isRange full
Just (0,255)
>>>
isRange (singleton 5)
Just (5,5)
>>>
isRange (range 10 20)
Just (10,20)
>>>
isRange (fromList [3, 5])
Nothing
size :: Word8Set -> Int Source #
Cardinality of the set.
>>>
size empty
0
>>>
size (union (range 10 20) (range 30 40))
22
isSubsetOf :: Word8Set -> Word8Set -> Bool Source #
Is this a subset? (s1
tells whether s1 is a subset of s2.isSubsetOf
s2)
>>>
isSubsetOf (range 10 20) (range 5 25)
True
>>>
isSubsetOf (range 10 20) (range 10 20)
True
>>>
isSubsetOf (range 5 25) (range 10 20)
False
isProperSubsetOf :: Word8Set -> Word8Set -> Bool Source #
Is this a proper subset? Is this a proper subset? (ie. a subset but not equal).
>>>
isProperSubsetOf (range 10 20) (range 5 25)
True
>>>
isProperSubsetOf (range 10 20) (range 10 20)
False
>>>
isProperSubsetOf (range 5 25) (range 10 20)
False
disjoint :: Word8Set -> Word8Set -> Bool Source #
Check whether two sets are disjoint (i.e. their intersection is empty).
>>>
disjoint (range 11 20) (range 21 30)
True
Combine
symmetricDifference :: Word8Set -> Word8Set -> Word8Set Source #
Symmetric difference between two sets
symmetricDifference
xs ys =difference
(union
xs ys) (intersection
xs ys)
>>>
symmetricDifference (range 10 20) (range 15 25)
fromList [10,11,12,13,14,21,22,23,24,25]
Since: 0.1.1
complement :: Word8Set -> Word8Set Source #
The complement of the set.
Filter
filter :: (Key -> Bool) -> Word8Set -> Word8Set Source #
Filter all elements that satisfy some predicate.
>>>
filter even (range 10 20)
fromList [10,12,14,16,18,20]
partition :: (Key -> Bool) -> Word8Set -> (Word8Set, Word8Set) Source #
Partition the set according to some predicate.
>>>
partition even (range 10 20)
(fromList [10,12,14,16,18,20],fromList [11,13,15,17,19])
Map
map :: (Key -> Key) -> Word8Set -> Word8Set Source #
is the set obtained by applying map
f sf
to each element of s
.
>>>
map (+ 1) (fromList [0, 10, 250, 255])
fromList [0,1,11,251]
Folds
foldr :: (Key -> b -> b) -> b -> Word8Set -> b Source #
Lazy right fold.
>>>
foldr (:) [] (unions [range 10 20, range 70 73, range 130 132, range 200 202, singleton 255])
[10,11,12,13,14,15,16,17,18,19,20,70,71,72,73,130,131,132,200,201,202,255]
foldl :: (a -> Key -> a) -> a -> Word8Set -> a Source #
Lazy left fold.
>>>
foldl (flip (:)) [] (unions [range 10 20, range 70 73, range 130 132, range 200 202, singleton 255])
[255,202,201,200,132,131,130,73,72,71,70,20,19,18,17,16,15,14,13,12,11,10]
Strict folds
Min/Max
findMin :: Word8Set -> Word8 Source #
The minimal element of the set.
>>>
findMin (fromList [3, 5])
3
Returns 0 for empty set.
>>>
findMin empty
0
findMax :: Word8Set -> Word8 Source #
The maximal element of the set.
>>>
findMax (fromList [3, 5])
5
Returns 255 for empty set.
>>>
findMax empty
255
deleteMin :: Word8Set -> Word8Set Source #
Delete the minimal element. Returns an empty set if the set is empty.
deleteMax :: Word8Set -> Word8Set Source #
Delete the maximal element. Returns an empty set if the set is empty.
maxView :: Word8Set -> Maybe (Key, Word8Set) Source #
Retrieves the maximal key of the set, and the set
stripped of that element, or Nothing
if passed an empty set.
>>>
maxView (fromList [3, 5])
Just (5,fromList [3])
>>>
maxView empty
Nothing
minView :: Word8Set -> Maybe (Key, Word8Set) Source #
Retrieves the minimal key of the set, and the set
stripped of that element, or Nothing
if passed an empty set.
>>>
minView (fromList [3, 5])
Just (3,fromList [5])
>>>
minView empty
Nothing