On this page:
7.1 The cons struct
cons
cons?
7.2 The Cons.X family of functions
Cons.list?
Cons.List  C
Cons.len
Cons.app
Cons.rev
Cons.rev_  app
Cons.concat
Cons.to_  vec
Cons.into_  vec
Cons.from_  vec
Cons.foreach
Cons.foldr
Cons.foldl
Cons.map
Cons.filter
Cons.andmap
Cons.ormap
Cons.sort
7.3 Class Cons  Builder
«Cons  Builder».cons
«Cons  Builder».snoc
«Cons  Builder».take
7.8

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 car
    let cdr: Cons.list?

The end of the linked list must be marked with None.

procedure

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

Constructs a cons struct.

procedure

cons?(AnyC) -> bool?

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

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.

procedure

Cons.ListC[contract?]: contract?

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

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(FunC[AnyC, NoneC], Cons.list?): NoneC

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

procedure

Cons.foldr[Y](FunC[AnyC, Y, Y], Y, Cons.list?): Y

Traverses a list from right to left, accumulating a result using the given function. O(n × f) time and O(n) space.

procedure

Cons.foldl[Y](FunC[Y, AnyC, Y], Y, Cons.list?): Y

Traverses a list from left to right, accumulating a result using the given function. O(n × f) time and O(1) space.

procedure

Cons.map(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).

procedure

Cons.filter(FunC[AnyC, AnyC], Cons.list?): Cons.list?

Filters a list by applying a predicate to each element. O(n) time and O(n) space.

procedure

Cons.andmap(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.

procedure

Cons.ormap(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.

procedure

Cons.sort[T](FunC[T, T, AnyC], Cons.listC[T]): Cons.list?

Sorts a list producing a new list, and not modifying the input list. Uses the given function as a "less than" comparison to determine the order. O(n²).

7.3 Class ConsBuilder

The ConsBuilder class provides a convenient way to build lists from front to back.

The ConsBuilder constructor takes no arguments, and starts off building an empty list.

method

«ConsBuilder».cons(AnyC) -> NoneC

Adds the given value to the beginning of the list.

method

«ConsBuilder».snoc(AnyC) -> NoneC

Adds the given value to the end of the list.

method

«ConsBuilder».take() -> Cons.list?

Takes the built list out of this ConsBuilder and returns it, leaving this ConsBuilder empty.