6 Composing Operations🔗ℹ

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 ~. Additionally, a number of general-purpose utilities leveraging generic composition are provided.

6.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. While ID implements some generic interfaces that allow it to be treated as a null value in various contexts (such as generic sequences), it 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/type 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:

6.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.

6.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.

6.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.

6.2 Types🔗ℹ

• map - The function that will be applied to each seed value to produce the values of the resulting sequence.

• gen - The function that will be applied to each seed value to generate the next seed value.

• stop? - The condition applied to the seed value that, when true, terminates the unfold operation. It is specified via the keyword argument #:stop?. If left unspecified, this defaults to false., i.e. the unfold operation does not terminate, and must be used together with a utility like take.

• tail - The function that will be applied to the seed value at the point when the unfold operation terminates (or when it begins, in the case of unfoldr), to produce the tail of the resulting sequence. This attribute is typically used to indicate the type of the resulting sequence, and must be provided via the keyword argument #:tail. If left unspecified, it defaults to (thunk* null), that is, a function that returns null, resulting in the output sequence being a list. If a hash is desired instead, for example, this could be specified as (thunk* (hash)).

• cons - The constructor to be used in creating the resulting sequence, which is provided via the keyword argument #:cons. If left unspecified, this defaults to the generic type constructor, :, so that the type of the resulting sequence is determined by the type of its tail. This value is used in unfoldl and unfoldr but it is ignored in unfold, which produces values lazily using stream-cons instead.

map and gen are the only parameters that are always required, while stop? is only required for unfoldl and unfoldr, but not for unfold (because the former are not lazy and thus require a finite stop condition). tail is usually needed when the desired output sequence is not a list or a stream, and cons is rarely needed since it can usually be inferred from the tail.

6.3 Utilities🔗ℹ

.., ∘, and ..> are deprecated and will be removed in a future version. Use ~ for concatenation, and if you need left-to-right composition for functions, consider using Threading Macros.

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).

Additionally, note that foldl computes values lazily, whereas foldr is not lazy.

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.

All of these operations leverage the generic type constructor : by default, so that a constructor usually need not be provided in the sequencer specification, and the type of the resulting sequence would be inferred from the type of the tail (which defaults to a list).

unfold is essentially the same as unfoldl, except that it returns values lazily (i.e. produces a stream). unfoldl and unfoldr are not lazy.

Whenever a function produces an output of the same type as its input (i.e. in mathematical terms it is a self-map), it has a well-defined notion of "powers." For example, cdr is a self-map on lists, but car is not.