11. List Processing

This tutorial is an introduction to processing lists of data. Lists are conceptually represented as a linked list of nodes in which the head of the node stores the list element and the tail stores the next node, i.e. the remainder, of the list. The meta-nodes head and tail, from the core module, return the head and tail of a list node respectively.

[Note]

This is only a conceptual view as not all lists are necessarily implemented as linked lists. Some lists are actually implemented as contiguous arrays which provide a linked list interface. In the current release, only linked lists can be created explicitly, however functionality for creating arrays will be added in a future release.

The empty list is represented by the value of the node Empty. The tail of the last node in a list is bound to this node.

[Tip]

The node Empty! is bound to a failure of type Empty, which is returned when attempting to access the head or tail of an empty list.

11.1. Creating Lists

The cons meta-node creates a list node, taking the value for the head and the tail as arguments. This can be used to append to the front of an existing list:

# Create a list of 1 element, by appending to the front of the empty
# list
l1 <- cons(a, Empty)

# Append to front of l1, creating a list of 2 elements
l2 <- cons(b, l1)

The list meta-node takes a variable number of arguments and returns a list containing the values of the arguments as elements.

# Create list with elements: 1, 2, 3
l <- list(1, 2, 3)

The list* meta-node, also taking a variable number of arguments, is used to prepend a number of elements to the front of a list. The last argument is interpreted as a list with the remaining arguments prepended to the front of it.

# Create list with 1 and 2 prepended to the front of l1
l2 <- list*(1, 2, l1)

11.2. Higher-Order Meta-Nodes

Meta-Nodes can be passed to other meta-nodes as arguments, or bound to ordinary nodes, in which case the function of the meta-node is referenced.

A node can appear as the operator in a functor node in which case the function, of which the reference is stored in the node’s value, is applied on the arguments. If the node’s value is not a reference to function or the function is applied on an incorrect number of arguments, the result is a failure value.

Example. 

call(f, arg) : f(arg)
func(x) : x

f <- func
result <- call(f, y)

In this example the call meta-node takes two arguments and returns the result of applying the first argument f on the second argument arg. The node f is bound to a reference to the function of the meta-node func, which is then passed to the call meta-node.

Outer Node References

An interesting aspect of higher-order programming in Tridash is that when referencing a meta-node as a value, which references the values of nodes declared in the global scope, a binding is established between the referenced nodes and meta-node reference. A binding is also established between the default values of optional arguments, in the case that they are references to other nodes, and the meta-node reference.

Example. 

# Increment `x` by the value of the global node `delta
increment(x) : x + delta

call(f, arg) : f(arg)

result <- call(increment, n)

The increment meta-node references the value of the global delta node. The function of the increment meta-node is referenced by the node call(increment, n), thus a binding is established between delta and call(increment, n). The result is that whenever the value of delta is changed, the value of call(increment, n) is updated.

Let’s demonstrate this with a simple application. Create a ui.html file containing the above code in a Tridash code tag and the following interface in the HTML body.

<div><label>N:<br/><input value="<?@ to-int(n) ?>"/></label></div>
<div><label>Delta:<br/><input value="<?@ to-int(delta) ?>"/></label></div>
<hr/>
<div>Result: <?@ result ?></div>

Build and run the application and enter a value for N and Delta.

N: 5, Delta: 1, Result: 6

The result of the value entered for N plus Delta is displayed, nothing new here.

Now change the value for Delta:

N: 5, Delta: 3, Result: 8

The result is updated even though there is no direct instance of increment but rather a reference to the function of increment, which is passed to the call meta-node. This demonstrates that an implicit binding delta -> call(increment, n) is created due to increment referencing the value of delta in its definition.

Higher-Order Meta-Nodes in List Processing

Higher-order meta-nodes are extremely useful for processing lists. There are many list processing utility meta-nodes, in the core module, which take a reference to a meta-node as an argument, and perform an operation on the list using the meta-node. Here are few examples:

map(f, list)The map meta-node takes a function f and a list as arguments and returns a new list with the result of the applying the function on each element of the list.

Example: map

l <- list(1, 2, 3)

1+(n) : n + 1
map(1+, l)    # Result: list(2, 4, 6)

The meta-node 1+ returns its argument plus one. 1+ is applied on each element of list l, containing the elements 1, 2, 3, using the map meta-node. The result is the list containing the elements 2, 4, 6, which is each element of the original list plus one.

foldl(f, list)The foldl meta-node reduces a list to a single value by applying a function on the first two elements of the list, and then applies the function again on the result of the previous application and the next element. This is repeated until there are no more elements in the list.

Example: foldl

l <- list(1, 2, 3)
foldl(+, l)  # Result ((1 + 2) + 3) = 6

In this example the + function is applied on the list containing the elements 1, 2, 3. foldl first applies + on the first two elements of the list (1, 2) producing the result 3. The + function is then applied on the result 3 and the next element of the list 3, producing the result 6.

The foldl'(x, f, list) function is similar to foldl except the function f is first applied on x and the first element of the list, rather than the first two elements of the list.

The foldr(f, list) function is similar to foldl except the reduction starts from the last two elements of the list and proceeds backwards until the first element.

Some other useful functions are:

filter(f, list)
Returns a list containing only those elements of list for which f returns true.
every?(f, list)
Returns true if f returns true for every element of list.
some?(f, list)
Returns true if f returns true for at least one element of list.
not-any?(f, list)
Returns true if f returns false for all elements of list.
not-every?(f, list)
Returns true if f returns false for at least one element of list.

11.3. Example: Message List

We’ll create a simple application consisting of an input field and an Add Message button. When the Add Message button is pressed, the message entered in the input field is appended to the list of messages, which are displayed below the button.

Start off with the following user interface:

ui.html

<div><label>New Message: <input value="<?@ new-message ?>"/></label></div>
<div><button id="add">Add Message</button></div>
<hr/>
<pre><?@ messages ?></pre>

The value of the New Message input field is bound to the node new-message. The value of the messages node is bound to the contents of a pre tag. This node will store the list of messages in a single formatted string.

The button is given the id add so that we can attach an event listener for its click event, in JavaScript:

Add the following code, which is similar to the code seen in Section 10, “Node States”, to a script tag below the pre tag:

document.addEventListener("DOMContentLoaded", async () => {
    const module = await mod;

    const add = document.getElementById('add');
    const clicked = module.nodes.clicked;

    add.addEventListener('click', function() {
        clicked.set_value(true);
        clicked.set_value(false);
    });
});

The value of the node with the public identifier clicked, which is the add-clicked? node, is set to true and the immediately to false when the button is clicked. Add the following attribute declarations for the add-clicked? node:

/attribute(add-clicked?, input, True)
/attribute(add-clicked?, public-name, "clicked")

We’ll need a node to store the list of messages. Let’s call it message-list and set its initial value to the empty list.

message-list <- Empty

The new message entered, bound to new-message, has to be added to the end of message-list. The append meta-node takes two lists and appends the second list at the end of the first list. Thus to append a single item, we’ll pass a list of that one item to append.

append(message-list, list(new-message))

We want the value of new-message to be appended to message-list when the Add Message button is clicked. This can be achieved with a stateful binding to message-list in the add-new state.

append(message-list, list(new-message)) ->
    message-list :: add-new

The state of message-list should be set to add-new when the Add Message Button is pressed. The add-clicked? node is true when the button is being pressed and false otherwise, thus the state of message-list can be set with the following case expression:

case(
    add-clicked? : '(add-new),
    '(default)
) -> /state(message-list)

We have completed the functionality for adding a message to the end of the messages list. All that remains is to format that list into a string which is displayed to the user.

We need a single string containing each message followed by a newline. We’ll write a format-message meta-node which appends a line break to a message.

Meta-Node format-message

format-message(message) :
    format("%s\n", message)

format-message uses the format meta-node, introduced in Section 4, “Writing your own Functions”, to produce a string containing the message, replacing the %s placeholder, followed by a line break.

[Tip]

\n in a string is an escape sequence for a line break. Other escape sequences are: \r — carriage return, \t — tab and \u{<code>} — Unicode character with code <code>.

To format each message, we’ll apply format-message on each message in message-list using map.

formatted-messages <- map(format-message, message-list)

Finally, to concatenate the formatted messages into a single string, we’ll use the string-concat meta-node, which takes two strings as arguments and returns the concatenation of both strings. We’ll need to apply string-conat on each element in formatted-messages in turn, accumulating the result in a single string. We can do that using the foldl node, passing in string-concat as the reduction function:

messages <- foldl(string-concat, formatted-messages)

The resulting string is bound to messages which is displayed in the pre (preformatted) tag, below the Add Message button.

Build and run the application, using the build configuration file from Section 10.3, “Example: Counter Application”. Enter a message and press the Add Message button.

Hello World!

The message is displayed.

Now enter a new message and click the Add Message button.

Hello World!, Hi there, how you doing?

The message is displayed below the old message.