## LispKit Datatype

Library `(lispkit datatype)`

implements algebraic datatypes for LispKit. It provides the following functionality:

`define-datatype`

creates a new algebraic datatype consisting of a type test predicate and a number of variants. Each variant implicitly defines a constructor and a pattern.`define-pattern`

introduces a new pattern and constructor for an existing datatype variant.`match`

matches a value of an algebraic datatype against patterns, binding pattern variables and executing the code of the first case whose pattern matches the value.

### Usage

Here is an example of a datatype defining a tree for storing and finding elements:

```
(define-datatype tree tree?
(empty)
(node left element right) where (and (tree? left) (tree? right)))
```

The datatype `tree`

defines a predicate `tree?`

for checking whether a value is of type `tree`

. In addition, it defines two variants with corresponding constructors `empty`

and `node`

for creating values of type `tree`

. Variant `node`

defines an invariant that prevents nodes from being constructed unless `left`

and `right`

are also trees.

The following line defines a new tree:

```
(define t1 (node (empty) 4 (node 7 (empty) (empty))))
```

Using `match`

, values like `t1`

can be deconstructed using pattern matching. The following function `elements`

shows how to collect all elements from a tree in a list:

```
(define (elements tree)
(match tree
((empty) ())
((node l e r) (append (elements l) (list e) (elements r)))))
```

`match`

is a special form which takes a value of an algebraic datatype and matches it against a list of cases. Each case defines a pattern and a sequence of statements which get executed if the pattern matches the value.

Cases can also optionally define a guard which is a boolean expression that gets executed if the pattern of the case matches a value. Only if the guard evaluates to true, the statements of the case get executed. Otherwise, pattern matching continues. The following function `insert`

demonstrates this functionality:

```
(define (insert tree x)
(match tree
((empty)
(node (empty) x (empty)))
((node l e r) where (< x e)
(node (insert l x) e r))
((node l e r)
(node l e (insert r x)))))
```

A new tree `t2`

, with two new elements inserted, can be created like this:

```
(define t2 (insert (insert t1 2) 9))
```

If a pattern is used frequently containing a lot of boilerplate, it is possible to define a shortcut using the `define-pattern`

syntax:

```
(define-pattern (single x)
(node (empty) x (empty)))
```

With this declaration, it is possible to use `single`

in patterns. The following example also shows that it is possible to use `else`

for defining a fallback case, if no other pattern is matching.

```
(match t
((empty) #f)
((single x) x)
(else (error "two many elements")))
```

`single`

can also be used as a constructor for creating trees with a single element:

```
(single 6)
```

An advanced feature of `match`

is the usage of pattern alternatives in a single case of a `match`

construct. This can be achieved using the `or`

form on the top level of a pattern:

```
(define (has-many-elements tree)
(match tree
((or (empty) (single _)) #f)
(else #t)))
```

The underscore in the `(single _)`

subpattern is a wildcard that matches every value and that does not bind a new variable.

### API

**(define-datatype type (constr arg ...) ...)** [syntax]

**(define-datatype**

*type pred (constr arg ...) ...*)**(define-datatype**

*type pred (constr arg ...)*where*condition*..._)Defines a new datatype with a given number of datatype variants. The definition requires the symbol *type* denoting the new type, an optional symbol *pred* which gets bound to a type test function for testing whether a value is an instance of this type, and a list of constructors of the form *(constr arg1 arg2 ...)* where *constr* is the constructor and *arg1*, *arg2*, ... are parameter names of the constructor. A constructor can be annotated with an invariant for defining requirements the parameters need to meet. This is done via clause `where`

*expr* succeeding the constructor declaration. *condition* is a boolean expression which gets checked when the constructor gets invoked.

**(define-pattern (constr arg ...) (impl expr ...))** [syntax]

Defines a new pattern *(constr arg ...)* which specializes an existing pattern *(impl expr ...)*. Such custom patterns can be used in pattern matching expressions as well as constructors for defining values of an algebraic datatype.

**(match expr case ...)** [syntax]

**(match**

*expr case ...*(else*stat ...*))`match`

provides a mechanism for decomposing values of algebraic datatypes via pattern matching. A `match`

construct takes a value *expr* to pattern match on, as well as a sequence of cases. Each case consists of pattern alternatives, an optional guard, and a sequence of statements:

```
case = '(' patterns stat ... ')'
| '(' patterns 'where' condition stat ... ')'
patterns = pattern
| '(' 'or' pattern ... ')'
pattern = '_' -- wildcard
| variable -- variable
| ',' expr -- value (result of evaluating expr)
| pattern 'as' variable -- pattern bound to variable
| '(' constr pattern ... ')' -- variant pattern
```

`match`

iterates through the cases and executes the sequence of statements of the first case whose pattern is matching `expr`

and whose guard evaluates to true. The value returned by this sequence of statements is returned by `match`

.