This week in the Sets series, we’ll look at
It does the same thing as
List.filter, except using our sets.
We’ll have it take a function that checks whether we should include a value and use the output of that function to filter the values from the set.
We can’t remove values at random without unbalancing our sets, so we’ll use
insert to keep our set balanced:
filter : (comparable -> Bool) -> Set comparable -> Set comparable filter cmp set = foldl (\item acc -> if cmp item then insert item acc else acc ) empty set
We’re inserting the item into a new set if the comparator function returns
True, otherwise we’ll skip adding it and return the accumulator value.
We could implement this in reverse: we’d start with the accumulator as our initial value and use
remove if the comparator function didn’t match.
Both approaches work, but in the real world we would benchmark before deciding.
So how do we use
Say we had a set with the numbers 1 through 10:
numbers : Set Int numbers = List.range 1 10 |> fromList
If we wanted to get only the even numbers from that set, we’d use
filter like this:
evens : Set Int evens = filter (\i -> i % 2 == 0) numbers
Side note: I’ve shown point-free style before, but here it makes our code worse!
evens : Set Int evens = filter (flip (%) 2 >> (==) 0) numbers
A little goes a long way with point-free style. Remember that next time you’re feeling clever!
filter done, we can add
We use this when we want to split a set in two according to some criteria.
It takes the same filter function, but returns both items which passed and failed the filter.
partition : (comparable -> Bool) -> Set comparable -> ( Set comparable, Set comparable ) partition cmp set = foldl (\item ( yes, no ) -> if cmp item then ( insert item yes, no ) else ( yes, insert item no ) ) ( empty, empty ) set
How about we do something more interesting with
We can implement two more combination functions,
Last week we implemented
We can represent that operation as a Venn diagram.
The two circles below represent our two sets, with the shared area representing shared values.
When we take a union of the two sets, we get everything contained in both sets.
Taking the intersection of the two sets, on the other hand, means taking all the values that the two sets have in common. The circles in our Venn diagram overlap for these values.
intersect : Set comparable -> Set comparable -> Set comparable intersect a b = filter (\item -> member item a) b
filter to implement
We select which items to include by using
This can read “if both set
b have this item, include it.”
That works out to the intersection of the sets!
intersect (fromList [1, 2]) (fromList [2, 3]) == fromList 
But what if we want only the values in one set or the other, instead of both?
To do that, we use
diff removes all the items in the second set from the first set.
Do note that we’re implementing an asymmetric diff.
That means that we’re only removing values from one set.
Some set implementations (and most image editing programs) refer to this as subtraction (where
union is addition.)
They refer to diff as a symmetric diff, which removes any items in common between the two sets, and leaves only items unique to one or the other.
Elm’s built-in Set uses asymmetric diffs, with the right-hand set removing values from the left-hand set. We’ll do that too!
diff : Set comparable -> Set comparable -> Set comparable diff a b = filter (\item -> not <| member item b) a
This looks like
intersect, but with an added
We’re checking if the set
b has an item from set
If so, we don’t include it.
It ends up working like this:
diff (fromList [1, 2]) (fromList [2, 3]) == fromList 
So we’ve learned:
- You can use folds to implement every collection operation.
filteris no exception.
partitiondoes the same thing as
filter, but keeps the items that fell through the filter in a separate set.
filter. We wouldn’t have to do this (we could implement using folds every time) but using
filtermakes things much cleaner.
After this, we have one major piece of the API left: mapping. See you then!