Home › Topics › Essence › Structural

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.

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

UML Model Distilled Model Essence Example Object Graph Datatype
Mutually-Recursive Linked Lists
A 1->1 nextB B
B 1->1 nextA A		 A->B
B->A		 0+2 = 2 a1->b1->a2->b2->a1 Circular singly-linked mutually-recursive list
A 1->0..1 nextB B
B 0..1->1 nextA A		 A->B
B->A		 0+2 = 2 a1->b1->a2 Singly-linked mutually-recursive list
A prevA 1<->1 nextB B
A nextA 1<->1 prevB B		 A->B
B->A		 0+2 = 2 a1->b1->a2->b2->a1
b2->a2->b1->a1->b2		 Circular doubly-linked mutually-recursive list
A prevA 1<->0..1 nextB B
A nextA 1<->0..1 prevB B		 A->B
B->A		 0+2 = 2 a1->b1->a2
a2->b1->a1		 Doubly-linked mutually-recursive list
Mutually-Recursive Trees
A 1->0..* children B
B 0..1->0..* children A		 A->B[
B[->B
B->A[
A[->A		 2+2 = 4 a1->a11, a1->a12, a11->a111 Mutually-recursive tree
A parent 1<->0..* children B
B parent 0..1<->0..* children A		 A->B[
B[->B
B->A
B->A[
A[->A
A->B		 2+2 = 4 a1->a11, a1->a12, a11->a111
a111->a11, a11->a1, a12->a1		 Mutually-recursive tree with parent pointer
A parent 1<-0..* B
B parent 0..1<-0..* A		 B[->B
B->A
A[->A
A->B		 2+2 = 4 a111->a11, a11->a1, a12->a1 Mutually-recursive tree without children pointer
Mutually-Recursive Graphs
A 1->0..* outEdges B
B 0..*->1 targetNode A		 A->B[
B[->B
B->A
B['->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 B
B inEdges 0..*<->1 targetNode A		 A->B[
B[->B
B->A
A->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

Notes