3.1 Reducers

8.12

3.1 Reducers🔗ℹ

A reducer is an object that can combine a (possibly infinite) sequence of elements into a single result value. Reducers form the final step of a stream pipeline and specify how the output elements of the pipeline should be collected into a final result. To use a reducer, pass it as the #:into argument to the transduce function.

Example:

> (transduce (in-range 0 10)
(filtering even?)
#:into into-list)
'(0 2 4 6 8)

Reducers are state machines; performing a reduction involves starting the reducer to get an initial state, then consuming elements one at a time to transform the current state into a new, updated state. When no more elements are available, the reducer’s finisher is called to transform the final state into a result value. Optionally, a reducer may terminate the reduction early, before the sequence is fully consumed. This process is known as the reduction protocol: see make-reducer for a more concrete description of the protocol.

procedure
(reducer? v) → boolean?
v : any/c

A predicate for reducers.

value
into-sum : (reducer/c number? number?)

A reducer that reduces a sequence of numbers into their sum with +.

Examples:

> (transduce (list 1 2 3) #:into into-sum)
6
> (transduce empty-list #:into into-sum)
0
> (transduce (in-range 10000) #:into into-sum)
49995000

value
into-product : (reducer/c number? number?)

A reducer that reduces a sequence of numbers into their product with *.

Examples:

> (transduce (list 2 3 4) #:into into-product)
24
> (transduce empty-list #:into into-product)
1
> (transduce (in-range 1 20) #:into into-product)
121645100408832000

value
into-count : (reducer/c any/c number?)

A reducer that ignores the specific elements it reduces and returns only a count of how many elements were reduced.

Examples:

> (transduce (list 'a 'b 'c) #:into into-count)
3
> (transduce "hello world" #:into into-count)
11

value
into-first : (reducer/c any/c option?)

A reducer that returns an option of the first element it reduces, or absent if the reduced sequence is empty. If you know the reduced sequence will never contain more than one element, prefer using into-option so that a sequence with unexpectedly many elements results in a contract error. Furthermore, if you know the sequence will always contain exactly one element then prefer using into-only-element.

Example:

> (transduce "hello world" #:into into-first)
(present #\h)

value
nonempty-into-first : reducer?

A reducer that returns the first element it reduces. If the reduced sequence is empty, a contract error is raised.

Examples:

> (transduce "hello world" #:into nonempty-into-first)
#\h
> (transduce "" #:into nonempty-into-first)
nonempty-into-first: expected at least one element

value
into-option : (reducer/c any/c option?)

A reducer that reduces sequences of zero or one elements into options. If a reduced sequence has more than one element, a contract error is raised.

Examples:

> (transduce (list 4) #:into into-option)
(present 4)
> (transduce empty-list #:into into-option)
#<absent>
> (transduce (list 4 7) #:into into-option)
into-option: expected at most one element
first element: 4
second element: 7

value
into-only-element : reducer?

A reducer that reduces a sequence of exactly one element into that element. If the reduced sequence is empty, or if the reduced sequence contains multiple elements, a contract error is raised.

Examples:

> (transduce (list 4) #:into into-only-element)
4
> (transduce (list 4 7) #:into into-only-element)
into-only-element: expected exactly one element, but
multiple elements were received
first element: 4
second element: 7
> (transduce empty-list #:into into-only-element)
into-only-element: expected exactly one element, but zero
elements were received

value
into-last : (reducer/c any/c option?)

A reducer that returns an option of the last element it reduces, or absent if the reduced sequence is empty.

Example:

> (transduce "hello world" #:into into-last)
(present #\d)

value
nonempty-into-last : reducer?

A reducer that returns the last element it reduces. If the reduced sequence is empty, a contract error is raised.

Examples:

> (transduce "hello world" #:into nonempty-into-last)
#\d
> (transduce "" #:into nonempty-into-last)
nonempty-into-last: expected at least one element

procedure
(into-nth n) → (reducer/c any/c option?)
n : natural?

Constructs a reducer that returns the nth element it reduces, wrapped in an option value. If the reduced sequence has fewer than n elements, the reducer returns absent.

Examples:

> (transduce "hello world" #:into (into-nth 8))
(present #\r)
> (transduce "hello world" #:into (into-nth 20))
#<absent>
> (transduce "hello world" #:into (into-nth 0))
(present #\h)

procedure
(into-index-of v) → (reducer/c any/c (option/c natural?))
v : any/c

Constructs a reducer that searches the reduced sequence for v and returns an option wrapping the position of v in the sequence. If the reduced sequence does not contain v, then the reducer returns absent.

Examples:

> (transduce "battery" #:into (into-index-of #\e))
(present 4)
> (transduce "cat" #:into (into-index-of #\e))
#<absent>

procedure
(into-index-where pred) → (reducer/c any/c (option/c natural?))
pred : predicate/c

Constructs a reducer that searches the reduced sequence for the first value for which pred returns true, then returns an option wrapping the position of that value. If the reduced sequence does not contain any values satisfying pred, then the reducer returns absent.

Examples:

> (transduce "hello world" #:into (into-index-where char-whitespace?))
(present 5)
> (transduce "hello world" #:into (into-index-where char-numeric?))
#<absent>

procedure
(into-any-match? pred) → (reducer/c any/c boolean?)
pred : predicate/c

Constructs a reducer that searches the reduced sequence for at least one element that satisfies pred, returning true if an element is found and returning false otherwise. If the sequence is empty, then the reducer returns false.

Examples:

> (transduce "hello world" #:into (into-any-match? char-whitespace?))
#t
> (transduce "hello" #:into (into-any-match? char-whitespace?))
#f
> (transduce "" #:into (into-any-match? char-whitespace?))
#f

procedure
(into-all-match? pred) → (reducer/c any/c boolean?)
pred : predicate/c

Constructs a reducer that returns true if every element in the reduced sequence satisfies pred, otherwise false is returned. If the sequence is empty, then the reducer returns true.

Examples:

> (transduce "hello" #:into (into-all-match? char-alphabetic?))
#t
> (transduce "hello world" #:into (into-all-match? char-alphabetic?))
#f
> (transduce "" #:into (into-all-match? char-alphabetic?))
#t

procedure
(into-none-match? pred) → (reducer/c any/c boolean?)
pred : predicate/c

Constructs a reducer that returns true if no element in the reduced sequence satisfies pred, otherwise false is returned. If the sequence is empty, then the reducer returns true.

Examples:

> (transduce "hello" #:into (into-none-match? char-whitespace?))
#t
> (transduce "hello world" #:into (into-none-match? char-whitespace?))
#f
> (transduce "" #:into (into-none-match? char-whitespace?))
#t

procedure
(into-for-each handler) → (reducer/c any/c void?)
handler : (-> any/c void?)

Constructs a reducer that calls handler on each element for its side effects. The reduction result of the returned reducer is always (void).

Example:

> (transduce (in-range 5) #:into (into-for-each displayln))
0
1
2
3
4

procedure
(into-max [comparator #:key key-function])
→ (reducer/c any/c option?)
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values
procedure
(into-min [comparator #:key key-function])
→ (reducer/c any/c option?)
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values

Constructs a reducer that searches the reduced sequence for either the greatest element or the least element, respectively. If the reduced sequence contains no values, absent is returned by the constructed reducer.

Examples:

> (transduce (in-range 1 10) #:into (into-max))
(present 9)
> (transduce (in-range 1 10) #:into (into-min))
(present 1)
> (transduce empty-list #:into (into-max))
#<absent>

Comparisons are performed with comparator (which defaults to a numeric comparison). If key-function is provided, it is used to extract the compared value from each element. When the sequence contains equivalent but distinct maximum or minimum elements, the first of them is returned.

Examples:

> (transduce (list "goodbye" "cruel" "world") #:into (into-min string<=>))
(present "cruel")

(define-record-type gemstone (color weight))
(define gems
  (list
   (gemstone #:color 'red #:weight 5)
   (gemstone #:color 'blue #:weight 7)
   (gemstone #:color 'green #:weight 3)
   (gemstone #:color 'yellow #:weight 7)))

> (transduce gems #:into (into-max #:key gemstone-weight))
(present (gemstone #:color 'blue #:weight 7))

procedure
(nonempty-into-max [ comparator
#:key key-function]) → reducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values
procedure
(nonempty-into-min [ comparator
#:key key-function]) → reducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values

Constructs a reducer that searches the reduced sequence for either the greatest element or the least element, respectively. If the reduced sequence contains no values, a contract error is raised by the constructed reducer.

Examples:

> (transduce (in-range 1 10) #:into (nonempty-into-max))
9
> (transduce (in-range 1 10) #:into (nonempty-into-min))
1
> (transduce empty-list #:into (nonempty-into-max))
nonempty-into-max: expected at least one element

Examples:

> (transduce (list "goodbye" "cruel" "world") #:into (nonempty-into-min string<=>))
"cruel"

(define-record-type gemstone (color weight))
(define gems
  (list
   (gemstone #:color 'red #:weight 5)
   (gemstone #:color 'blue #:weight 7)
   (gemstone #:color 'green #:weight 3)
   (gemstone #:color 'yellow #:weight 7)))

> (transduce gems #:into (nonempty-into-max #:key gemstone-weight))
(gemstone #:color 'blue #:weight 7)

procedure
(into-sorted? [ comparator
#:key key-function
#:descending? descending?
#:strict? strict?])
→ (reducer/c any/c boolean?)
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values
  descending? : boolean? = #false
  strict? : boolean? = #false

Constructs a reducer that determines whether the reduced sequence is sorted in ascending order (or descending order, if descending? is true) according to comparator.

Example:

> (transduce (list 1 2 3 4 5) #:into (into-sorted?))
#t

If key-function is provided, it is applied to each element to extract a key and the keys are compared instead of the elements themselves.

Example:

> (transduce (list "cat" "dog" "horse" "zebra") #:into (into-sorted? #:key string-length))
#t

If strict? is true, the elements must be strictly ascending or descending — that is, the reducer returns false for sequences where adjacent elements are equivalent according to comparator.

Examples:

> (transduce (list 1 2 2 3) #:into (into-sorted?))
#t
> (transduce (list 1 2 2 3) #:into (into-sorted? #:strict? #true))
#f

value
into-string : (reducer/c char? immutable-string?)

A reducer that collects a sequence of individual characters into an immutable string.

Example:

> (transduce (list #\h #\e #\l #\l #\o) #:into into-string)
"hello"

value
into-line : (reducer/c char? immutable-string?)

Like into-string, but stops the reduction as soon as a #\newline character is encountered.

Example:

> (transduce "Haikus are easy\nBut sometimes they don't make sense\nRefrigerator"
#:into into-line)
"Haikus are easy"

procedure
(join-into-string sep
[ #:before-first before-first
#:before-last before-last
#:after-last after-last])
→ (reducer/c immutable-string? immutable-string?)
  sep : immutable-string?
  before-first : immutable-string? = ""
  before-last : immutable-string? = sep
  after-last : immutable-string? = ""

Constructs a reducer that joins a sequence of immutable strings into a single immutable string, in the same manner as string-join.

Examples:

> (transduce (in-range 1 10)
             (mapping number->immutable-string)
             #:into (join-into-string " + "))
"1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9"
> (transduce (in-range 1 10)
             (mapping number->immutable-string)
             #:into (join-into-string ", " #:before-last ", and "))
"1, 2, 3, 4, 5, 6, 7, 8, and 9"
> (transduce (in-range 1 10)
             (mapping number->immutable-string)
             #:into (join-into-string ", " #:before-first "func(" #:after-last ")"))
"func(1, 2, 3, 4, 5, 6, 7, 8, 9)"

3.1.1 Reducer Constructors🔗ℹ

The full reducer interface is captured by the make-reducer constructor, but this is sufficiently more power than most users should need. Three separate constructors are provided, each designed for three different categories of reducers with increasing power and complexity:

make-fold-reducer constructs fold reducers, which can express the same reductions as foldl.
make-effectful-fold-reducer constructs effectful fold reducers, which can express folds where a private, potentially mutable state value is initialized at the start of reduction and converted into a public result value at the end of reduction. Effectful fold reducers are a superset of fold reducers.
make-reducer constructs general reducers, with the full power of the reduction protocol and the ability to terminate the sequence early.

procedure
(make-fold-reducer consumer
init-state
[ #:name name]) → reducer?
  consumer : (-> any/c any/c any/c)
  init-state : any/c
  name : (or/c interned-symbol? #f) = #f

Constructs a fold reducer, the simplest type of reducer. A fold reducer starts each reduction with an initial state of init-state and transforms it into a new state by calling (consumer state element) with each reduced sequence element. When no more elements are available, the state is returned as the reduction result.

Examples:

> (define into-reversed-list
(make-fold-reducer (λ (lst v) (cons v lst)) (list)))
> (transduce (in-range 5 25) #:into into-reversed-list)
'(24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5)

procedure
(make-effectful-fold-reducer consumer
init-state-maker
finisher
[ #:name name]) → reducer?
  consumer : (-> any/c any/c any/c)
  init-state-maker : (-> any/c)
  finisher : (-> any/c any/c)
  name : (or/c interned-symbol? #f) = #f

Constructs an effectful fold reducer, which is like a fold reducer with a private, possibly mutable state. An effectful fold reducer starts each reduction by calling (init-state-maker) to construct an initial state. Elements are consumed in the same way as fold reducers by calling (consumer state element). When no more elements are available, (finisher state) is called to determine the convert the final state into the reduction result.

Examples:

> (define into-list
(make-effectful-fold-reducer (λ (lst v) (cons v lst)) list reverse))
> (transduce (in-range 5 25) #:into into-list)
'(5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24)

procedure
(make-reducer #:starter starter
#:consumer consumer
#:finisher finisher
#:early-finisher early-finisher
[ #:name name]) → reducer?
  starter : (-> (variant/c #:consume any/c #:early-finish any/c))
  consumer : (-> any/c any/c (variant/c #:consume any/c #:early-finish any/c))
  finisher : (-> any/c any/c)
  early-finisher : (-> any/c any/c)
  name : (or/c interned-symbol? #f) = #f

Constructs a reducer that reduces sequences by following the following steps, known as the reduction protocol:

Start the reduction by calling (starter) to create the initial reduction state, which must be a variant tagged as either #:consume or #:early-finish.
If the current state is tagged as #:consume, and the sequence is not empty, call (consumer (variant-value state) element) with the next sequence element to get the updated reduction state. Repeat this step until either no more elements are available or until the reduction state is tagged as #:early-finish.
If the current state is tagged as #:early-finish, call (early-finisher (variant-value state)) to determine the reduction result. Otherwise, call (finisher (variant-value state)) to get the reduction result.

Examples:

> (define-record-type state (vector position))
> (define into-small-immutable-vector
    (make-reducer
     #:starter
     (λ ()
       (variant #:consume
                (state #:vector (make-vector 10 #f)
                       #:position 0)))
     #:consumer
     (λ (st v)
       (define i (state-position st))
       (define vec (state-vector st))
       (vector-set! vec i v)
       (define i* (add1 i))
       (if (< i* 10)
           (variant #:consume (state #:vector vec #:position i*))
           (variant #:early-finish vec)))
     #:finisher
     (λ (st)
       (define vec (state-vector st))
       (define i (state-position st))
       (vector->immutable-vector (vector-copy vec 0 i)))
     #:early-finisher vector->immutable-vector))
> (transduce (list 1 2 3) #:into into-small-immutable-vector)
'#(1 2 3)
> (transduce (in-naturals) #:into into-small-immutable-vector)
'#(0 1 2 3 4 5 6 7 8 9)

procedure
(reducer-starter red)
→ (-> (variant/c #:consume any/c #:early-finish any/c))
  red : reducer?
procedure
(reducer-consumer red)
→ (-> any/c any/c (variant/c #:consume any/c #:early-finish any/c))
  red : reducer?
procedure
(reducer-finisher red) → (-> any/c any/c)
  red : reducer?
procedure
(reducer-early-finisher red) → (-> any/c any/c)
  red : reducer?

Accessors for the functions that implement a reducer. Each accessor corresponds to one of the functions given to make-reducer.

3.1.2 Reducer Operators🔗ℹ

procedure
(reducer-map red [#:domain f #:range g]) → reducer?
  red : reducer?
  f : (-> any/c any/c) = values
  g : (-> any/c any/c) = values

Wraps red to apply f to each sequence element and to apply g to its reduction result. Both f and g default to values.

Examples:

> (define into-total-letters
(reducer-map into-sum #:domain string-length))
> (transduce (list "the" "quick" "brown" "fox") #:into into-total-letters)
16
> (define stringly-typed-into-sum
(reducer-map into-sum #:domain string->number #:range number->string))
> (transduce (list "12" "5" "42" "17") #:into stringly-typed-into-sum)
"76"

procedure
(reducer-zip zip-function subreducer ...) → reducer?
zip-function : procedure?
subreducer : reducer?

Combines subreducers into a single reducer that applies zip-function to the reduction results of the subreducers. The given zip-function must accept as many arguments as there are subreducers. If every subreducer finishes early, the combined reducer finishes early. Note that this allows multiple reducers to reduce a sequence while only iterating the sequence once.

Examples:

(define-tuple-type endpoints (first last))
(define into-endpoints (reducer-zip endpoints nonempty-into-first nonempty-into-last))

> (transduce (list 1 2 3 4 5) #:into into-endpoints)
(endpoints 1 5)

procedure
(reducer-filter red pred) → reducer?
red : reducer?
pred : predicate/c

Wraps red to only reduce sequence elements for which pred returns #t, and ignore elements completely when pred returns #f.

Example:

> (transduce (list 1 'a 2 3 'b 'c 'd 4 'e 5) #:into (reducer-filter into-sum number?))
15

procedure
(reducer-limit red amount) → reducer?
red : reducer?
amount : natural?

Wraps red to only accept at most amount elements before terminating the reduction.

Example:

> (transduce "hello world" #:into (reducer-limit into-string 5))
"hello"

3.1.3 Iteration and Comprehension with Reducers🔗ℹ

syntax
(for/reducer reducer-expr (for-clause ...) body-or-break ... body)

reducer-expr : reducer?

Iterates like for, but the sequence of iterated body results is reduced with reducer-expr.

Example:

> (for/reducer into-sum
               ([char (in-string "aaa0aa00a0aa")])
    (if (char-alphabetic? char)
        1
        -1))
4

syntax
(for*/reducer reducer-expr (for-clause ...) body-or-break ... body)

reducer-expr : reducer?

Iterates like for*, but the sequence of iterated body results is reduced with reducer-expr.

procedure
(make-reducer-based-for-comprehensions reducer-expression)
→
(-> syntax? syntax?) (-> syntax? syntax?)
reducer-expression : syntax?

Returns two syntax transformers suitable for use with define-syntaxes that implement two for-like macros. The returned macros use reducer-expression to iterate like for/reducer and for*/reducer, respectively. Provided at phase 1.

In order to prevent confusion over how many times reducer-expression is expanded and evaluated, strongly prefer using a single identifier for reducer-expression instead of an expression using reducer-map, make-fold-reducer, etc.

Examples:

> (require (for-syntax racket/base))
> (define-syntaxes (for/sum for*/sum)
(make-reducer-based-for-comprehensions #'into-sum))
> (for/sum ([str (in-list (list "apple" "orange" "banana" "grapefruit"))])
(string-length str))
27

3.1.4 Reducer Contracts🔗ℹ

procedure
(reducer/c domain-contract range-contract) → contract?
domain-contract : contract?
range-contract : contract?

A contract combinator for reducers. Returns a contract that enforces that the contracted value is a reducer and wraps the reducer to enforce domain-contract and range-contract. Every reduced element is checked with domain-contract, and every reduction result is checked with range-contract. If both domain-contract and range-contract are chaperone contracts, then the returned contract is as well.

Examples:

(define/contract into-string-append
  (reducer/c string? string?)
  (make-fold-reducer string-append "" #:name 'into-string-append))

> (transduce (list "Red" "Blue" "Green") #:into into-string-append)
"RedBlueGreen"
> (transduce (list "Red" 42 "Green") #:into into-string-append)
into-string-append: contract violation
  expected: string?
  given: 42
  in: an element reduced by
      (reducer/c string? string?)
  contract from:
      (definition into-string-append)
  blaming: top-level
   (assuming the contract is correct)
  at: eval:2:0

3.1.5 Reducer Chaperones and Impersonators🔗ℹ

procedure
(reducer-impersonate reducer
[ #:domain-guard domain-guard
#:range-guard range-guard
#:properties properties
#:chaperone? chaperone?]) → reducer?
  reducer : reducer?
  domain-guard : (or/c (-> any/c any/c) #f) = #f
  range-guard : (or/c (-> any/c any/c) #f) = #f
   properties : (hash/c impersonator-property? any/c #:immutable #t)
= empty-hash
   chaperone? : boolean?
= (and (false? domain-guard) (false? range-guard))

Returns an impersonator of reducer. Whenever the impersonating reducer is used to reduce a sequence, domain-guard is applied to each sequence element it reduces and range-guard is applied to the result of the reducer. Either of domain-guard or range-guard may be skipped by providing #f (the default). All of the impersonator properties in properties are attached to the returned impersonator.

If chaperone? is true, then the returned impersonator is a chaperone. In that case, both domain-guard and range-guard must always return values equal to whatever they’re given. Additionally, if a returned value is an impersonator, it must also be a chaperone.

Examples:

(define (print-domain v)
  (printf "Reducing ~a\n" v)
  v)
(define (print-range v)
  (printf "Reduction finished, result is ~a\n" v)
  v)
(define into-list/printing
  (reducer-impersonate into-list
                       #:domain-guard print-domain
                       #:range-guard print-range))

> (transduce (in-range 5) #:into into-list/printing)
Reducing 0
Reducing 1
Reducing 2
Reducing 3
Reducing 4
Reduction finished, result is (0 1 2 3 4)
'(0 1 2 3 4)

3.1.6 Legacy Reduction APIs🔗ℹ

procedure
(reduce red v ...) → any/c
red : reducer?
v : any/c

Reduces vs with red, in left-to-right order. Use of this function is lightly discouraged in favor of using transduce with a list of values, as it’s simpler and more consistent if transduce is the only entrypoint to the reducer and transducer APIs.

Examples:

> (reduce into-sum 1 2 3 4 5 6 7 8 9 10)
55
> (reduce into-product 2 3 5 7 11 13 17 19 23)
223092870
> (reduce into-count 'a 'b 'c 'd 'e)
5

procedure
(reduce-all red seq) → any/c
red : reducer?
seq : sequence?

Reduces seq with red. The sequence is iterated lazily, so if red terminates the reduction early then the sequence will not be fully traversed. Use of this function is lightly discouraged in favor of using transduce, as it’s simpler and more consistent if transduce is the only entrypoint to the reducer and transducer APIs.

Examples:

> (reduce-all into-sum (in-range 1 100))
4950
> (reduce-all into-product (in-range 1 20))
121645100408832000
> (reduce-all into-count (in-hash-values (hash 'a 1 'b 2 'c 3 'd 4)))
4

1	Base Libraries
2	Data Types
3	Streaming Computations
4	Collections
5	Concurrency
6	Binary Data
7	Module Utilities
8	Other Libraries

3.1.1	Reducer Constructors
3.1.2	Reducer Operators
3.1.3	Iteration and Comprehension with Reducers
3.1.4	Reducer Contracts
3.1.5	Reducer Chaperones and Impersonators
3.1.6	Legacy Reduction APIs