I just published a partial implementation of what I will refer to as an “insertion-order-preserving set”. The API (as well as the module, type and function names) is derived from that of Data.Set.Ordered from the ordered-containers package.

I found this implementation’s lack of Foldable, Semigroup, Monoid and Data instances annoying. I’ve filed some bugs and submitted some pull requests so we’ll see if I can get this original package updated. In the meantime, I need to have something working right now, so I’ve created oset (GitHub) with a type of the exact same name, Data.Set.Ordered.

Note that this package does not implement the full ordered-containers API: it only implements the bits that I currently need. I’ve been adding new bits as I need them. I also spent some time analysing the complexity bounds of the various functions and documenting these systematically in the package.

Here are some examples:

I’m going to hold off publishing this to Hackage in the hope that this project can be mothballed in the long term.

Related posts

Tags