4 Algebraic Operators

Generic algebraic operators for composing data.

The built-in operators + and * operate on numbers specifically. Often, however, we are interested in performing operations "similar" to these for datatypes that aren’t numbers, for which we would resort to type-specific operators like append for lists.

This module generalizes the standard algebraic operators to work on any type that supports a "canonical" notion of addition, multiplication, or concatenation. This allows our intuitions about addition and other forms of composition to extend over all appropriate types via the use of the common generic operators +, * and ...

4.1 Interfaces

This module provides three generic interfaces – gen:appendable, gen:multipliable, and gen:addable. These are meant to represent the canonical "idea" of the operations of concatenation, multiplication and addition, respectively, whose behavior may be customized for each type via these generic interfaces, and used via the common operators .. (concatenation), * (multiplication), and + (addition).

In order to support generic composition seamlessly, all of the composition interfaces support a generic (rather than type- and operation-specific) identity value that is employed in cases where type information is not available.

In the event no operands are received in the course of a computation, the result of composition would be ID, which would not be a usable result in utilities that are expecting a specific type such as a string. In such cases, the result could be converted to the expected type using one of the transformers in relation/transform such as ->string. If you are not using a built-in type but rather a custom type, however, you could use the following more general utility to "reify" the generic identity value to a type of your choosing:

4.1.1 Concatenation

• numbers

• strings

• byte strings

• lists

• vectors

• sets

• sequences

• procedures

To implement this interface for custom types, the following methods need to be implemented, unless the type already implements another interface for which a default implementation exists for gen:appendable (such as gen:sequence) and if more specific handling is not needed for the custom type.

In addition to providing a definition of concatenation appropriate to the type, implementations of this method must also handle the special value ID in the following way: if the operand b is eq? to ID, then the result of the function must be a.

Providing an implementation for this method is optional, and most types would usually not define an inverse for an append-like operation. That is, in mathematical terms, append-like operations typically form an algebraic semigroup or monoid rather than a group.

4.1.2 Multiplication

• numbers

Since numbers are the only common type for which the multiply operation is defined, this interface is present mostly for uniformity, being leveraged by utilities like fold, and of course also for use in custom types.

To implement this interface for custom types, the following methods need to be implemented:

In addition to providing a definition of multiplication appropriate to the type, implementations of this method must also handle the special value ID in the following way: if the operand b is eq? to ID, then the result of the function must be a.

Providing an implementation for this method is optional; a multiply operation need not admit an inverse, for instance, for a custom integer type, multiplication would not define an inverse since multiplicative inverses for numbers would be rational numbers, rather than integers, thus being excluded by the "same type" requirement above.

4.1.3 Addition

• numbers

• vectors

To implement this interface for custom types, the following methods need to be implemented:

In addition to providing a definition of addition appropriate to the type, implementations of this method must also handle the special value ID in the following way: if the operand b is eq? to ID, then the result of the function must be a.

Providing an implementation for this method is required; an addition operation must admit an inverse. That is, in mathematical terms, addition-like operations are expected to form an algebraic group.

4.2 Utilities

With folding operations there are two parameters that one may wish to tweak. The first is the direction of the fold, either left or right, for which one may use either foldl or foldr. The second is the order in which arguments are supplied to the folding function f, which may be controlled by the keyword argument #:order, with a value of 'abb corresponding to the accumulator always being passed last, consistent with Racket’s built-in foldl, and a value of 'bab corresponding to the accumulator always being passed first, consistent with the version of foldl found in data/collection and also in some other functional languages like Haskell.

In many common cases, modulating the folding direction and/or the argument order does not make a difference to the result. Specifically, in those cases where the operation is commutative and closed, it doesn’t matter whether you use foldl or foldr, or whether you use argument order 'abb or 'bab. The result would be the same. However, in cases where the operation is not closed, argument order becomes significant. As a general guideline, choose between foldl and foldr in cases where the operation is not commutative (a relatively common case, such as string concatenation), and between the two argument orders in cases where the operation isn’t closed (a less common case, such as type constructors).

foldl is equivalent to calling fold with #:direction 'left, and foldr is equivalent to calling fold with #:direction 'right. fold/steps is equivalent to calling fold with #:with-steps? #t.