## Structural Essence: Effect of Recursive Datatypes

This is a page of the online appendix of our paper on Structural Essence.

### Fundamental Recursive Datatypes

Here we present the most fundamental recursive datatypes, their representation in UML, in our distilled model, and their absolute structural essence. Note that lists have a structural essence of 1, trees have a structural essence of 2, and graphs have a structural essence of 3.

 Linked Lists Trees Graphs UML Model Distilled Model Essence Example Object Graph Datatype A 1->1 next A A->A 0+1 = 1 a1->a2->a3->a1 Circular singly-linked list A 0..1->0..1 next A A->A 0+1 = 1 a1->a2->a3 Singly-linked list A prev 1<->1 next A A->A 0+1 = 1 a1->a2->a3->a1a3->a2->a1->a3 Circular doubly-linked list A prev 0..1<->0..1 next A A->A 0+1 = 1 a1->a2->a3a3->a2->a1 Doubly-linked list A 0..1->0..* children A A->A[A[->A 1+1 = 2 a1->a11, a1->a12, a11->a111 Tree A parent 0..1<->0..* children A A->A[A[->AA->A 1+1 = 2 a1->a11, a1->a12, a11->a111a111->a11, a11->a1, a12->a1 Tree with parent pointer A parent 0..1<-0..* A A[->AA->A 1+1 = 2 a111->a11, a11->a1, a12->a1 Tree without children pointers A 0..*->0..* successors A A->A[A[->AA['->A 2+1 = 3 a1->a2, a1->a3, a2->a4, a4->a2 Singly-linked graph A predecessors 0..*<->0..* successors A A->A[A[->AA->A['A['->A 2+1 = 3 a1->a2, a2->a1, a1->a3, a3->a1, a2->a4, a4->a2 Doubly-linked graph

### Special Mutually-Recursive Datatypes

Besides the above fundamental recursive datatypes above, we also investigate some more specialized datatypes, in particular mutually-recursive lists and trees.

 Mutually-Recursive Linked Lists Mutually-Recursive Trees Mutually-Recursive Graphs UML Model Distilled Model Essence Example Object Graph Datatype A 1->1 nextB BB 1->1 nextA A A->BB->A 0+2 = 2 a1->b1->a2->b2->a1 Circular singly-linked mutually-recursive list A 1->0..1 nextB BB 0..1->1 nextA A A->BB->A 0+2 = 2 a1->b1->a2 Singly-linked mutually-recursive list A prevA 1<->1 nextB BA nextA 1<->1 prevB B A->BB->A 0+2 = 2 a1->b1->a2->b2->a1b2->a2->b1->a1->b2 Circular doubly-linked mutually-recursive list A prevA 1<->0..1 nextB BA nextA 1<->0..1 prevB B A->BB->A 0+2 = 2 a1->b1->a2a2->b1->a1 Doubly-linked mutually-recursive list A 1->0..* children BB 0..1->0..* children A A->B[B[->BB->A[A[->A 2+2 = 4 a1->a11, a1->a12, a11->a111 Mutually-recursive tree A parent 1<->0..* children BB parent 0..1<->0..* children A A->B[B[->BB->AB->A[A[->AA->B 2+2 = 4 a1->a11, a1->a12, a11->a111a111->a11, a11->a1, a12->a1 Mutually-recursive tree with parent pointer A parent 1<-0..* BB parent 0..1<-0..* A B[->BB->AA[->AA->B 2+2 = 4 a111->a11, a11->a1, a12->a1 Mutually-recursive tree without children pointer A 1->0..* outEdges BB 0..*->1 targetNode A A->B[B[->BB->AB['->B 2+2 = 4 a1->b1, b1->a2, a1->b2, b2->a3, a2->b3, b3->a4, a4->b4, b4->a2 Singly-linked graph with edges A sourceNode 1<->0..* outEdges BB inEdges 0..*<->1 targetNode A A->B[B[->BB->AA->B['B['->B 2+2 = 4 a1->b1, b1->a2, a1->b2, b2->a3, a2->b3, b3->a4, a4->b4, b4->a2 Doubly-linked graph with edges