3.2 Transducers

8.16.0.1

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-transduced 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 Transforming Elements with 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.

This is similar to Java’s Stream.flatMap method.

Example:

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

(transduce (list 3 1 2) (append-mapping (lambda (n) (in-range 0 n)) #:into into-list))

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

procedure
(windowing window-size
[ #:into window-reducer]) → transducer?
window-size : exact-positive-integer?
window-reducer : reducer? = into-list

Constructs a transducer that groups the elements of the transduced sequence into sliding windows of size window-size. Each window contains window-size elements that were adjacent in the original sequence, and the window "slides" one element to the right at a time.

Example:

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

If window-reducer is provided, it is used to reduce each window. By default each window’s elements are collected into a list. Only full windows are reduced and emitted downstream: if window-reducer finishes early for a window, before consuming window-size elements, the reduction result is not emitted downstream until after enough elements are consumed from the transduced sequence to verify that the result corresponds to a full window.

Examples:

> (transduce "hello world"
             (windowing 3 #:into into-string)
             #:into into-list)
'("hel" "ell" "llo" "lo " "o w" " wo" "wor" "orl" "rld")
> (transduce "hello world"
             (windowing 3 #:into (into-index-of #\w))
             #:into into-list)
(list
#<absent>
#<absent>
#<absent>
#<absent>
(present 2)
(present 1)
(present 0)
#<absent>
#<absent>)

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)
(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 Removing Elements with 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
(taking-maxima [ comparator
#:key key-function]) → transducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values
procedure
(taking-minima [ comparator
#:key key-function]) → transducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values

Constructs transducers that remove all elements from the sequence except for the largest elements (called the maxima) or the smallest elements (called the minima), respectively. If multiple values are tied for largest or smallest, all of them are kept. The relative order of the maxima or minima is preserved.

Example:

> (transduce (list 2 512 3 5 512)
(taking-maxima)
#:into into-list)
'(512 512)

Elements are compared using comparator. If key-function is provided, then elements are not compared directly. Instead, a key is extracted from each element using key-function and the keys of elements are compared instead of the elements themselves.

Examples:

> (transduce (list "cat" "dog" "zebra" "horse")
             (taking-maxima string<=>)
             #:into into-list)
'("zebra")
> (transduce (list "red" "yellow" "blue" "purple" "green")
             (taking-maxima #:key string-length)
             #:into into-list)
'("yellow" "purple")

procedure
(taking-local-maxima [ comparator
#:key key-function]) → transducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values
procedure
(taking-local-minima [ comparator
#:key key-function]) → transducer?
  comparator : comparator? = real<=>
  key-function : (-> any/c any/c) = values

Constructs transducers that remove all elements from the sequence except for the elements that are larger than their neighbors (called the local maxima) or smaller than their neighbors (called the local minima), respectively. If a subsequence of values are equivalent but larger (or smaller) than the subsequence’s neighbors, the last element of the subsequence is kept. The relative order of the local maxima or minima is preserved.

Example:

> (transduce (list 1 8 4 7 1)
(taking-local-maxima)
#:into into-list)
'(8 7)

Examples:

> (transduce (list "cat" "dog" "aardvark" "zebra" "horse")
             (taking-local-maxima string<=>)
             #:into into-list)
'("dog" "zebra")
> (transduce (list "a" "long" "b" "longer" "longest" "c")
             (taking-local-maxima #:key string-length)
             #:into into-list)
'("long" "longest")

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

Constructs a transducer that keeps only the duplicate elements of the transduced sequence. The first time an element occurs, it is removed from the sequence. Subsequent occurrences of that element are emitted downstream.

Example:

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

If key-function is provided, then it is used to extract a key from each element and only elements with duplicate keys are emitted downstream.

Example:

> (transduce (list "red" "yellow" "blue" "purple" "green")
(taking-duplicates #:key string-length)
#:into into-list)
'("purple")

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 Adding Elements with Transducers🔗ℹ

procedure
(adding-between separator) → transducer?
separator : any/c

Constructs a transducer that inserts separator between elements of the transduced sequence. If the input sequence does not contain at least two elements, nothing is inserted.

Example:

> (transduce "BEHOLD" (adding-between #\space) #:into into-string)
"B E H O L D"

procedure
(splicing-between seperator-seq) → transducer?
seperator-seq : (sequence/c any/c)

Constructs a transducer that inserts each element of separator-seq between elements of the transduced sequence. If the input sequence does not contain at least two elements, nothing is inserted.

Example:

> (transduce "BEHOLD" (splicing-between " ") #:into into-string)
"B E H O L D"

Beware that if separator-seq is inserted into the input sequence multiple times, it is initiated each time it’s inserted. This can have unexpected behavior with sequences that have side effects, sequences that are nondeterministic, and sequences that observe concurrently-mutated state. This behavior can be suppressed by converting the sequence to a stream using sequence->stream.

Examples:

(struct shoes-or-hat ()
  ; This sequence randomly picks between a pair of shoes or a single hat
  #:property prop:sequence
  (λ (this)
    (random-ref (list (list 'shoe 'shoe)
                      (list 'hat)))))

> (transduce (list 1 2 3 4 5 6)
             (splicing-between (shoes-or-hat))
             #:into into-list)
'(1 hat 2 hat 3 shoe shoe 4 hat 5 shoe shoe 6)
> (transduce (list 1 2 3 4 5 6)
             (splicing-between (sequence->stream (shoes-or-hat)))
             #:into into-list)
'(1 hat 2 hat 3 hat 4 hat 5 hat 6)

3.2.4 Rearranging Elements with 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)
(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)
(list
(gem #:kind 'ruby #:weight 17)
(gem #:kind 'topaz #:weight 17)
(gem #:kind 'emerald #:weight 13)
(gem #:kind 'sapphire #:weight 9))

procedure
(shuffling) → transducer?

Constructs a transducer that shuffles the stream’s elements randomly. The entire input stream is consumed before any elements are emitted downstream.

Example:

> (transduce "hello my friend"
(shuffling)
#:into into-string)
"nr hdelileyfm o"

procedure
(transposing #:into column-reducer
[ #:ordered? preserve-column-order?])
→ (transducer/c (sequence/c any/c) any/c)
column-reducer : reducer?
preserve-column-order? : boolean? = #true

Constructs a transducer that transforms a sequence of rows (where each row can be any single-element sequence) into a sequence of columns, using column-reducer to build each column. All of the row sequences must have the same length, or else a contract error is raised.

Examples:

> (transduce (list (list 1 2 3) (list 4 5 6) (list 7 8 9))
             (transposing #:into into-list)
             #:into into-list)
'((1 4 7) (2 5 8) (3 6 9))
> (transduce (list "abc" "xyz")
             (transposing #:into into-string)
             #:into into-list)
'("ax" "by" "cz")

If column-reducer finishes early while building a column, that column may be sent downstream before additional rows are consumed. If preserve-column-order? is true, a column is only sent downstream once all columns to the left of it have been sent downstream. If preserve-column-order? is false, columns are sent downstream as soon as they’re ready. In either case, if all columns finish early the transducer stops consuming input rows from upstream.

Examples:

(define into-list-while-positive
  (into-transduced (taking-while positive?) #:into into-list))
(define rows
  (list (list 1 2 3)
        (list 1 0 3)
        (list 0 0 3)
        (list 0 0 0)))

> (transduce rows
             (transposing #:into into-list-while-positive)
             #:into into-list)
'((1 1) (2) (3 3 3))
> (transduce rows
             (transposing #:into into-list-while-positive #:ordered? #false)
             #:into into-list)
'((2) (1 1) (3 3 3))

3.2.5 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.6 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.7 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.8 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.9 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.10 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)
(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)
(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?.

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	Transforming Elements with Transducers
3.2.2	Removing Elements with Transducers
3.2.3	Adding Elements with Transducers
3.2.4	Rearranging Elements with Transducers
3.2.5	Transducer Composition
3.2.6	The Transduction Protocol
3.2.7	Transducer Contracts
3.2.8	Transducer Chaperones and Impersonators
3.2.9	Debugging Transducers
3.2.10	Testing Transducers