8 LISTS

8.1 List Creation
8.2 Adding Elements to a List
8.3 Accessing Elements of a List
8.4 Inserting Elements into a List
8.5 Removing Elements from a List
8.6 Lists and Streams
8.7 Lists and Functions
8.8 Summary

 

Lists, as well as arrays, are basic collections defined in the language. A list consists of a number of elements. The number of elements in a list is not fixed but may vary during execution. This is in contrast to arrays where the (maximum) number of array elements is fixed at creation time.

The elements of a list are arranged in linear order. Each element has a successor, except the last element of a list, and each element has a predecessor, except the first element of a list. All elements of a list can be visited in forward direction, from the beginning to the end of a list, but also in backward direction, from the end to the beginning of the list. That means that lists in Elisa are bi-directional.

Each element of a list is represented by a separate data-structure, called node. A node contains a pointer to its predecessor in the list, a pointer to its successor, and a reference to the associated data item.

The basic operations defined for all types of lists and their elements are:

alist (elementtype) 	-> list;
add (list, element) 	-> nothing;
add (element, list) 	-> nothing;
first (list)            -> node; 
last (list)             -> node; 
next (node)             -> node; 
prior (node) 		-> node; 
item (node)             -> element;
insert (node, element)	-> nothing;
insert (element, node)	-> nothing;
remove (node) 		-> element;
endlist (node) 		-> boolean;
items (list) 		-> multi (element);
prioritems (list) 	-> multi (element);
nodes (list) 		-> multi (node);
priornodes (list) 	-> multi (node);

These operations are discussed in the following sections.

8.1 List Creation

The language offers two ways to create lists. One way is to use the predefined alist function. This function expects one argument: the type of the elements of the list. Let us give an example:

L = alist (text);

The evaluation of the alist function results in the creation of a new and empty list. In this example, all elements of the list will be text items. The type of a list is a compound type. It is derived from the type of the elements. In this case it is the compound type list(text) which will also be the type of the name L.

We will give some other examples of creating new empty lists:

L1 = alist (integer); 		<< type of L1 is list (integer) >>

L2 = alist (array (real)); 	<< type of L2 is list (array (real)) >>

L3 = alist (list (text)); 	<< type of L3 is list (list (text)) >>

From these examples it will be clear that lists of lists and lists of arrays are also allowed. In fact there is no limitation of list element types.

In our examples so far, the lists defined are homogeneous lists with elements which are all of the same type. To create heterogeneous lists with elements of different types the element type must be the name of a category or it must be the term type. Categories are discussed in Chapter 14, terms are discussed in Chapter 13.

As said earlier, the alist function creates only an empty list. The elements of the list have to be added separately by dedicated list operations as discussed in one of the following sections. However, in a lot of cases it is much more convenient to combine the creation of a list together with some elements in one language construct. Therefore there is an additional method for creating lists.

This second way of creating a list is based on the following language construct:

{ expr, expr2, expr3 ... }

The curly brackets are indicating a new list. The expressions between the curly brackets are representing the elements of the new list. Each expression may represent one element or a stream of elements. Each element of a stream will become an element of the list. An empty stream creates no list elements.

Examples are:

{ 17, 39, 3 * 45, -12 } 		<< type list (integer) >>

{ "a", "bc", "def" } 			<< type list (text) >>

{{ "a", "bc" }, { "A", "BC", "DEF"} }	<< type list (list (text)) >>

{ array (real, 7), array (real, 15) } 	<< type list (array (real)) >>

Exercise:

• 8.1 Create a list with the first 6 Fibonacci numbers.

8.2 Adding Elements to a List

There are two ways to add a new element to a list: the element may be added to the front of the list or to the rear of the list. In both cases the add operation is used:

add (list, element) -> nothing;

add (element, list) -> nothing;

The operation add (list, element), adds a new element at the end of the list.

The operation add (element, list), adds a new element at the beginning of the list.

In both cases nothing will be returned as a result.

Examples are:

L = { "ab", "abc" }; 	<< L = { "ab", "abc" }; >>

add (L, "abcd"); 	<< L = {"ab", "abc", "abcd"}; >>

add ("a", L); 		<< L = {"a", "ab", "abc", "abcd"}; >>

Exercise:

• 8.2 Add two other numbers to the list of Fibonacci numbers of Exercise 8.1.

8.3 Accessing Elements of a List

There are a number of accessor functions defined on lists:

first (list) returns the first node of a list

last (list) returns the last node of a list

next (node) returns the successor of a node

prior (node) returns the predecessor of a node

item (node) returns the data item of a node

endlist (node) returns a boolean. If the end of the list has been reached the endlist function will return the value true otherwise will return the value false will be returned.

Let us use some examples. Suppose S is a list of text-objects:

S = { "A", "B", "C", "D", "E", "F", "G" };

The type of the list S is list (text). The following expressions will produce as results:

item (first (S)) 		=> "A"

item (last (S)) 		=> "G"

item (next (first (S))) 	=> "B"

item (next (next (first (S)))) 	=> "C"

item (prior (prior (last (S))))	=> "E"

endlist (prior (last (S))) 	=> false

endlist (last (S)) 		=> false

endlist (next (last (S))) 	=> true

endlist (first (S)) 		=> false

endlist (prior (first (S)))	 => true

item (prior (first (S))) 	=> ERROR

item (next (last (S))) 		=> ERROR

Exercise:

• 8.3 Select the first, the fifth and the last Fibonacci numbers from the list produced in Exercise 8.2.

8.4 Inserting Elements into a List

There are two ways to insert a new element into a list: either the element may be inserted after a given element of the list or before the given element of the list. In both cases we use the insert operation:

insert (node, element) -> nothing;

insert (element, node) -> nothing;

If we want to insert a new element E after a given node N we will use the expression:

insert (N, E)

If the new element E should be inserted before the given node N we will use:

insert (E, N)

In both cases nothing will be returned as a result.

Some examples are:

L = { "ab", "abc" }; 		<< L = { "ab", "abc" }; >>

insert (last (L), "abcd");	<< L = { "ab", "abc", "abcd"}; >>

insert ( "a", first (L)); 	<< L = { "a", "ab", "abc", "abcd"}; >>

insert (first (L), "b"); 	<< L = {"a","b","ab", "abc", "abcd"}; >>

Exercise:

• 8.4 Insert the ninth and tenth Fibonacci number in the list produced in Exercise 8.2.

8.5 Removing Elements from a List

To delete an element from a list we may use the remove operation:

remove (node) -> element;

This operation removes the designated node from the list and returns the associated data item. For example, using the S list of a previous example, the following expression:

remove (next (first (S)))

removes the second element of S and returns the text string "B".

Other examples are:

T = { "a","ab","abc" };		<< T = { "a","ab","abc" }; >>

P = remove (last (T)); 		<< P = "abc"; T = {"a","ab"}; >>

Q = remove (prior (last (T))); 	<< Q = "a"; T = {"ab"}; >>

Exercise:

• 8.5 Remove the seventh and fourth Fibonacci numbers from the list produced in Exercise 8.4.

8.6 Lists and Streams

To extract all the elements of a list four multi-value operations are available:

items (list) generates a stream of all the data items of the list in normal order.

prioritems (list) generates a stream of all the data items of the list in reverse order.

nodes (list) generates a stream of all the nodes of the list in normal order.

priornodes (list) generates a stream of all the nodes of the list in reverse order.

Let us use some examples. Suppose we have a list:

L = { "a", "ab", "abc"}; 

The following expressions will produce streams:

items (L) 	<< ( "a", "ab", "abc") >>

prioritems (L) 	<< ( "abc", "ab", "a") >>

nodes (L) 	<< ( node("a"), node("ab"), node("abc")) >>

priornodes (L) 	<< ( node("abc"), node("ab"), node("a")) >>

An empty list will produce an empty stream.

Exercise:

• 8.6 Create a stream of Fibonacci numbers from the list produced in Exercise 8.5.

There are many ways to combine list operations and streams. We will give some examples:

Our first example is to create a copy of a given list L by using the following expression:

{ items (L) }

In this example, the items of list L are converted into a stream and the stream on its turn is converted into a new list. This is a very common scheme which is used in many situations, as will be shown by some other examples.

Our next example is to create a list in reverse order. If you want to create a new list R, which consists of all the elements of list L but in reversed order, this is done by:

R = { prioritems (L) };

Another example is to concatenate the elements of two lists L1 and L2 without disturbing the original lists, by:

{ items (L1), items (L2) }

And to use an example based on arrays: suppose you want to store all the elements of array A into a list. You just convert the elements of the array into a stream and then enclose them in curly brackets to create a list of all the array elements:

{ A[ 1 .. size (A) ] }

In all these examples we used streams as intermediate between the inputs and the required results.

8.7 Lists and Functions

Lists may be used as arguments but also as results of functions. Suppose we want to use lists as the basis for first-in-first-out queues and we want to define two functions on those queues: one for entering elements in a queue, which we will call Enqueue and another one for getting an element out of a queue, named Dequeue. As an example, the definitions for queueing text messages are:

Enqueue (Queue = list (text), Message = text) -> nothing;
Enqueue (Queue, Message) = add (Queue, Message );

Dequeue (Queue = list (text)) -> text;
Dequeue (Queue) = remove (first (Queue));

The first line is a specification of the Enqueue function. It says that the function has two parameters, the first being the Queue which must be a list of text and the second being the Message which must be text. The definition has no output.

At the second line the Enqueue operation is defined. A new Message will be added at the end of the Queue.

The third line is a specification of the Dequeue function. It says that the function has one parameter, being the Queue which again must be a list of text. The output of the function is the text of the Message.

The fourth line defines the Dequeue operation. The first Message will be removed from the queue and returned to the caller.

We can now use these functions in a dialogue session in the following way:

Q = alist (text);
Enqueue (Q, "Message 1");
Enqueue (Q, "Message 2");

Dequeue (Q)?
"Message 1"

Dequeue (Q)?
"Message 2"

Notice that the elements of the queue are retrieved in First-In-First-Out order.

Exercise:

• 8.7 In a real application, we also will need a function to test if a Queue is empty. Give a definition for that.

8.8 Summary

• A list is a basic collection defined in the language. A list consists of a number of elements. The number of elements in a list is not fixed but may vary during execution.

• Each element has a successor, except the last element of a list, and each element has a predecessor, except the first element of a list.

• There are two ways to create lists. One way is to use the predefined alist function. The other way is by using a pair of curly brackets to enclose a list of expressions.

• There are two ways to add a new element to a list: the element may be added to the front of the list or to the rear of the list. In both cases the add operation is used.

• The first, last, next, and prior operations are accessing the first, last, next or prior element of a list.

• The endlist operation returns a boolean to indicate if the end of a list is reached.

• The item operation returns the current data item of a list.

• The insert operation inserts an element into a list.

• The remove operation removes the current element of a list and returns the associated item.

• The items(list) operation produces a stream of all the items of a list in normal order.

• The prioritems(list) operation produces a stream of all the items of a list in reverse order.

• The nodes(list) operation produces a stream of all the nodes of a list in normal order.

• The priornodes(list) operation produces a stream of all the nodes of a list in reverse order.

• The use of list operations together with streams can provide very powerful combinations.

• Lists may be used as arguments but also as results of definitions.

Part 1: Language Description

Chapter 8: Lists