Im having trouble understanding this implementation of lists in Standard ML. Here is how it is defined:
An append list is a (simple) implementation of the list abstract data type that makes construction cheap (O(1)), but makes destruction expensive (O(n)). The 'a alistNN and 'a alist types are defined as follows:
datatype 'a alistNN = Sing of 'a | Append of 'a alistNN * 'a alistNN
datatype 'a alist = Nil | NonNil of 'a alistNN
The 'a alistNN type represents the “non-nil” append lists, while the 'a alist type represents arbitrary (nil or non-nil) append lists.
Im confused on how I would work with these lists/make these lists. For example I have to write a function that is defined as:
'a alist -> 'a alist -> 'a alist that appends to append lists.
Any help will be appreciated in understanding this list definition.
This data structure represents a list with a tree, where each internal node represents concatenation of its children, and each leaf is an element. For example, here's two possible representations for the list [1,2,3,4]:
val L1 = Append (Append (Sing 1, Sing 2), Append (Sing 3, Sing 4))
*
/ \
* *
/ \ / \
1 2 3 4
val L2 = Append (Append (Sing 1, Append (Sing 2, Sing 3)), Sing 4)
*
/ \
* 4
/ \
1 *
/ \
2 3
Appending these data structures is extremely easy; you just link them together with a new Append node. We could append the two examples above:
Append (L1, L2)
*
/ \
/ \
* *
/ \ / \
* * * 4
/ \ / \ / \
1 2 3 4 1 *
/ \
2 3
Obviously you'll also have to wrap these in NonNil as appropriate, but I'll leave that to you.