Data.Set

The Data.Set module offers us sets in the mathematical sense:

  • all the elements in a set are unique;
  • and because they’re internally implemented with trees (for speed), they’re ordered;
  • checking for membership, inserting, deleting etc. is much faster than doing the same thing with lists;

Because the names in Data.Set clash with a lot of Prelude and Data.List names, we do a qualified import.


ghci 27> import qualified Data.Set as S

fromList :

Besides inserting into a set and checking for membership, the most common operation when dealing with sets is probably converting a list into a set.

with sets is probably converting a list into a set. Let’s say we have two pieces of text. We want to find out which characters were used in both of them


ghci 28> let text1 = "I just had an anime dream. Anime... Reality... Are they so different?"

ghci 29> let text2 = "The old man left his garbage can out " + "and now his trash is all over my lawn!"

The fromList function works much like you would expect. It takes a list and converts it into a set.


ghci 30> let set1 = S.fromList text1

ghci 31> let set2 = S.fromList text2

ghci 32> : t S.fromList
S.fromList :: Ord a => [a] -> S.Set a

ghci 33> set1
fromList " .?AIRadefhijlmnorstuy"


ghci 34> : t set1
set1 :: S.Set Char

ghci 35> set2
fromList " !Tabcdefghilmnorstuvwy"

As you can see, the items are ordered and each element is unique

intersection :

Now let’s use the intersection function to see which elements are in both sets


ghci 36> S.intersection set1 set2
fromList " adefhilmnorstuy"

difference :

We can use the difference function to see which letters are in the first set but aren’t in the second one and vice versa


ghci 37> S.difference set1 set2
fromList ".?AIRj"


ghci 38> S.difference set2 set1
fromList "!Tbcgvw"

union :

Or we can see all the unique letters used in both sentences by using union


ghci 39> S.union set1 set2
fromList " !.?AIRTabcdefghijlmnorstuvwy"

empty, null, size, member, singleton, insert, delete :

The empty, null, size, member, singleton, insert and delete functions all work like you’d expect them to.


ghci 40> S.empty
fromList [ ]

ghci 41> S.null S.empty
True


ghci 42> S.null $ S.fromList [3, 4, 5, 5, 4, 3]
False


ghci 43> S.size $ S.fromList [3, 4, 5, 3, 4, 5]
3


ghci 44> S.singleton 9
fromList [9]


ghci 45> S.insert 4 $ S.fromList [9, 3, 8, 1]
fromList [1, 3, 4, 8, 9]


ghci 46> S.insert 8 $ S.fromList [5 . . 10]
fromList [5, 6, 7, 8, 9, 10]


ghci 47> S.delete 4 $ S.fromList [3, 4, 5, 4, 3, 4, 5]
fromList [3, 5]

isSubsetOf and isProperSubsetOf :

We can also check for subsets or proper subsets.


ghci 48> S.fromList [2, 3, 4] ‘S.isSubsetOf‘ S.fromList [1, 2, 3, 4, 5]
True


ghci 49> S.fromList [1, 2, 3, 4, 5] ‘S.isSubsetOf‘ S.fromList [1, 2, 3, 4, 5]
True


ghci 50> S.fromList [2, 3, 4, 8] ‘S.isSubsetOf‘ S.fromList [1, 2, 3, 4, 5]
False


ghci 51> S.fromList [1, 2, 3, 4, 5] ‘S.isProperSubsetOf‘ S.fromList [1, 2, 3, 4, 5]
False

map and filter :

We can also map over sets and filter them.



ghci 52> S.filter odd $ S.fromList [3, 4, 5, 6, 7, 2, 3, 4]
fromList [3, 5, 7]


ghci 53> S.map (+1) $ S.fromList [3, 4, 5, 6, 7, 2, 3, 4]
fromList [3, 4, 5, 6, 7, 8]

setNub :

Sets are often used to weed out duplicates in a list by first making the list into a set with fromList and then converting the set back to a list with toList.

The Data.List function nub already does this, but it is much faster to weed out duplicates for large lists if you convert them to sets and then convert them back to lists

However, using nub only requires the type of the list elements to be part of the Eq typeclass, whereas if we want to convert the list to a set, the type of the list elements has to be in Ord.


ghci 54> let setNub xs = S.toList $ S.fromList xs


ghci 55> setNub "HEY WHATS CRACKALACKIN"
" ACEHIKLNRSTWY"


ghci 56> import Data.List


ghci 57> nub "HEY WHATS CRACKALACKIN"
"HEY WATSCRKLIN"

As we already mentioned, setNub is generally faster than nub on big lists. But as you can see, nub preserves the ordering of the list’s elements, while setNub does not.

About Author

Myself KarthiQ, I am the author of this blog, I know ways to write a good article but some how I donot have the skills to make it to reach people, would you like help me to reach more people By sharing this Article in the social media.

Share this Article Facebook
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recen