2019-10-07

# CL-ALGEBRAIC-DATA-TYPE

by Robert Smith

CL-ALGEBRAIC-DATA-TYPE, or ADT, is a library for defining algebraic data types in a similar spirit to Haskell or Standard ML, as well as for operating on them.

We can define ADTs using `defdata`:

``````(adt:defdata maybe
(just t)
nothing)``````

which will define a new type `maybe`, with a unary constructor `just`, and a nullary constructor `nothing`. The `t` represents the data type of that field.

``````> (just 5)
#.(JUST 5)
> nothing
#.NOTHING``````

Note that the `#.` are printed so that they can be read back. This allows them to be used literally in quoted lists, for example.

``````> '(#.(just 1) #.nothing)
(#.(JUST 1) #.NOTHING)
> (typep (first *) 'maybe)
T``````

If this is annoying to you, you can set the variable `adt:*print-adt-readably*` to `nil`.

We can define our own version of a list via

``````(adt:defdata liszt
(kons t liszt)
knil)``````

which defines the binary constructor `kons` and the nullary constructor `knil`.

``````> (kons 1 (kons 2 knil))
#.(KONS 1 #.(KONS 2 #.KNIL))``````

At the end we will define `kar` and `kdr`.

For efficiency, we might specify the types more exactly. For a `point` type that supports rectangular and polar coordinates, which is also mutable, we might have:

``````(adt:defdata (point :mutable t)
(rectangular float float)
(polar float float))``````

The `:mutable` option signifies that the data is mutable.

When we have constructed a value, we can extract data out of it using `match`:

``````> (let ((pt (rectangular 1.0 2.0)))
((rectangular x y) (+ x y))
((polar _ _) nil)))
3.0``````

If we did not include the `polar` case, we would get a warning.

``````> (let ((pt (rectangular 1.0 2.0)))
((rectangular x y) (+ x y))))
; caught WARNING:
;   Non-exhaustive match. Missing cases: (POLAR)
3.0``````

We can also specify a fall-through:

``````> (let ((pt (rectangular 1.0 2.0)))
((rectangular x y) (+ x y))
(_ nil)))
3.0``````

Since `point` is mutable, we can efficiently modify its fields using `set-data`.

``````> (defun mirror-point! (pt)

> (let ((pt (rectangular 1.0 2.0)))
(mirror-point! pt)
((rectangular x y) (format t "point is (~A, ~A)" x y))
(_ nil))``````

will print `point is (2.0, 1.0)`.

See examples.txt for examples.

Q. How do we define `kar` and `kdr` for `liszt`?

A. Easy.

``````(defun kar (l)
((kons a _) a)
(knil knil)))

(defun kdr (l)
((kons _ b) b)
(knil knil)))``````

Q. Can I get the constructors dynamically for a particular ADT?

A. Yes. You can get the constructors and associated arity by calling the `get-constructors` function, which will return a list of `(<constructor> <arity>)` pairs. For example, given the `liszt` example above, we have

``````> (adt:get-constructors 'liszt)
((KONS 2) (KNIL 0))
T``````

The second value `t` represents the fact that the ADT is known and exists.

Q. I have an ADT defined, and I'd like to extend it with another ADT. How can I do that?

A. You can define a new ADT which includes another one. For example, consider the following Boolean ADT.

``````(adt:defdata bool
true
false)``````

Suppose you wanted to extend this to have a "fuzzy" option, a probability between true and false, specifically a `real` between `0` and `1` exclusive. We can create a `fuzzy-bool` which includes the `bool` type, as well as a unary `fuzzy` constructor. This is done by the `:include` option to `defdata`.

``````(adt:defdata (fuzzy-bool :include bool)
(fuzzy (real (0) (1))))``````

Note that `true` and `false` are constructors for both `bool` and `fuzzy-bool`, as we can see with `get-constructors`.

``````> (adt:get-constructors 'bool)
((TRUE 0) (FALSE 0))
T
((TRUE 0) (FALSE 0) (FUZZY 1))
T``````