On this page:
6.1 Interfaces
ID
reify
6.1.1 Concatenation
gen:  appendable
appendable?
append
appendable-identity
appendable-inverse
6.1.2 Multiplication
gen:  multipliable
multipliable?
multiply
multipliable-identity
multipliable-inverse
6.1.3 Addition
gen:  addable
addable?
add
addable-identity
addable-inverse
6.2 Types
sequencer
6.3 Utilities
..
..>
*
+
id
inverse
-
/
fold
foldl
foldr
fold/  steps
foldl/  steps
foldr/  steps
unfold
unfoldl
unfoldr
onto
join
sum
product
power
^

6 Composing Operations

 (require relation/composition) package: relation

This module was formerly named relation/algebraic. Any code using relation/algebraic directly should be changed to use relation/composition instead. The former alias is still provided alongside the new one for backwards compatibility, but will be removed in a future version.

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

      6.1.1 Concatenation

      6.1.2 Multiplication

      6.1.3 Addition

    6.2 Types

    6.3 Utilities

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.

value

ID : composition-identity?

The special value ID serves as the generic identity value for all construction and composition operations when the type of the operands is not known. It may appear at intermediate stages of a computation when there isn’t sufficient information to infer a type-specific identity. Any value when composed with ID yields itself. If ID is used as a null constructor, it acts like null, that is, constructing a list.

Examples:
> (+ 5 ID)

5

> (* ID 5)

5

> (+)

(composition-identity)

> (apply * '())

(composition-identity)

> (: 3 ID)

'(3)

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:

procedure

(reify v example [op])  any/c

  v : any/c
  example : any/c
  op : procedure? = ..
"Reifies" a value to a specific type. If the value is already a tangible value (i.e. anything other than ID), then it is returned without modification. Otherwise, the identity value for the desired type (indicated by supplying an arbitrary example of this type) for the operation op is returned. Custom types are expected to implement one of the canonical algebraic operations (e.g. gen:appendable) in order to leverage this utility.

Examples:
> (reify ID 3)

0

> (reify ID 3 *)

1

> (reify ID "cherry")

""

> (reify ID (list))

'()

> (reify "hi" (list))

"hi"

> (reify '(1 2 3) "")

'(1 2 3)

6.1.1 Concatenation

A generic interface that represents any object for which a concatenation or "append-like" operation can be defined. The following built-in types have implementations for gen:appendable:

Examples:
> (.. "hi" " " "there")

"hi there"

> (.. '(1 2 3) '(4 5 6))

'(1 2 3 4 5 6)

procedure

(appendable? v)  boolean?

  v : any/c
Predicate to check if a value may be operated on using the generic append operator, .. or .

Examples:
> (appendable? 3)

#t

> (appendable? #\a)

#f

> (appendable? "cherry")

#t

> (appendable? (list))

#t

> (appendable? (set))

#t

> (appendable? (hash))

#t

> (appendable? (vector))

#t

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.

procedure

(append a b)  appendable?

  a : appendable?
  b : appendable?
A function taking two arguments that composes them in the natural "append-like" operation for the type. Both arguments are expected to be instances of the structure type to which the generic interface is associated (or a subtype of the structure 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.

procedure

(appendable-identity a)  appendable?

  a : appendable?
A function that returns the identity value for the type, for the append operation. The identity value is that value which, when composed with other values of the same type under the append operation, yield those other values as if there had been no composition. The identity value is expected to be an instance of the structure type to which the generic interface is associated (or a subtype of the structure type).

procedure

(appendable-inverse a)  appendable?

  a : appendable?
A function that returns the inverse value for the type, for the append operation. The inverse value is that value which, when composed with other values of the same type under the append operation, yields the identity value. The inverse value is expected to be an instance of the structure type to which the generic interface is associated (or a subtype of the structure type).

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

A generic interface that represents any object for which a "multiplication-like" operation can be defined. The following built-in types have implementations for gen:multipliable:

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.

Example:
> (* 1 2 3 4)

24

procedure

(multipliable? v)  boolean?

  v : any/c
Predicate to check if a value may be operated on using the generic multiplication operator, *.

Examples:
> (multipliable? 3)

#t

> (multipliable? #\a)

#f

> (multipliable? "cherry")

#f

> (multipliable? (list))

#f

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

procedure

(multiply a b)  multipliable?

  a : multipliable?
  b : multipliable?
A function taking two arguments that composes them in the natural "multiplication-like" operation for the type. Both arguments are expected to be instances of the structure type to which the generic interface is associated (or a subtype of the structure type).

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.

A function that returns the identity value for the type, for the multiply operation. The identity value is that value which, when composed with other values of the same type under the multiply operation, yield those other values as if there had been no composition. The identity value is expected to be an instance of the structure type to which the generic interface is associated (or a subtype of the structure type).

procedure

(multipliable-inverse a)  multipliable?

  a : multipliable?
A function that returns the inverse value for the type, for the multiply operation. The inverse value is that value which, when composed with other values of the same type under the multiply operation, yields the identity value. The inverse value is expected to be an instance of the structure type to which the generic interface is associated (or a subtype of the structure type).

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

A generic interface that represents any object for which an "addition-like" (group) operation can be defined. The following built-in types have implementations for gen:addable:

Examples:
> (+ 1 2 3)

6

> (+ #(1 2 3) #(1 2 3) #(1 2 3))

'#(3 6 9)

procedure

(addable? v)  boolean?

  v : any/c
Predicate to check if a value may be operated on using the generic addition operator, +.

Examples:
> (addable? 3)

#t

> (addable? #\a)

#f

> (addable? "cherry")

#f

> (addable? (list))

#f

> (addable? (set))

#f

> (addable? (hash))

#f

> (addable? (vector))

#t

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

procedure

(add a b)  addable?

  a : addable?
  b : addable?
A function taking two arguments that composes them in the natural "addition-like" operation for the type. Both arguments are expected to be instances of the structure type to which the generic interface is associated (or a subtype of the structure type).

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.

procedure

(addable-identity a)  addable?

  a : addable?
A function that returns the identity value for the type, for the add operation. The identity value is that value which, when composed with other values of the same type under the add operation, yield those other values as if there had been no composition. The identity value is expected to be an instance of the structure type to which the generic interface is associated (or a subtype of the structure type).

procedure

(addable-inverse a)  addable?

  a : addable?
A function that returns the inverse value for the type, for the add operation. The inverse value is that value which, when composed with other values of the same type under the add operation, yields the identity value. The inverse value is expected to be an instance of the structure type to which the generic interface is associated (or a subtype of the structure type).

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

struct

(struct sequencer (map gen stop? tail cons))

  map : (-> any/c any/c)
  gen : (-> any/c any/c)
  stop? : (-> any/c boolean?)
  tail : (-> any/c collection?)
  cons : (-> any/c collection? collection?)
A type representing the specification of an unfold operation.

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

procedure

(.. v ...)  appendable?

  v : appendable?

procedure

( v ...)  appendable?

  v : appendable?

procedure

(..> v ...)  appendable?

  v : appendable?
Append the provided values together, using the canonical "append-like" operation on the data based on its type. .. and its alias compose right-to-left, while ..> composes left-to-right. The special value ID serves as the generic identity value for all composition operations when the type of the operands is not known. In particular, this value is the result when no operands are provided.

Examples:
> (.. "hi" " " "there")

"hi there"

> (.. '(1 2 3) '(4 5 6))

'(1 2 3 4 5 6)

> (.. (hash 'a 1 'b 2) (hash 'c 3))

'#hash((c . 3) (b . 2) (a . 1))

> ((.. ->string +) 3 4)

"7"

> ((..> + ->string) 3 4)

"7"

> ( "hi" " " "there")

"hi there"

procedure

(* v ...)  multipliable?

  v : multipliable?
Multiply the provided values together, using the canonical "multiplication-like" operation on the data based on its type. The special value ID serves as the generic identity value for all composition operations when the type of the operands is not known. In particular, this value is the result when no operands are provided.

Example:
> (* 1 2 3 4)

24

procedure

(+ v ...)  addable?

  v : addable?
Add the provided values together, using the canonical "addition-like" operation on the data based on its type. The special value ID serves as the generic identity value for all composition operations when the type of the operands is not known. In particular, this value is the result when no operands are provided.

Examples:
> (+ 1 2 3 4)

10

> (+ #(1 2 3) #(1 2 3) #(1 2 3))

'#(3 6 9)

procedure

(id operation)  procedure?

  operation : procedure?
Produces the "identity" procedure for the given canonical operation, which, when evaluated for a particular value, yields the identity value for that type under the indicated operation.

Examples:
> ((id add) 3)

0

> ((id multiply) 3)

1

> ((id add) #(1 2 -3))

'#(0 0 0)

> ((id append) "hi")

""

> ((id append) '(1 2 3))

'()

> ((id ..) "hi")

""

> ((id +) 3)

0

> ((id *) 3)

1

procedure

(inverse operation)  procedure?

  operation : procedure?
Produces the "inverse" procedure for the given canonical operation, which, when evaluated for a particular value, yields the inverse value for that type under the indicated operation.

Examples:
> ((inverse +) 3)

-3

> ((inverse *) 3)

1/3

> ((inverse +) #(1 2 -3))

'#(-1 -2 3)

procedure

(- v ...)  addable?

  v : addable?
A general version of "subtraction" that works no differently than usual on numbers, but also supports any other group type, for instance, vectors. The result is computed by adding the first supplied value to the inverse of every subsequent value. If only one argument is provided, then it simply returns the additive inverse.

Examples:
> (- 5 3)

2

> (- #(3 3 3) #(0 1 0) #(0 0 2))

'#(3 2 1)

> (- 5)

-5

procedure

(/ v ...)  multipliable?

  v : multipliable?
A general version of "division" that works no differently than usual on numbers, but also supports any other multipliable type. The result is computed by multiplying the first supplied value with the inverse of every subsequent value. If only one argument is provided, then it simply returns the multiplicative inverse.

Examples:
> (/ 5 3)

5/3

> (/ 5)

1/5

procedure

(fold f    
  seqs    
  [#:into base    
  #:order order    
  #:direction direction    
  #:with-steps? with-steps?])  any/c
  f : procedure?
  seqs : (listof (sequenceof any/c))
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb
  direction : (one-of/c 'left 'right) = 'right
  with-steps? : boolean? = #f

procedure

(foldl f    
  seqs    
  [#:into base    
  #:order order    
  #:with-steps? with-steps?])  any/c
  f : procedure?
  seqs : (listof (sequenceof any/c))
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb
  with-steps? : boolean? = #f

procedure

(foldr f    
  seqs    
  [#:into base    
  #:order order    
  #:with-steps? with-steps?])  any/c
  f : procedure?
  seqs : (listof (sequenceof any/c))
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb
  with-steps? : boolean? = #f
Similar to foldl and foldr, but infers the relevant identity element where possible and uses it as the base value, if none is provided. The identity element is determined by considering the first element of the input sequence seqs (or of the first input sequence, if multiple sequences are provided) together with the given operation f.

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.

Examples:
> (fold + '(1 2 3 4))

10

> (fold * '(1 2 3 4))

24

> (fold .. '("hi" " " "there"))

"hi there"

> (foldr + '(1 2 3 4))

10

> (foldl + '(1 2 3 4))

10

> (foldr + '(1 2 3 4) #:order 'bab)

10

> (foldl + '(1 2 3 4) #:order 'bab)

10

> (foldr .. '("hi" " " "there"))

"hi there"

> (foldl .. '("hi" " " "there"))

"there hi"

> (foldr cons '(1 2 3) #:into '() #:order 'abb)

'(1 2 3)

> (foldl cons '(1 2 3) #:into '() #:order 'abb)

'(3 2 1)

> (foldr cons '(1 2 3) #:into '() #:order 'bab)

'(((() . 3) . 2) . 1)

> (foldl cons '(1 2 3) #:into '() #:order 'bab)

'(((() . 1) . 2) . 3)

procedure

(fold/steps f    
  seqs    
  [#:into base    
  #:order order    
  #:direction direction])  any/c
  f : (-> any/c any/c any/c)
  seqs : (listof (sequenceof any/c))
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb
  direction : (one-of/c 'left 'right) = 'right

procedure

(foldl/steps f    
  seqs    
  [#:into base    
  #:order order])  any/c
  f : (-> any/c any/c any/c)
  seqs : (listof (sequenceof any/c))
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb

procedure

(foldr/steps f    
  seqs    
  [#:into base    
  #:order order])  any/c
  f : (-> any/c any/c any/c)
  seqs : (listof (sequenceof any/c))
  base : any/c = undefined
  order : (one-of/c 'abb 'bab) = 'abb
Similar to foldl/steps, but, like fold, infers the relevant identity element where possible and uses it as the base value, if none is provided. foldl/steps is equivalent to calling fold/steps with #:direction 'left, and foldr/steps is equivalent to calling fold/steps with #:direction 'right.

Examples:
> (->list (fold/steps + '(1 2 3 4)))

'(0 4 7 9 10)

> (->list (foldr/steps + '(1 2 3 4)))

'(0 4 7 9 10)

> (->list (foldl/steps + '(1 2 3 4)))

'(0 1 3 6 10)

> (->list (foldr/steps * '(1 2 3 4)))

'(1 4 12 24 24)

> (->list (foldl/steps * '(1 2 3 4)))

'(1 1 2 6 24)

> (->list (foldr/steps .. '("hi" " " "there")))

'("" "there" " there" "hi there")

> (->list (foldl/steps .. '("hi" " " "there")))

'("" "hi" " hi" "there hi")

procedure

(unfold seqr seed)  stream?

  seqr : sequencer?
  seed : any/c

procedure

(unfoldl seqr seed)  collection?

  seqr : sequencer?
  seed : any/c

procedure

(unfoldr seqr seed)  collection?

  seqr : sequencer?
  seed : any/c
Similar to unfold and unfold-right, but generic versions that can produce any kind of collection rather than only a list. These also expect the functions specifying the unfolding operation to be included in a sequencer rather than provided individually.

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.

Examples:
> (define naturals (unfold (sequencer values add1) 0))
> (->list (take 10 naturals))

'(0 1 2 3 4 5 6 7 8 9)

> (unfoldl (sequencer sqr add1 #:stop? (λ (x) (> x 10))) 1)

'(1 4 9 16 25 36 49 64 81 100)

> (unfoldr (sequencer sqr sub1 #:stop? zero?) 10)

'(1 4 9 16 25 36 49 64 81 100)

> (unfoldl (sequencer car cdr #:stop? null?) '(h e l l o))

'(h e l l o)

> (unfoldr (sequencer car cdr #:stop? null?) '(h e l l o))

'(o l l e h)

> (define fibs (unfold (sequencer sum
                                  (match-lambda
                                    [(list a b) (list b (+ a b))]))
                       (list 0 1)))
> (->list (take 10 fibs))

'(1 2 3 5 8 13 21 34 55 89)

> (define symbol+1 (..> ->char ->number add1 ->char ->symbol))
> (unfoldl
    (sequencer values
               (λ (x)
                 (cons (symbol+1 (car x))
                       (add1 (cdr x))))
               #:stop? (λ (x) (> (cdr x) 10))
               #:tail (thunk* (hash)))
    '(a . 1))

'#hash((c . 3) (b . 2) (a . 1) (g . 7) (f . 6) (e . 5) (d . 4) (j . 10) (i . 9) (h . 8))

procedure

(onto fs v ...)  sequence?

  fs : (sequenceof procedure?)
  v : any/c
A kind of "dual" to the usual map operation where we map values under a function, onto instead maps functions onto a value. Specifically, this applies each function in the input sequence of functions to the provided arguments, independently, lazily yielding a corresponding sequence of results. Each of the input functions must have an arity that accepts the provided number of arguments.

This utility was formerly known as gather. It is still provided under that name for backwards compatibility, but the old name will be removed in a future version. The new name was chosen to match a similar utility found in the Bel dialect of Lisp.

Examples:
> (->list (onto (list add1 sub1 ->string) 0))

'(1 -1 "0")

> (->list (onto (list + * min max) 7 6 9))

'(22 378 6 9)

> (define (conjoin . fs)
    (.. all? (curry onto fs)))
> ((conjoin positive? even? integer?) 4)

#t

> (define (n·xⁿ [n 0])
    (stream-cons (.. (curry * n)
                     (curryr expt n))
                 (n·xⁿ (add1 n))))
> (->list (take 10 (onto (n·xⁿ) 3)))

'(0 3 18 81 324 1215 4374 15309 52488 177147)

> (->list (take 10 (onto (map .. (repeat ->string) (n·xⁿ)) 3)))

'("0" "3" "18" "81" "324" "1215" "4374" "15309" "52488" "177147")

procedure

(join vs)  appendable?

  vs : (sequenceof appendable?)
Equivalent to (apply .. vs), this stitches together a sequence containing elements of any appendable type, for instance, strings, lists, or procedures. This function is sometimes called concatenate.

Examples:
> (join (list "hello" " " "there"))

"hello there"

> (join (stream '(1 2 3) '(4 5 6)))

'(1 2 3 4 5 6)

> (join (list number->string add1 sqr))

#<procedure:composed>

> (join (list 1 2 3 4))

10

> (join (list #(1 2 3) #(1 2 3) #(1 2 3)))

'#(1 2 3 1 2 3 1 2 3)

> (join (list (stream 1 2 3) (stream 1 2 3) (stream 1 2 3)))

#<stream>

procedure

(sum vs)  addable?

  vs : (sequenceof addable?)
Equivalent to (apply + vs), this supports numbers in the usual way, but also supports any other addable type, for instance, vectors.

Examples:
> (sum (list 1 2 3 4))

10

> (sum (list #(1 2 3) #(1 2 3) #(1 2 3)))

'#(3 6 9)

procedure

(product vs)  multipliable?

  vs : (sequenceof multipliable?)
Equivalent to (apply * vs), this supports numbers in the usual way, but also supports any other multipliable type.

Example:
> (product (list 1 2 3 4))

24

procedure

(power v n [op])  any/c

  v : any/c
  n : integer?
  op : procedure? = ..

procedure

(^ v n)  any/c

  v : any/c
  n : integer?
Compose v with itself n times with the op operation. If n is negative, the result is the inverse of the value computed with a positive exponent. This generalizes the idea of a numeric "power" to any type and composing operation. ^ is a right-curried form of power, useful in cases where we want to abstract over the numeric power n rather than the value v, for append-like compositions specifically (such as function composition).

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.

Examples:
> ((power add1 3) 5)

8

> (power "abc" 5)

"abcabcabcabcabc"

> (power 2 3)

6

> (power 2 3 *)

8

> (power 2 -3 *)

1/8

> (power 2 -3 +)

-6

> (((^ 3) add1) 4)

7

> (->list (((^ 3) rest) (list 1 2 3 4 5 6 7 8 9 10)))

'(4 5 6 7 8 9 10)