►Rebellion
▼3 Streaming Computations
►3.1 Reducers
On this page:
reducer?
reduce
reduce-all
into-sum
into-product
into-count
into-first
into-last
into-nth
into-index-of
into-index-where
into-any-match?
into-all-match?
into-none-match?
into-for-each
into-max
into-min
into-string
into-line
join-into-string
3.1.1 Reducer Constructors
make-fold-reducer
make-effectful-fold-reducer
make-reducer
reducer-starter
reducer-consumer
reducer-finisher
reducer-early-finisher
3.1.2 Reducer Operators
reducer-map
reducer-filter
reducer-limit
3.1.3 Iteration and Comprehension with Reducers
for/  reducer
for*/  reducer
make-reducer-based-for-comprehensions
3.1.4 Reducer Contracts
reducer/  c
3.1.5 Reducer Chaperones and Impersonators
reducer-impersonate
7.7
  top  ← prev  up  next → 

3.1 Reducers

 (require rebellion/streaming/reducer)
  package: rebellion

A reducer is an object that can combine a (possibly infinite) sequence of elements into a single result value. 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.

procedure

(reducer? v) → boolean?

  v : any/c
A predicate for reducers.

procedure

(reduce red v ...) → any/c

  red : reducer?
  v : any/c
Reduces vs with red, in left-to-right order.

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.

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

value

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

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

Examples:
> (reduce into-sum 1 2 3)

6

> (reduce into-sum)

0

> (reduce-all into-sum (in-range 10000))

49995000

value

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

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

Examples:
> (reduce into-product 2 3 4)

24

> (reduce into-product)

1

> (reduce-all into-product (in-range 1 20))

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:
> (reduce into-count 'a 'b 'c)

3

> (reduce-all into-count "hello world")

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.

Example:
> (reduce-all into-first "hello world")

(present #\h)

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:
> (reduce-all into-last "hello world")

(present #\d)

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:
> (reduce-all (into-nth 8) "hello world")

(present #\r)

> (reduce-all (into-nth 20) "hello world")

#<absent>

> (reduce-all (into-nth 0) "hello world")

(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:
> (reduce-all (into-index-of #\e) "battery")

(present 4)

> (reduce-all (into-index-of #\o) "cat")

#<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:
> (reduce-all (into-index-where char-whitespace?) "hello world")

(present 5)

> (reduce-all (into-index-where char-numeric?) "goodbye world")

#<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:
> (reduce-all (into-any-match? char-whitespace?) "hello world")

#t

> (reduce-all (into-any-match? char-numeric?) "hello world")

#f

> (reduce-all (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:
> (reduce-all (into-all-match? char-alphabetic?) "hello")

#t

> (reduce-all (into-all-match? char-alphabetic?) "hello world")

#f

> (reduce-all (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:
> (reduce-all (into-none-match? char-whitespace?) "hello")

#t

> (reduce-all (into-none-match? char-whitespace?) "hello world")

#f

> (reduce-all (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:
> (reduce-all (into-for-each displayln) (in-range 5))

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 key-function is provided, it is used to extract the compared value from each element. Comparisons are performed with comparator (which defaults to a numeric comparison). If the reduced sequence contains no values, absent is returned by the constructed reducer. When the sequence contains equivalent but distinct maximum or minimum elements, the first of them is returned.

Examples:
> (reduce-all (into-max) (in-range 1 10))

(present 9)

> (reduce-all (into-min) (in-range 1 10))

(present 1)

> (reduce-all (into-max) empty-list)

#<absent>

> (reduce (into-min string<=>) "goodbye" "cruel" "world")

(present "cruel")

 

(define-record-type gemstone (color weight))

 

> (reduce (into-max #:key gemstone-weight)
          (gemstone #:color 'red #:weight 5)
          (gemstone #:color 'blue #:weight 7)
          (gemstone #:color 'green #:weight 3)
          (gemstone #:color 'yellow #:weight 7))

(present (gemstone #:color 'blue #:weight 7))

value

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

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

Examples:
> (reduce into-string #\h #\e #\l #\l #\o)

"hello"

> (reduce-all into-string (list #\a #\b #\c))

"abc"

value

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

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

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

"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:
> (reduce-all (join-into-string " + ")
              (sequence-map number->immutable-string (in-range 1 10)))

"1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9"

> (reduce-all (join-into-string ", " #:before-last ", and ")
              (sequence-map number->immutable-string (in-range 1 10)))

"1, 2, 3, 4, 5, 6, 7, 8, and 9"

> (reduce-all (join-into-string ", " #:before-first "func(" #:after-last ")")
              (sequence-map number->immutable-string (in-range 1 10)))

"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:

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)))
> (reduce-all into-reversed-list (in-range 5 25))

'(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))
> (reduce-all into-list (in-range 5 25))

'(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:

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))
> (reduce into-small-immutable-vector 1 2 3)

'#(1 2 3)

> (reduce-all into-small-immutable-vector (in-naturals))

'#(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))
> (reduce into-total-letters "the" "quick" "brown" "fox")

16

> (define stringly-typed-into-sum
    (reducer-map into-sum
                 #:domain string->number
                 #:range number->string))
> (reduce stringly-typed-into-sum "12" "5" "42" "17")

"76"

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.

Examples:
> (define numbers-into-sum (reducer-filter into-sum number?))
> (reduce numbers-into-sum 1 'a 2 3 'b 'c 'd 4 'e 5)

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:
> (reduce-all (reducer-limit into-string 5) "hello world")

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

 

> (reduce into-string-append "Red" "Blue" "Green")

"RedBlueGreen"

> (reduce into-string-append "Red" 42 "Green")

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

 

> (reduce-all into-list/printing (in-range 5))

Reducing 0

Reducing 1

Reducing 2

Reducing 3

Reducing 4

Reduction finished, result is (0 1 2 3 4)

'(0 1 2 3 4)

  top  ← prev  up  next →