colon-equals: Define a new data type from a sequence of constructors.
In pmatch: Pattern Matching

Description Usage Arguments Details Examples

This assignment operator introduces a domain-specific language for specifying new types. Types are defined by the ways they can be constructed. This is provided as a sequence of |-separated constructors, where a constructor is either a constant, i.e., a bare symbol, or a function.

1	":="(data_type, constructors)

`data_type`	The name of the new data type. Should be given as a bare symbol.
`constructors`	A list of `\|`-separated constructor specifications.

We can construct an enumeration like this:

numbers := ONE | TWO | THREE

This will create the type numbers and three constants, ONE, TWO, and THREE that can be matched against using the cases function

x <- TWO cases(x, ONE -> 1, TWO -> 2, THREE -> 3)

Evaluating the cases function will compare the value in x against the three patterns and recognize that x holds the constant TWO and it will then return 2.

With function constructors we can create more interesting data types. For example, we can create a linked list like this

linked_list := NIL | CONS(car, cdr : linked_list)

This expression defines constant NIL and function CONS. The function takes two arguments, car and cdr, and requires that cdr has type linked_list. We can create a list with three elements, 1, 2, and 3, by writing

CONS(1, CONS(2, CONS(3, NIL)))

and we can, e.g., test if a list is empty using

cases(lst, NIL -> TRUE, CONS(car,cdr) -> FALSE)

A special pattern, otherwise,can be used to capture all patterns, so the emptiness test can also be written

cases(lst, NIL -> TRUE, otherwise -> FALSE)

Arguments to a constructor function can be typed. To specify typed variables, we use the :-operator. The syntax is then var : type. The type will be checked when you construct a value using the constructor.

linked_list := NIL | CONS(car, cdr : linked_list)
lst <- CONS(1, CONS(2, CONS(3, NIL)))
len <- function(lst, acc = 0) {
    cases(lst,
          NIL -> acc,
          CONS(car,cdr) -> len(cdr, acc + 1))
}
len(lst)

list_sum <- function(lst, acc = 0) {
    cases(lst,
          NIL -> acc,
          CONS(car,cdr) -> list_sum(cdr, acc + car))
}
list_sum(lst)