## cl-algebraic-data-type

2024-10-12

A library for algebraic data types.

### Author

### License

# 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))) (adt:match point pt ((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))) (adt:match point pt ((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))) (adt:match point pt ((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) (adt:with-data (rectangular x y) pt (adt:set-data pt (rectangular y x)))) > (let ((pt (rectangular 1.0 2.0))) (mirror-point! pt) (adt:match 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.

## Frequently Asked Questions

**Q.** How do we define `kar`

and `kdr`

for `liszt`

?

**A.** Easy.

`(defun kar (l) (adt:match liszt l ((kons a _) a) (knil knil))) (defun kdr (l) (adt:match liszt 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 > (adt:get-constructors 'fuzzy-bool) ((TRUE 0) (FALSE 0) (FUZZY 1)) T`

**Q.** Can we do parametric ADTs like I can in Haskell?

**A.** There is no support for it because Lisp doesn't have any useful
notion of definable parametric types that aren't aliases of another
existing parametric type.

**Q.** Why doesn't deeper pattern matching work?

**A.** It's not implemented, but it could be implemented for fields
which are themselves algebraic data types. Patches welcome!