Understanding user defined append list Standard ml

Question

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.

Answer 1

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.

Answer 2

With normal lists,

datatype 'a normal_list = Nil | Cons of 'a * 'a normal_list

your Cons operator to prepend a single element is O(1), but to append two lists is O(n):

fun append (Nil, ys) = ys
  | append (xs, Nil) = xs
  | append (Cons (x, xs), ys) = Cons (x, append (xs, ys))

With these append lists,

datatype 'a alistNN = Sing of 'a | Append of 'a alistNN * 'a alistNN
datatype 'a alist = Nil | NonNil of 'a alistNN

your Append operator is now the O(1), but cons becomes the more difficult O(n) because, as you say, it requires destroying the list to rebuild it, since the head of the data structure is no longer the first element, but rather the point at which the list was most recently appended.

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.

(Edit: Clarified this section.) You already have a constructor Append : 'a alistNN * 'a alistNN -> 'a alistNN that does just that. To make one that instead works for 'a alist, you have to pattern match against the different cases of 'a alist; only when both lists are NonNil can you use Append (since an empty list is not expressible as an 'a alistNN. The cases where either operand is Nil can be handled separately;

fun append Nil ys = ys
  | append xs Nil = xs
  | append (NonNil xs) (NonNil ys) = NonNil (Append (xs, ys))

One thing that becomes more difficult is if you want to prepend a single element in front of an 'a alist, i.e. a function with the signature 'a * 'a alist -> 'a alist:

fun cons (x, Nil) = NonNil (...)
  | cons (x, NonNil (Sing y)) = NonNil (...)
  | cons (x, NonNil (Append (ys, zs))) = NonNil (...)

In every case x is prepended. There are three cases when it comes to the list to which you're prepending x: Either the list is empty, the list is non-empty and contains a single element, or the list is non-empty and contains the Append of two other lists. In every case, the result is something NonNil, since prepending an x to a list will never give Nil.

The first two cases should be straight forward. The third case you have to think about where to put x in terms of the sub-lists ys and zs.

Like this you can build all the auxiliary functions found by typing open List; in a REPL. Even hd and tl are not completely trivial because they're bent on finding the split between the first element and the rest of the list. A useful function for testing purposes would be toList with the signature 'a alist -> 'a list. A funny one to make for these append lists is rev. :-)

Since you're probably not going to make foldl:

fun foldl f e Nil = e
  | foldl f e (NonNil (Sing x)) = f (x, e)
  | foldl f e (NonNil (Append (xs, ys))) =
      foldl f (foldl f e (NonNil xs)) (NonNil ys)

For amusement, you could implement hd using foldl and throwing an exception:

fun hd xs =
    let exception FoundIt of 'a
    in foldl (fn (x, _) => raise FoundIt x) (fn _ => raise Empty) xs ()
       handle FoundIt x => x
    end

Here's a slightly related StackOverflow post: Standard ML functor examples