7 The cons library🔗ℹ

This library provides a representation for header-free singly-linked lists, as well as a number of utility functions that operate on them.

These definitions are not part of the base DSSL2 language, and must be imported explicitly using: import cons

7.1 The cons struct🔗ℹ

The core definition of the cons library is the cons struct, which represents a node in a singly-linked list:

struct cons:

let data

let next: Cons.list?

The end of the linked list must be marked with None. A value of None on its own is therefore an empty linked list.

For example, the code:

cons(1, cons(2, cons (3, None)))

Produces a linked list with elements 1, 2, and 3, in that order.

procedure cons(AnyC, Cons.list?) -> Cons.list?

Constructs a cons struct.

O(1) time and space.

procedure cons?(AnyC) -> bool?

A predicate that checks whether the given value is a cons struct.

O(1) time and space.

7.2 The Cons.X family of functions🔗ℹ

This library provides a number of utility functions for working with lists made of cons structs with names starting with Cons..

procedure Cons.list?(AnyC) -> bool?

A predicate that checks whether the given value is a linked list made of cons structs, with None at the end.

O(1) time and space.

procedure Cons.ListC[C: contract?]: contract?

Constructs a contract for a list, given a contract C for the elements. This contract copies the list while applying constract C to each element.

O(n × TC) time and O(n + SC) space.

procedure Cons.len(Cons.list?) -> nat?

Finds the length of a list.

O(n) time and O(1) space.

procedure Cons.app(Cons.list?, Cons.list?) -> Cons.list?

Appends two lists producing a new list, and not modifying either of the input lists. The resulting list will share structure with the second list.

O(n) time and space, where n is the length of the first list.

procedure Cons.rev(Cons.list?) -> Cons.list?

Reverses a list producing a new list, and not modifying the input list.

O(n) time and space.

procedure Cons.rev_app(Cons.list?, Cons.list?) -> Cons.list?

Reverses the first list, appending it onto the second.

O(n) time and space, where n is the length of the first list.

procedure Cons.concat(Cons.list?, Cons.list?) -> Cons.list?

Destructively concatenates two lists, returning the concatenated list, and modifying the first list.

O(n) time and O(1) space, where n is the length of the first list.

procedure Cons.to_vec(Cons.list?) -> vec?

Converts a list to a vector.

O(n) time and space.

procedure Cons.into_vec(Cons.list?, vec?, nat?) -> NoneC

Copies a list into a vector starting at the index given by the third argument. Assumes there is enough space in the vector.

O(n) time and O(1) space.

procedure Cons.from_vec(vec?) -> Cons.list?

Creates a list from the elements of a vector.

O(n) time and space.

procedure Cons.foreach(f: FunC[AnyC, AnyC], Cons.list?) -> NoneC

Calls a visitor function on each element of the given list, in order.

O(n × Tf) time and O(Sf) space.

procedure Cons.foldr[Y](f: FunC[AnyC, Y, Y], Y, Cons.list?) -> Y

Traverses a list from right to left, accumulating a result using the given function.

O(n × Tf) time and O(n + Sf) space.

procedure Cons.foldl[Y](f: FunC[Y, AnyC, Y], Y, Cons.list?) -> Y

Traverses a list from left to right, accumulating a result using the given function.

O(n × Tf) time and O(Sf) space.

procedure Cons.map(f: FunC[AnyC, AnyC], Cons.list?) -> Cons.list?

Maps over a list by applying a function to each element. O(n) time and O(n) space (to allocate the new list).

O(n × Tf) time and O(n + Sf) space.

procedure Cons.filter(pred?: FunC[AnyC, AnyC], Cons.list?) -> Cons.list?

Filters a list by applying a predicate to each element.

O(n × Tpred?) time and O(Spred?) space.

procedure Cons.andmap(f: FunC[AnyC, AnyC], Cons.list?) -> AnyC

Applies the given function to each element in turn, returning False if the result is False for any element, and otherwise returning the result of the function applied to the last element. Returns True if the list is empty.

O(n × Tf) time and O(Sf) space.

procedure Cons.ormap(f: FunC[AnyC, AnyC], Cons.list?) -> AnyC

Applies the given function to each element in turn, returning the first non-False result, or False if none is non-False.

O(n × Tf) time and O(Sf) space.

procedure Cons.sort[T](lt?: FunC[T, T, AnyC], Cons.listC[T]) -> Cons.list?

Sorts a list producing a new list, without modifying the input list. Uses the given function as a “less than” comparison to determine the order.

This function uses insertion sort as its sorting algorithm.

O(n² × Tlt?) time and O(n + Slt?) space.