3.2 Transducers

7.7

3.2 Transducers

(require rebellion/streaming/transducer)
	package: rebellion

A transducer is an object that can incrementally transform one (potentially infinite) sequence of elements into another sequence. Transducers are state machines; performing a transduction involves starting the transducer to get an initial state, then repeatedly updating that state by either consuming an element from the input sequence or by emitting an element to the output sequence. When the input sequence is exhausted, the transducer enters a half closed state where it may emit more output elements but it will never consume more input elements. When the transducer stops emitting elements, its finisher is called to clean up any resources held in the final transduction state. Optionally, a transducer may half close early, before the input sequence is fully consumed.

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

A predicate for transducers.

procedure
(transduce seq trans ... #:into red) → any/c
  seq : sequence?
  trans : transducer?
  red : reducer?

Executes a transduction pipeline, alternatively called a stream pipeline, which transforms the source seq with a series of intermediate operations — represented by the trans arguments — then reduces the transformed sequence with red.

Example:

> (transduce (in-range 1 20)
             (filtering even?)
             (mapping number->immutable-string)
             #:into (join-into-string ", "))
"2, 4, 6, 8, 10, 12, 14, 16, 18"

procedure
(in-transducing seq trans) → sequence?
seq : sequence?
trans : transducer?

Lazily transduces seq with trans, returning a sequence that, when iterated, passes the elements of seq to trans as inputs and uses the emitted outputs of trans as the wrapper sequence’s elements.

procedure
(into-transduced trans ... #:into red) → reducer?
trans : transducer?
red : reducer?

Combines red with each trans, returning a new reducer that, when reducing a sequence, first passes the elements through the given chain of transducers. The outputs of the last trans are sent to red as inputs.

Examples:

(define into-first-ten-letters
  (into-transduced (filtering char-alphabetic?)
                   (mapping char-downcase)
                   (taking 10)
                   #:into into-string))

> (transduce "The quick brown fox" #:into into-first-ten-letters)
"thequickbr"

3.2.1 Element-Transforming Transducers

procedure
(mapping f) → transducer?
f : (-> any/c any/c)

Constructs a transducer that applies f to input elements and emits the returned result downstream.

Example:

> (transduce (in-range 1 10)
(mapping (λ (x) (* x x)))
#:into into-list)
'(1 4 9 16 25 36 49 64 81)

procedure
(append-mapping f) → transducer?
f : (-> any/c sequence?)

Constructs a transducer that applies f to input elements and emits each element in the returned sequence downstream.

Example:

> (transduce (set 'red 'green 'blue)
(append-mapping symbol->immutable-string)
#:into into-string)
"redbluegreen"

procedure
(folding f init) → transducer?
f : (-> any/c any/c any/c)
init : any/c

Constructs a transducer that folds over the input elements and emits the current fold state after each element. Specifically, the transducer starts with init as its state and, for each input element, applies f to its current state and the input element returning the next state, which is also sent downstream.

Example:

> (transduce (in-range 1 10)
(folding + 0)
#:into into-list)
'(1 3 6 10 15 21 28 36 45)

procedure
(batching batch-reducer) → transducer?
batch-reducer : reducer?

Constructs a transducer that collects elements of the transduced sequence into batches using batch-reducer. Elements are fed into batch-reducer until it terminates the reduction, then the reduction result is emitted downstream. If there are more elements remaining, then the batch-reducer is restarted to prepare the next batch. When the transduced sequence has no more elements, if the last batch is only partially complete, then the batch-reducer’s finisher is called to produce the last batch.

If batch-reducer refuses to consume any elements and immediately terminates the reduction every time it’s started, then the returned transducer raises exn:fail:contract.

Example:

> (transduce (in-range 10)
(batching (reducer-limit into-list 4))
#:into into-list)
'((0 1 2 3) (4 5 6 7) (8 9))

value
enumerating : (transducer/c any/c enumerated?)

A transducer that emits each element along with its position in the sequence, as an enumerated? value.

Example:

> (transduce "cat" enumerating #:into into-list)
'(#<enumerated: #:element #\c #:position 0>
#<enumerated: #:element #\a #:position 1>
#<enumerated: #:element #\t #:position 2>)

procedure
(enumerated? v) → boolean?
  v : any/c
procedure
(enumerated #:element element
#:position position) → enumerated?
  element : any/c
  position : natural?
procedure
(enumerated-element enum) → any/c
  enum : enumerated?
procedure
(enumerated-position enum) → natural?
  enum : enumerated?

Predicate, constructor, and accessors for the enumerated values emitted by the enumerating transducer.

3.2.2 Element-Removing Transducers

procedure
(filtering pred) → transducer?
pred : predicate/c

Constructs a transducer that passes input elements downstream only when they satisfy pred.

Example:

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

procedure
(taking amount) → transducer?
amount : natural?

Constructs a transducer that limits the upstream sequence to its first amount elements. There is no buffering; each element is consumed and emitted downstream before the next one is consumed.

Example:

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

procedure
(taking-while pred) → transducer?
pred : predicate/c

Constructs a transducer that terminates the upstream sequence as soon as pred returns false for an element. Each element for which pred returns true is passed downstream.

Example:

> (transduce "The quick brown fox"
(taking-while char-alphabetic?)
#:into into-string)
"The"

procedure
(dropping amount) → transducer?
amount : natural?

Constructs a transducer that removes the first amount elements from the transduced sequence, then passes all remaining elements downstream.

Example:

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

procedure
(dropping-while pred) → transducer?
pred : predicate/c

Constructs a transducer that removes elements from the transduced sequence until pred returns false for an element, then passes all remaining elements downstream.

Example:

> (transduce "The quick brown fox"
(dropping-while char-alphabetic?)
#:into into-string)
" quick brown fox"

procedure
(deduplicating [#:key key-function]) → transducer?
key-function : (-> any/c any/c) = values

Constructs a transducer that removes duplicate elements from the transduced sequence. The relative order of unique elements is preserved.

Example:

> (transduce "Hello world!" (deduplicating) #:into into-string)
"Helo wrd!"

If key-function is provided, is is applied to each element and uniqueness is based on the returned key value.

Example:

> (transduce (list "cat" "dog" "CAT" "HORSE" "horse")
(deduplicating #:key string-foldcase)
#:into into-list)
'("cat" "dog" "HORSE")

procedure
(deduplicating-consecutive [#:key key-function]) → transducer?
key-function : (-> any/c any/c) = values

Constructs a transducer that removes consecutive duplicate elements from the transduced sequence. The relative order of retained elements is preserved. If the input sequence is sorted, or if it merely has all duplicates grouped together, then the constructed transducer behaves equivalently to deduplicating except it consumes a constant amount of memory.

Example:

> (transduce "Mississippi" (deduplicating-consecutive) #:into into-string)
"Misisipi"

If key-function is provided, it is applied to each element and uniqueness is based on the returned key value.

Example:

> (transduce (list "cat" "Cat" "CAT" "dog" "HORSE" "horse" "Dog")
(deduplicating-consecutive #:key string-foldcase)
#:into into-list)
'("cat" "dog" "HORSE" "Dog")

3.2.3 Element-Rearranging Transducers

procedure
(sorting [ comparator
#:key key-function
#:descending? descending?]) → transducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values
  descending? : boolean? = #f

Constructs a transducer that sorts elements in ascending order according to comparator. The sort is stable; the relative order of equivalent elements is preserved. If descending? is true, the elements are sorted in descending order instead of ascending order.

Examples:

> (transduce (list 4 1 2 5 3)
             (sorting)
             #:into into-list)
'(1 2 3 4 5)
> (transduce (list "the" "quick" "brown" "fox")
             (sorting string<=>)
             #:into into-list)
'("brown" "fox" "quick" "the")

If key-function is provided, it is applied to each element and the result is tested with comparator rather than the element itself.

Examples:

(define-record-type gem (kind weight))
(define gems
  (list (gem #:kind 'ruby #:weight 17)
        (gem #:kind 'sapphire #:weight 9)
        (gem #:kind 'emerald #:weight 13)
        (gem #:kind 'topaz #:weight 17)))

> (transduce gems
             (sorting #:key gem-weight)
             #:into into-list)
'(#<gem: #:kind sapphire #:weight 9>
  #<gem: #:kind emerald #:weight 13>
  #<gem: #:kind ruby #:weight 17>
  #<gem: #:kind topaz #:weight 17>)
> (transduce gems
             (sorting #:key gem-weight #:descending? #t)
             #:into into-list)
'(#<gem: #:kind ruby #:weight 17>
  #<gem: #:kind topaz #:weight 17>
  #<gem: #:kind emerald #:weight 13>
  #<gem: #:kind sapphire #:weight 9>)

3.2.4 Transducer Composition

procedure
(transducer-pipe trans ...) → transducer?
trans : transducer?

Composes each trans into the next, returning a single transducer. When the returned transducer is used with transduce, it has the same behavior as using all of the given transducers in series. That is, (transduce seq (transducer-pipe trans ...) #:into red) always has the same result as (transduce seq trans ... #:into red).

Example:

> (transduce (in-naturals)
             (transducer-pipe (filtering even?)
                              (taking 5))
             #:into into-list)
'(0 2 4 6 8)

procedure
(transducer-compose trans ...) → transducer?
trans : transducer?

Like transducer-pipe, but in right-to-left order instead of left-to-right order. This matches the behavior of the compose and compose1 functions, but right-to-left ordered composition is not recommended. Left-to-right composition with transducer-pipe should be preferred instead as it is far more readable and aligns with the order in which transducers are given to transduce.

Example:

> (transduce (in-naturals)
             (transducer-compose (filtering even?)
                                 (taking 5))
             #:into into-list)
'(0 2 4)

3.2.5 The Transduction Protocol

procedure
(make-transducer #:starter starter
#:consumer consumer
#:emitter emitter
#:half-closer half-closer
#:half-closed-emitter half-closed-emitter
#:finisher finisher
[ #:name name])
→ transducer?
  starter : (-> transduction-state/c)
  consumer : (-> any/c transduction-state/c)
  emitter : (-> any/c emission?)
  half-closer : (-> any/c half-closed-transduction-state/c)
  half-closed-emitter : (-> any/c half-closed-emission?)
  finisher : (-> any/c void?)
  name : (or/c interned-symbol? #f) = #f

value
transduction-state/c : flat-contract?
=
(variant/c #:consume any/c
           #:emit any/c
           #:half-closed-emit any/c
           #:finish any/c)

value
half-closed-transduction-state/c : flat-contract?
=
(variant/c #:half-closed-emit any/c
#:finish any/c)

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

procedure
(emission state value) → emission?
state : transduction-state/c
value : any/c

procedure
(emission-state em) → transduction-state/c
em : emission?

procedure
(emission-value em) → any/c
em : emission?

procedure
(half-closed-emission? v) → boolean?
v : any/c

procedure
(half-closed-emission state value) → half-closed-emission?
state : half-closed-transduction-state/c
value : any/c

procedure
(half-closed-emission-state em)
→ half-closed-transduction-state/c
em : half-closed-emission?

procedure
(half-closed-emission-value em) → any/c
em : half-closed-emission?

3.2.6 Transducer Contracts

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

A contract combinator for transducers. Returns a contract that enforces that the contracted value is a transducer and wraps the transducer to enforce domain-contract and range-contract. Every consumed element is checked with domain-contract, and every emitted element 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 squaring
  (transducer/c number? number?)
  (mapping sqr))

> (transduce (in-range 1 5) squaring #:into into-list)
'(1 4 9 16)
> (transduce "abcd" squaring #:into into-list)
squaring: contract violation
  expected: number?
  given: #\a
  in: an element consumed by
      (transducer/c number? number?)
  contract from: (definition squaring)
  blaming: top-level
   (assuming the contract is correct)
  at: eval:2.0

3.2.7 Transducer Chaperones and Impersonators

procedure
(transducer-impersonate transducer
[ #:domain-guard domain-guard
#:range-guard range-guard
#:properties properties
#:chaperone? chaperone?])
→ transducer?
  transducer : transducer?
  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 transducer. Whenever the impersonating transducer is used to transduce a sequence, domain-guard is applied to each element it consumes and range-guard is applied to each element it emits. 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 "Consuming ~a\n" v)
  v)
(define (print-range v)
  (printf "Emitting ~a\n" v)
  v)
(define summing/printing
  (transducer-impersonate (folding + 0)
                          #:domain-guard print-domain
                          #:range-guard print-range))

> (transduce (in-range 1 6) summing/printing #:into into-list)
Consuming 1
Emitting 1
Consuming 2
Emitting 3
Consuming 3
Emitting 6
Consuming 4
Emitting 10
Consuming 5
Emitting 15
'(1 3 6 10 15)

3.2.8 Debugging Transducers

procedure
(peeking handler) → transducer?
handler : (-> any/c void?)

Constructs a transducer that calls handler on each element for its side effects. Elements are emitted immediately after handler is called on them, so if an element is never consumed downstream then handler won’t be called on any later elements.

This function is intended mostly for debugging, as (peeking displayln) can be inserted into a transduction pipeline to investigate what elements are consumed in that part of the pipeline.

Example:

> (transduce (list 1 2 3 'apple 4 5 6)
             (peeking displayln)
             (taking-while number?)
             #:into into-sum)
1
2
3
apple
6

3.2.9 Testing Transducers

(require rebellion/streaming/transducer/testing)
	package: rebellion

This module provides utilities for testing transducers.

procedure
(observing-transduction-events subject)
→ (transducer/c any/c transduction-event?)
subject : transducer?

Constructs a transducer that passes consumed values to subject, then emits transduction-event? structures describing the state transitions that subject performs, including any consumed or emitted values. This is mostly useful when testing transducers, as the emitted events can be gathered into a list and asserted against.

The first emitted event is always start-event and the last one is always finish-event. A half-close-event is emitted if subject was half-closed, which means the upstream sequence ran out of elements while subject was trying to consume one.

Examples:

> (transduce (in-naturals)
             (observing-transduction-events (taking 3))
             #:into into-list)
'(#<start-event>
  #<consume-event: 0>
  #<emit-event: 0>
  #<consume-event: 1>
  #<emit-event: 1>
  #<consume-event: 2>
  #<half-closed-emit-event: 2>
  #<finish-event>)
> (transduce (list 1 2)
             (observing-transduction-events (taking 3))
             #:into into-list)
'(#<start-event>
  #<consume-event: 1>
  #<emit-event: 1>
  #<consume-event: 2>
  #<emit-event: 2>
  #<half-close-event>
  #<finish-event>)

procedure
(transduction-event? v) → boolean?
v : any/c

A predicate that identifiers transducer events, which are emitted by observing-transduction-events to describe the behavior of a transducer.

value
start-event : transduction-event?
value
half-close-event : transduction-event?
value
finish-event : transduction-event?

Constants representing a transducer starting, half-closing, or finishing, respectively.

value
consume-event? : predicate/c
procedure
(consume-event v) → consume-event?
v : any/c
procedure
(consume-event-value event) → any/c
event : consume-event?

Predicate, constructor, and accessor for transducer events representing a transducer consuming a value. The consumed value is wrapped by the event. Every consume-event? is a transduction-event?.

value
emit-event? : predicate/c
procedure
(emit-event v) → emit-event?
v : any/c
procedure
(emit-event-value event) → any/c
event : emit-event?

Predicate, constructor, and accessor for transducer events representing a transducer emitting a value. The emitted value is wrapped by the event. Every emit-event? is a transduction-event?.

value
half-closed-emit-event? : predicate/c
procedure
(half-closed-emit-event v) → half-closed-emit-event?
v : any/c
procedure
(half-closed-emit-event-value event) → any/c
event : half-closed-emit-event?

Predicate, constructor, and accessor for transducer events representing a half-closed transducer emitting a value. The emitted value is wrapped by the event. Every half-closed-emit-event? is a transduction-event?.

top ← prev up next →

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

3.2.1	Element-Transforming Transducers
3.2.2	Element-Removing Transducers
3.2.3	Element-Rearranging Transducers
3.2.4	Transducer Composition
3.2.5	The Transduction Protocol
3.2.6	Transducer Contracts
3.2.7	Transducer Chaperones and Impersonators
3.2.8	Debugging Transducers
3.2.9	Testing Transducers