Friday, September 16, 2011

splaytree package released

I've just uploaded a new package to Hackage, splaytree-0.1.  Splaytree provides pure functional splay trees, implemented using monoidal annotations.  A splay tree is a self-balancing tree with the property that recently-accessed nodes remain near the root, and thus subsequent accesses can be quite cheap.  As for the monoid annotations, it's the same technique as used in finger trees (see here, here, and here).  The idea is that each node of a tree holds an annotation in addition to data.  If the type of the annotation is chosen properly, it can be used to prune branches when searching.  One clever aspect of this technique is that different data structures can be implemented simply by choosing different annotations.

Currently three different data structures are available, Data.SplayTree.Set, Data.SplayTree.Seq, and Data.SplayTree.RangeSet.  'Set' provides a set with standard operations.  Not much time has been spent optimizing this library, but performance is competitive with unordered-containers for many operations (inserts can be quite slow though).  Seq is a sequence type, similar to Data.Seq.

RangeSet is perhaps the most interesting of the available containers.  Similar to an IntervalSet, a RangeSet is used for storing a list of Ranges.  A RangeSet, however, guarantees that all ranges are non-overlapping.  When a new range is inserted into the RangeSet, it is combined with any ranges currently in the set with which it overlaps.

Example (Note that a Range is a starting point and duration):

Prelude Data.SplayTree.RangeSet Data.Foldable> let rs = singleton (range 0 4)
Prelude Data.SplayTree.RangeSet Data.Foldable> toList rs
[Range {rMin = 0, rang = 4}]
Prelude Data.SplayTree.RangeSet Data.Foldable> toList $ insert rs (range 3 2)
[Range {rMin = 0, rang = 5}]
Prelude Data.SplayTree.RangeSet Data.Foldable> 

Comments and patches welcome.

Friday, September 2, 2011

My mind is blown

Recently I've read two blog posts which have really started to change how I think about programming.  A while ago I found a solution to the word numbers problem which completely stunned me with its simplicity and generality. Today I stumbled upon Apfelmus's "monoids and finger trees" blog post, which is very timely since I can use the same approach to both simplify and generalize a data structure I've been working on recently.

With this in mind, I would like to move from my current awareness (being able to follow along with these discussions) to being able to recognize and apply very general structures.  Somewhat tongue-in-cheek, I'd like to know how to make good use of Edward Kmett's packages.  Advice would be appreciated.