//
// Define a recursive structure for a singly linked list
//
// A list must contain at least one element. If empty lists
// are desired in a given context, use the algebraic sum
// type (list | nothing) to indicate that the list may
// be empty.
//
// Note that the "next" member is either a reference to
// a list, or the special type "nothing".
//
// Note that we use generic syntax (angle brackets) and a
// dummy type placeholder "T" (which is arbitrarily chosen
// here) to denote that a list can hold elements of any
// type the programmer provides.
//
structure list :
T value,
(list ref | nothing) next
//
// Define a helper constructor for the list type
//
// This constructor creates a new list of one element
// given the value to place in the list. It is useful
// for constructing new lists without having to spell
// out the "nothing" in the "next" member.
//
list : T value -> list newlist = value, nothing [constructor]
//
// Prepend an element onto the beginning of a list
//
// This is a simple example of manipulating a data
// structure defined as above. Note again the use
// of generic syntax to indicate that the function
// can apply to any type.
//
prepend : list ref thelist, T value
{
list newlist = value, thelist
thelist = newlist
}
//
// Append an element to the end of a list
//
append : list ref thelist, T value
{
append_helper(thelist, thelist.next, value)
}
//
// Pattern matching base case: when appending to
// a list whose tail is nothing, replace the "next"
// reference with a new list containing the value
// to be appended to the original list.
//
append_helper : list ref thelist, nothing, T value
{
thelist.next = list(value)
}
//
// Pattern matching general case: when appending
// to a list which has a non-nothing tail, recurse
// until we reach the base case implemented above.
//
append_helper : list ref thelist, list ref tail, T value
{
append_helper(tail, tail.next, value)
}
//
// An example program using the list data structure
//
entrypoint :
{
list numbers = 1
append(numbers, 2)
append(numbers, 3)
print(numbers.value)
print(numbers.next.value)
print(numbers.next.next.value)
}I'm also thinking of adding built-in tuple syntax and some other goodies. This sort of thing is starting to intrigue me, so I may wind up implementing it soon.
