Rose Forests

Carl Masak blogged about tree data structures, which caught my interest because of a pet-project of mine (tailor; a structure description and measurement tool) where I found myself using trees a lot. An awful lot. Perhaps ... too much.

Anyway, a related tweet by AudreyT mentioned an article called "Origami Programming" by Jeremy Gibbons. Which is in haskell (perhaps not surprisingly), a language I don't speak very well. However, while reading - and not understanding it - I did get one thing which was the idea of having a tree datatype where the node (called a 'rose') references a forest (a list of roses). I think that's right.

In any case, it solves a object-modelling problem for me that I had. The difficulty was that protein structures are hierarchical, yes, but have a strange mixed hierarchy of types. Perhaps this is obvious to haskell programmers and compiler-code writers, but this makes it very difficult to use the 'simple' tree datatype, where a Node class has a List of Node children.

Specifically, I mean situations like: a Chain composed of Atoms or a Chain of SSEs of Residues of Atoms. The 'rose tree' way of doing things makes this possible, at the price of a more complex model. Now here is a picture of a sketch of it:

So, for example, you can have a Protein:ChainList(Chain:AtomList(Atom),Chain:ResidueList(Residue...)) or several other possibilities. Also a visitor to the hierarchy can do separate things to a Tree than to a LeafList. Neat! Oh, and the code for the implementation (just the bare bones, not usable) is here.

Comments