Our Set implementation is done! We just have a few things to wrap up.

Get All the Posts

This was a long series! If you’d like to go through it again, or didn’t see all of the posts the first time, I’ve set up a way to get them by email. You’ll get them once per week, but without any interruption. I’ve also included some exercises in each, to help with comprehension.

`Dict`s

There’s another fun experiment you can do now: build `Dict` on top of what we’ve already got!

`Dict`s are sets of keys associated with values. In fact, core’s `Set` is actually `Dict comparable ()`. All the Set functions there are wrappers over the `Dict` functions.

Since we’ve already got key management, you’ll just need to write some code to retrieve values. Core’s `Dict` implementation will be a great reference (although it uses red/black trees instead of AVL trees.) Here’s how you can change the `Set` constructors to get started:

``````type Dict comparable a
= Tree Int comparable a (Dict comparable a) (Dict comparable a)
| Empty
``````

Errata

Remove

The implementation of `remove` I wrote originally had a bug. The tree rooted at the item for removal would be rebalanced, but the parents wouldn’t be. That means that if you removed all the items on one side of the tree, it would become more and more unbalanced.

Try this yourself by creating a set, then removing all the items in the left side. The tree will become more and more unbalanced the more items you remove from it. An easy replication: `List.range 1 10 |> fromList |> remove 1 |> remove 2 |> remove 3`.

We fix this by rebalancing the tree after each removal:

``````remove : comparable -> Set comparable -> Set comparable
remove item set =
case set of
Empty ->
set

Tree _ head left right ->
tree head (remove item left) right |> balance
else if item > head then
tree head left (remove item right) |> balance
else
union left right
``````

Thanks to Ilias Van Peer for the catch!

Constructors

Some posts had incorrect `Set` constructors. This happened because I changed the set internals several times while writing the posts. I thought I got them all, but some slipped through. These have all been corrected.