I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology.

My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in the answer.

Say you have a particular Abstract Syntax Tree. Now you also have some editor that allows you to annotate arbitrary nodes in the tree by hand. For example to either highlight nodes, or tie particular textual annotations to nodes ("comments").

The datatypes that allow you to store the information as produced by this editor are somehow "embellished versions" of the original datatype for the AST. E.g. for each node we now have a node that also knows whether it is highlighted or not, and recursively contains such nodes. Values from such datatypes have at least the property that you can throw away the annotations and end up with the original tree.

There is also some notion of "coupling" between the embellished AST's nodes and the "underlying AST"'s nodes, i.e. we can always point at the "source" for any embellished node. This is also to say: if there are two ways of embellishing, we can connect them.

What is the proper framework to (generally) think about this?


2 Answers 2


A good framework for reasoning about this is research on "ornaments" which were introduced by Conor McBride here: https://personal.cis.strath.ac.uk/conor.mcbride/pub/OAAO/Ornament.pdf .

The idea of ornamentation is that you start with a simple algebraic data type and then you have a separate "ornamented" version of it where the constructors might have more information, which is especially useful in dependently typed programming because a lot of times you want to "adjoin" invariants to a datatype. For more on this, there is another article in the JFP: https://josh-hs-ko.github.io/manuscripts/JFP17.pdf

However, it seems like you are not interested in dependent type theory and have noticed that ornaments arise naturally in everyday programming. For that I would recommend reading about the work on using ornaments in OCaml, specifically this paper (http://pauillac.inria.fr/~remy/ornaments/mlorn-2017-09.pdf) which also has a tutorial for the library here: http://pauillac.inria.fr/~remy/ornaments/ocamlorn/doc/tutorial.html


I think I have heard the term "decorated trees" often but this is more a folklore term than a "framework".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.