chickadee » transducers

CHICKEN Transducers

Transducers for working with foldable data types.

Overview

This library provides an abstraction called "transducers." Originally, transducers were a concept in Clojure, meant to solve some of the following problems:

  1. Every new data structure requires a new implementation of map / filter / fold / etc.
  2. Every map / filter / fold operation creates intermediate structures that are thrown out as these operations are composed.
  3. A corollary to the previous two points &mdash performance is often unknown or variable across all these operations due to the fact that code is not shared. Some performance variation across data structures is expected, but it is often unclear why or where to start looking.

The SRFI process produced SRFI-171 Transducers, which I was unhappy with for various reasons. I've developed this egg as a means to address some of those concerns and provide the best transducers library available for Scheme.

Installation

Installation happens through chicken-install. You should be able to do the following:

 
chicken-install -s -test transducers

Module Structure

There are a handful of modules in this egg. They are:

Each of the sub-modules within the egg can be imported individually by doing something like

 
(import (transducers base)
        (transducers lists)
        (transducers numbers)
        (transducers vectors)
        (transducers ports))

For convenience, one can choose to directly import everything through the meta module transducers, which provides re-exports of all of the above sub-modules.

 
(import transducers)

Reporting issues

Please report issues in the repository or on the CHICKEN bug tracker.

Missing features

Strings

At present there is no immediate way to transduce over strings in this library. This is because in CHICKEN there are fundamentally two different kinds of strings: "normal" or default ASCII / latin1 strings and UTF-8 strings.

Right now there is no current plan to support both of these. Instead one can easily transduce over a string by using ports:

 
(import (chicken port)
        transducers)

(with-output-to-string
  (lambda ()
    (with-input-from-string "a b c d"
        (lambda ()
          (transduce reader-fold
                     (remove char-whitespace?)
                     (collect-writer write-char)
                     read-char)))))
; => "abcd"

Repository

https://gitlab.com/ThatGeoGuy/chicken-transducers

A Quick Tutorial

The easiest way to get started is to understand transduce and how to use it:

 
(import transducers)

(transduce list-fold         ; Folder
           values            ; Transducer
           (collect-list)    ; Collector
           (list 1 2 3 4 5)) ; Data

; => (1 2 3 4 5)

Let's go through each piece by piece:

If you want, you can also include a Sentinel value to seed the collector. It is not always obvious what each collector uses as a sentinel value, but sometimes it is pretty easy to tell. If you're wondering what the default for a given collector is, you can always call the collector with no arguments to see what the default value would be.

 
((collect-list)) ; => '()

((collect-list (list 'a 'b 'c))) ; => (a b c)

((collect-vector 0)) ; => #<transducers.vectors#<collector>>

((collect-first)) ; => #f

((collect-first (list 'nothing 'found))) ; => (nothing found)

Each of these is described in a bit more detail in the API reference below, so be sure to give those a read before using them to get an idea of whether or not you want to add a sentinel value to your transduce call.

Other libraries

It is important to beware combining transducers with other libraries (such as SRFI-1). I have intentionally not gone out of my way to avoid name-clashes with SRFI-1 (or SRFI-133, for example) for the sake of keeping transducers easy to read and easy to write.

map for example is the name of a procedure exported by this library. In the (scheme) module this is already exported, and you probably have already used this procedure for mapping over lists. The map exported by the transducers library is not the same as that map. This was by design, so just be careful of that. CHICKEN provides a number of ways to [[|prefix]] or otherwise [[|rename]] symbols that you import, so feel free to rename symbols if you plan to mix and match transducers with other libraries. In most cases I'd argue that you probably don't need to since transducers encompass that functionality already, so you have been warned.

Fold Procedures

I mentioned that the fold procedures are special in this library. Generally speaking any fold procedure with the signature (fold f sentinel data) could work with this library. Why then do we export list-fold / vector-fold / etc.? Well, it's because these fold procedures are a little different than the classical fold / vector-fold you're probably used to from SRFI-1 / SRFI-133. The fold procedures in this library are capable of stopping early if one of the transducers requires it. This is done by checking for reduced? values:

 
(define (list-fold f sentinel xs)
  (check-list 'list-fold xs 'xs)
  (define (list-fold-inner f sentinel xs)
    (if (null? xs)
      sentinel
      (let ((x (f sentinel (car xs))))
        (if (reduced? x)
          (unwrap x)
          (list-fold-inner f x (cdr xs))))))
  (list-fold-inner f sentinel xs))

The key is in the last branch, where we check (if (reduced? x) ...). If all you were doing was mapping over a list, one could theoretically do the following:

 
(import (chicken base)
        transducers)

(transduce foldl           ; foldl is provided by (chicken base)
           (map add1)
           (collect-list)
           (list 0 1 2 3))

; => (1 2 3 4)

Since every member of the list is visited and there is never an "early exit" due to a transducer or collector, this will work. Be warned however, because some collectors depend on early termination:

 
(import (chicken base)
        transducers)

(transduce foldl           ; foldl is provided by (chicken base)
           (map add1)
           (collect-first)
           (list 0 1 2 3))

; => #<transducers.base#<reduced>>

(transduce list-fold      ; list-fold is provided by transducers
           (map add1)
           (collect-first)
           (list 0 1 2 3))

; => 1

Normally, one would expect to see the first value of the list after it is mapped with add1 (i.e. the value 1). However, since foldl is not checking for reduced values it does not correctly unwrap this value if there's an early termination (which the first collector requires).

Because of this, we end up with #<transducers.base#<reduced>> instead of what we expected (1). It is therefore advisable to either rewrite your fold procedures to check for reduced values, or to use the ones provided by this library.

Composing multiple transducers

The fantastic thing about transducers is that they can be very easily composed together. Consider the following example:

 
(import transducers)

(transduce vector-fold
           (compose
             (filter odd?)
             (drop 1)
             (map (lambda (x) (* 3 x))))
           (collect-list)
           (vector 0 1 2 3 4 5 6 7 8 9 10))

; => (9 15 21 27)

Let's break down what's happening here step by step:

  1. We're folding over a vector as input.
  2. We're collecting the final output into a list.
  3. For each item we:
  4. Filter only the items for which odd? is true.
  5. Drop the first item (for which odd? was true)
  6. Map the remaining items by multiplying them by 3

The operations that are composed (using compose) are executed in order on each item from top to bottom (or left-to-right). Notice that only elements that make it past each transducer (filter -> drop -> map) are in the final list that we output.

API Reference

The API reference is split into sections according to which sub-module a procedure / type / syntax pertains to.

(transducers base)

Reduced values
<reduced>record

A record type that represents a "reduced" value &mdash reduced values are output by certain collectors or transducers to indicate that an early return is necessary. This type is disjoint from all other Scheme types.

make-reduced valueprocedure

Constructs a new <reduced> record holding the value.

reduced? valueprocedure

Predicate to check if value is a <reduced> or not.

unwrap reducedprocedure

Unwraps a <reduced> and returns the original value that it was constructed with.

 
(import transducers)

(unwrap (make-reduced 'a)) ; => 'a
(unwrap (make-reduced 1)) ; => 1
(unwrap (make-reduced (list 'a 'b 'c))) ; => (a b c)

preserving-reduced transducerprocedure

A transducer that creates a doubly-wrapped reduced value, as if calling (make-reduced (make-reduced value)). This is necessary for the implementation of some other transducers that fold over a provided collection. This is necessary because the fold procedures in this egg naturally will unwrap any reduced values / early exits. However, if a transducer is calling some kind of fold operation internally, we often want to be sure that if a value is reduced inside that fold operation that the transducer returns a reduced value, so that the outer transduce knows to stop.

This interface is primarily for folks implementing their own transducers. In most cases you won't need to know too much about it, but see define-flatten-transducer in this file for an example of how it is used.

Collectors
collect-any pred? #!optional (sentinel #f)procedure

Returns a collector that will return #t if any item it encounters satisfies pred?. Returns early if pred? is satisfied, but will iterate across the entirety of the data if pred? isn't satisfied by any of the items.

 
(import transducers)

(transduce list-fold
           (inspect (lambda (x)
                      (if (odd? x)
                        (print x " is odd!")
                        (print x " is not odd!"))))
           (collect-any odd?)
           (list 2 4 6 8))

; 2 is not odd!
; 4 is not odd!
; 6 is not odd!
; 8 is not odd!
; => #f

(transduce list-fold
           (inspect (lambda (x)
                      (if (odd? x)
                        (print x " is odd!")
                        (print x " is not odd!"))))
           (collect-any odd?)
           (list 2 1 6 8))

; 2 is not odd!
; 1 is odd!
; => #t

collect-all pred? #!optional (sentinel #t)procedure

Returns a collector that will return #t if all the items it encounters satisfy pred?. Returns early with #f if pred? is false for any item, but will iterate across the entirety of the data if pred? is always satisfied.

 
(import transducers)

(transduce list-fold
           (inspect (lambda (x)
                      (if (odd? x)
                        (print x " is odd!")
                        (print x " is not odd!"))))
           (collect-all odd?)
           (list 1 2 4 6))

; 1 is odd!
; 2 is not odd!
; => #f

(transduce list-fold
           (inspect (lambda (x)
                      (if (odd? x)
                        (print x " is odd!")
                        (print x " is not odd!"))))
           (collect-all odd?)
           (list 1 3 5 7))

; 1 is odd!
; 3 is odd!
; 5 is odd!
; 7 is odd!
; => #t

collect-count #!optional (sentinel 0)procedure

A collector which counts the number of items that are transduced.

 
(import transducers)

(transduce list-fold values count (list 'a 'b 'c))
; => 3

(transduce list-fold
           (filter odd?)
           (collect-count)
           (list 1 2 3 4 5 6 7))
; => 4

collect-first #!optional (sentinel #f)procedure
collect-last #!optional (sentinel #f)procedure

A collector that returns either the first or last item of the collection only. first will terminate early after collecting the first item.

 
(import transducers)

(transduce list-fold
           (filter odd?)
           (collect-first)
           (list 2 4 6 8 11 13 1 2 4))

; => 11

(transduce list-fold
           (filter odd?)
           (collect-last)
           (list 2 4 6 8 11 13 1 2 4))

; => 1

collect-first in particular is very useful as a collector. By combining the collect-first collector and the filter transducer, we can implement a "find" operation on a collection:

 
(import transducers)

(transduce list-fold
           (filter (lambda (x) (eq? x 'c)))
           (collect-first)
           (list 'b 'c 'd 'c))

; => 'c

What's more, collect-first and collect-last are also very useful with sentinel values. If collect-first or collect-last fail to find any items (say, because you filtered them out), then usually they return false:

 
(import transducers)

(transduce list-fold
           (filter odd?)
           (collect-first)
           (list 2 4 6 8))

; => #f

This is not too dissimilar from most find operations in Scheme. However, #f can sometimes be ambiguous. If you were extracting the value from an a-list as follows:

 
(import transducers)

(transduce list-fold
           (compose
             (filter (lambda (kv-pair)
                       (eq? (car kv-pair) 'bar)))
             (map cdr))
           (collect-first)
           (list (cons 'foo 1)
                 (cons 'bar #f)
                 (cons 'baz "abcd")))

; => #f

then we can see that #f is ambiguous. Instead, we can use a custom sentinel value, for example the sentinel (nothing) from SRFI-189:

 
(import transducers srfi-189)

(transduce list-fold
           (compose
             (filter (lambda (kv-pair)
                       (eq? (car kv-pair) 'bar)))
             (map cdr))
           (collect-first)
           (list (cons 'foo 1)
                 (cons 'bar #f)
                 (cons 'baz "abcd")))

; => #f

(transduce list-fold
           (compose
             (filter (lambda (kv-pair)
                       (eq? (car kv-pair) 0)))
             (map cdr))
           (collect-first (nothing))
           (list (cons 'foo 1)
                 (cons 'bar #f)
                 (cons 'baz "abcd")))

; => #<srfi-189#<nothing>>

This way, one can use the custom sentinel value to distinguish between ambiguous #f returns.

collect-max #!optional (sentinel -inf.0)procedure
collect-min #!optional (sentinel +inf.0)procedure

Collectors that collect either the maximum value or minimum value transduced over, respectively.

 
(import transducers)

(transduce list-fold
           values
           (collect-max)
           (list -999 0 999))

; => 999.0

(transduce list-fold
           values
           (collect-min)
           (list -999 0 999))

; => -999.0

collect-sum #!optional (sentinel 0)procedure
collect-product #!optional (sentinel 1)procedure

These collectors will compute the sum / product of the items being transduced, as if by applying + or * respectively to the arguments.

 
(import transducers)

(transduce list-fold
           values
           (collect-sum 100)
           (list 2 4 6))

; => 112

(transduce list-fold
           values
           (collect-product -1)
           (list 1 3 5))

; => -15

(collect-void #!optional (sentinel (void)))procedure

A collector that does nothing and returns an unspecified value (as if calling (void)). This is useful if your transducer is meant to only incur side effects:

 
(import transducers)

(transduce list-fold
           print
           (collect-void)
           (list "Each" "String" "Prints" "on" "its" "own" "line"))

; Each
; String
; Prints
; on
; its
; own
; line

A short hand for doing this is provided by the for-each procedure in this module.

Transducer procedures
map fprocedure

A transducer that calls (f item) on each item it encounters and forwards the result.

 
(import transducers)

(transduce list-fold
           (map (lambda (x) (* 3 x)))
           (collect-list)
           (list 1 2 3))

; => (3 6 9)

filter pred?procedure
remove pred?procedure

A transducer that filters for or removes items that satisfy pred?.

 
(import transducers)

(transduce list-fold
           (filter even?)
           (collect-list)
           (list 1 2 3 4))

; => (2 4)

(transduce list-fold
           (remove even?)
           (collect-list)
           (list 1 2 3 4))

; => (1 3)

drop nprocedure
drop-while pred?procedure

drop is a transducer that drops or skips over n many items before forwarding every item thereafter. drop-while is a procedure that drops or skips over items until it encounters an item that does not satisfy pred?. n must be a non-negative fixnum and pred? must be a predicate procedure (e.g. symbol?, list?, etc).

 
(import transducers)

(transduce list-fold
           (drop 2)
           (collect-list)
           (list 1 2 3 4 5))

; => (3 4 5)

(transduce list-fold
           (drop-while symbol?)
           (collect-list)
           (list 'a 'b 'c 'd 1 2 3 'e 'f 'g))

; => (1 2 3 e f g)

take nprocedure
take-while nprocedure

take is a transducer that takes n many items before ending the transduction early (assuming at least n items exist. If fewer than n items exist, take doesn't do anything). take-while continues to take items as long as each item satisfies pred?. take-while exits early on the first item that does not satisfy pred?.

 
(import transducers)

(transduce list-fold
           (take 2)
           (collect-list)
           (list 1 2 3 4 5))

; => (1 2)

(transduce list-fold
           (take-while symbol?)
           (collect-list)
           (list 'a 'b 'c 'd 1 2 3 'e 'f 'g))

; => (a b c d)

chunks n collectorprocedure
chunks-exact n collectorprocedure

chunks collects groups of up to n items given a collector and forwards these chunked representations on as individual items. If enough items are not available then chunks will return the chunk early.

 
(import transducers)

(transduce list-fold
           (chunks 3 (collect-list))
           (collect-list)
           (list 0 1 2 3 4 5 6 8 9 10))

; => ((0 1 2) (3 4 5) (6 7 8) (9 10))

Notice how that last group is (9 10) even though we asked for chunks of size 3. chunks-exact works similarly to chunks, but drops any groups that do not have exactly size n.

 
(import transducers)

(transduce list-fold
           (chunks 3 (collect-list))
           (collect-list)
           (list 0 1 2 3 4 5 6 8 9 10))

; => ((0 1 2) (3 4 5) (6 7 8))

enumerateprocedure

conses an ordered index starting at 0 and incrementing by 1 to the front of the value.

 
(import transducers)

(transduce list-fold
           enumerate
           (collect-list)
           (list 'a 'b 'c 'd))

; => ((0 . a) (1 . b) (2 . c) (3 . d))

inspect fprocedure

A transducer that "inspects" a value by applying a procedure f to the value and then forwarding the original value on. This is primarily useful for debugging but can also be used for side-effects.

 
(import transducers)

(transduce list-fold
           (compose
             (map add1)
             (inspect print)
             (map (lambda (x) (* 3 x)))
             (inspect print))
           (collect-list)
           (list 2 4 1 3 5 9))

; 3
; 9
; 5
; 15
; 2
; 6
; 4
; 8
; 6
; 18
; 10
; 30
; => (9 15 6 8 18 30)

(define-chain-transducer name folder)syntax

A macro that defines a chain transducer for a specific type given a fold procedure for that type.

 
(import transducers)

(define-chain-transducer chain-list list-fold)

(define-flatten-transducer name type? type-fold)syntax

A macro that defines a flatten transducer for a specific type given a predicate type? for that type and a fold procedure for that type.

 
(define-flatten-transducer flatten-list list? list-fold)

(define-interleave-transducer name make-state done? next update)syntax
(define-zip-transducer name make-state done? next update)syntax

A macro that defines an interleave / zip transducer for a specific type given four procedures. The procedures are as follows:

 
;; Defined as follows:

(define-syntax define-interleave-transducer
  (syntax-rules ()
    ((_ name make-state done? next update)
     (define (name collection)
       (lambda (reducer)
         (let ((state (make-state collection)))
           (case-lambda
             (() (reducer))
             ((result) (reducer result))
             ((result item)
              (if (done? collection state)
                (make-reduced result)
                (let ((interleave-item (next collection state))
                      (next-result (reducer result item)))
                  (set! state (update collection state))
                  (if (reduced? next-result)
                    next-result
                    (reducer next-result interleave-item))))))))))))

(define-syntax define-zip-transducer
  (syntax-rules ()
    ((_ name make-state done? next update)
     (define (name collection)
       (lambda (reducer)
         (let ((state (make-state collection)))
           (case-lambda
             (() (reducer))
             ((result) (reducer result))
             ((result item)
              (if (done? collection state)
                (make-reduced result)
                (let ((zip-item (next collection state)))
                  (set! state (update collection state))
                  (reducer result (cons item zip-item))))))))))))
  • make-state: a procedure that takes in the initial collection to interleave and creates a state for the interleave process. For lists this could just be the list, for vectors this might just be an index counter. See the following examples.
  • done?: a predicate that takes in the initial collection and the interleave state and returns #t iff the interleave process should stop (e.g. if a list is exhausted, or a vector exhausted).
  • next: a procedure that takes in the initial collection and the interleave state and returns the next item to be interleaved into the transduced sequence.
  • update: a procedure that takes in the initial collection and the interleave state and returns an updated state.

Note that these procedures should be the same for both interleave and zip transducers. Some examples that are already included in the egg:

 
(define-interleave-transducer interleave-list
    (lambda (coll) coll)
    (lambda (_ s) (null? s))
    (lambda (_ s) (car s))
    (lambda (_ s) (cdr s)))

(define-interleave-transducer interleave-vector
    (lambda (coll) 0)
    (lambda (coll s) (fx>= s (vector-length coll)))
    vector-ref
    (lambda (_ s) (fx+ s 1)))

Generally speaking, how to implement these can be somewhat difficult to understand without the above macro definitions. The macro is more a convenience, and the various interleave and zip transducers can be implemented without the above syntax.

transduce folder transducers collector dataprocedure

A procedure that runs transducers over data by folding over the data with folder, finally collecting all the final result of the transducers in the collector.

This is the fundamental transduction procedure. See the docs for a quick tutorial and a more complete reference for how to use transduce.

for-each folder transducers dataprocedure

A short-hand for transduce when collecting into an undefined / void result.

 
(import transducers)

(for-each list-fold print (list 1 2 3 4))

;; is the same as

(transduce list-fold print (collect-void) (list 1 2 3 4))

(transducers lists)

list-fold f sentinel lstprocedure

Fold operation over lists. Can be used with transduce in the following way:

 
(import transducers)

(transduce list-fold
           values
           (collect-list)
           (list 1 2 3))

; => (1 2 3)

collect-list #!optional (sentinel '())procedure
collect-reverse-list #!optional (sentinel '())procedure

Collectors that collect all items through a transducer into a list (or a reversed list).

 
(import transducers)

(transduce list-fold
           values
           (collect-list)
           (list 1 2 3))

; => (1 2 3)

(transduce list-fold
           values
           (collect-reverse-list)
           (list 1 2 3))

; => (3 2 1)

flatten-listprocedure

A transducer that flattens any and all lists (recursively) that it encounters.

 
(import transducers)

(transduce list-fold
           flatten-list
           (collect-list)
           (list (list 1 2 (list 3 4 5))
                 (list 6
                       (list 7 8 9)
                       (list 10 11))))

; => (1 2 3 4 5 6 7 9 10 11)

chain-list lstprocedure

A transducer that chains the contents of lst to the end of the current transduction.

 
(import transducers)

(transduce list-fold
           (chain-list (list 1 2 3))
           (collect-list)
           (list 'a 'b 'c))

; => (a b c 1 2 3)

interleave-list lstprocedure

A transducer that interleaves the contents of lst throughout of the current transduction. If there aren't enough elements in either the current transduction or the list being interleaved then the transducer exits early.

 
(import transducers)

(transduce list-fold
           (interleave-list (list 1 2 3))
           (collect-list)
           (list 'a 'b 'c))

; => (a 1 b 2 c 3)

(transduce list-fold
           (interleave-list (list 1 2))
           (collect-list)
           (list 'a 'b 'c))

; => (a 1 b 2)

(transduce list-fold
           (interleave-list (list 1 2 3))
           (collect-list)
           (list 'a 'b))

; => (a 1 b 2)

zip-list lstprocedure

A transducer that zips the contents of the lst together with each item throughout the current transduction.

 
(import transducers)

(transduce list-fold
           (interleave-list (list 'd 'e 'f))
           (collect-list)
           (list 'a 'b 'c))

; => ((a . d) (b . e) (c . f))

(transducers numbers)

<numeric-range>record

A record type for representing the various numeric ranges that can be transduced over. Disjoint from other Scheme types.

numeric-range? valueprocedure

A predicate for checking if a value is a numeric range.

range-fold f sentinel numeric-rangeprocedure
fixnum-range-fold f sentinel numeric-rangeprocedure

A folding operation that operates over numeric-range? records. The former (range-fold) is the more generic version of the two, in that it does not require that the ranges be composed of fixnums. The latter (fixnum-range-fold) is only valid for ranges that will iterate over fixnums.

 
(import transducers)

(transduce range-fold
           (take 5)
           (collect-list)
           (counter 1.5 2))

; => (1.5 3.5 5.5 7.5 9.5)

Whereas with fixnum-range-fold you will find that the above transduction fails:

 
(import transducers)

(transduce fixnum-range-fold
           values
           (collect-list)
           (iota 5 1.5 2))

; Error: (fixnum-range-fold) bad argument type - not a fixnum: 1.5
;
;         Call history:
;
;         <syntax>          (transduce fixnum-range-fold values (collect-list) (iota 5 1.5 2))
;         <syntax>          (iota 5 1.5 2)
;         <eval>    (transduce fixnum-range-fold values (collect-list) (iota 5 1.5 2))
;         <eval>    (iota 5 1.5 2)        <--

The advantage of fixnum-range-fold is that it is faster than range-fold when your have a finite range (from range or iota) consisting only of integers. This is often the fastest way to iterate through over a set of indices.

range start endprocedure

A constructor that creates a numeric range representing the half-open interval [start end). "Ranges" constructed with this procedure always increment by 1, and will be exhausted (i.e. generate no values for a transducer) if (>= end start).

counter start #!optional (step 1)procedure

A constructor that creates a numeric range that counts an infinite series of numbers starting at start and incrementing by step at each iteration. The numeric range generated by this will never be compatible with fixnum-range-fold.

iota count #!optional (start 0) (step 1)procedure

Creates a numeric range that behaves like iota from SRFI-1. Produces count number of values starting at start and incrementing by step each time.

 
(import transducers)

(transduce fixnum-range-fold
           values
           (collect-list)
           (iota 10 -2 -1))

; => (-2 -3 -4 -5 -6 -7 -8 -9 -10 -11)

flatten-rangeprocedure

A transducer that flattens any ranges found in the transduction.

 
(import transducers)

(transduce list-fold
           flatten-range
           (collect-list)
           (list (range 0 3)
                 (range 5 10)
                 (range 14 16)))

; => (0 1 2 5 6 7 8 9 14 15)

chain-range numeric-rangeprocedure

A transducer that chains a range to the end of the current transduction.

 
(import transducers)

(transduce list-fold
           (chain-range (range 0 4))
           (collect-list)
           (list 'a 'b 'c))

; => (a b c 0 1 2 3)

interleave-range numeric-rangeprocedure

A transducer that interleaves a range in between items from the current transduction. If there aren't enough elements in either the current transduction or the range being interleaved then the transducer exits early.

 
(import transducers)

(transduce list-fold
           (interleave-range (range 0 4))
           (collect-list)
           (list 'a 'b 'c))

; => (a 0 b 1 c 2)

zip-range numeric-rangeprocedure

A transducer that interleaves a range in between items from the current transduction. If there aren't enough elements in either the current transduction or the range being zipped then the transducer exits early.

 
(import transducers)

(transduce list-fold
           (zip-range (range 0 4))
           (collect-list)
           (list 'a 'b 'c))

; => ((a . 0) (b . 1) (c . 2))

Admittedly this is very much like enumerate. However, note that enumerate will have the following differences:

  1. enumerate pairs the number and transduced item in the reverse order (e.g. (0 . a) instead of (a . 0))
  2. enumerate only terminates when the rest of the transduction does.

Of course, if one feels strongly about the enumerate ordering they are more than welcome to do the following:

 
(import transducers)

(transduce list-fold
           (zip-range (counter 0))
           (collect-list)
           (list 'a 'b 'c))

; => ((a . 0) (b . 1) (c . 2))

Which is equivalent to enumerate except with reversed ordering (since counter is infinite and does not exhaust).

(transducers vectors)

vector-fold f sentinel vecprocedure
u8vector-fold f sentinel vecprocedure
u16vector-fold f sentinel vecprocedure
u32vector-fold f sentinel vecprocedure
u64vector-fold f sentinel vecprocedure
s8vector-fold f sentinel vecprocedure
s16vector-fold f sentinel vecprocedure
s32vector-fold f sentinel vecprocedure
s64vector-fold f sentinel vecprocedure
f32vector-fold f sentinel vecprocedure
f64vector-fold f sentinel vecprocedure
c64vector-fold f sentinel vecprocedure
c128vector-fold f sentinel vecprocedure

Fold operation over vectors. Can be used with transduce in the following way:

 
(import transducers)

(transduce vector-fold
           values
           (collect-vector)
           (vector 1 2 3))

; => #(1 2 3)

The SRFI-4 vector types behave in a similar fashion.

reverse-vector-fold f sentinel vecprocedure
reverse-u8vector-fold f sentinel vecprocedure
reverse-u16vector-fold f sentinel vecprocedure
reverse-u32vector-fold f sentinel vecprocedure
reverse-u64vector-fold f sentinel vecprocedure
reverse-s8vector-fold f sentinel vecprocedure
reverse-s16vector-fold f sentinel vecprocedure
reverse-s32vector-fold f sentinel vecprocedure
reverse-s64vector-fold f sentinel vecprocedure
reverse-f32vector-fold f sentinel vecprocedure
reverse-f64vector-fold f sentinel vecprocedure
reverse-c64vector-fold f sentinel vecprocedure
reverse-c128vector-fold f sentinel vecprocedure

A reverse fold operation over vectors. Behaves the same as the vector-fold equivalent except that it folds through vectors in reverse order. In effect these behave like a right fold instead of a left-fold as many of the folding operations in this module do.

 
(import transducers)

(transduce reverse-vector-fold
           values
           (collect-vector)
           (vector 1 2 3))

; => #(3 2 1)

collect-vector #!optional (size-hint 0)procedure
collect-u8vector #!optional (size-hint 0)procedure
collect-u16vector #!optional (size-hint 0)procedure
collect-u32vector #!optional (size-hint 0)procedure
collect-u64vector #!optional (size-hint 0)procedure
collect-s8vector #!optional (size-hint 0)procedure
collect-s16vector #!optional (size-hint 0)procedure
collect-s32vector #!optional (size-hint 0)procedure
collect-s64vector #!optional (size-hint 0)procedure
collect-f32vector #!optional (size-hint 0)procedure
collect-f64vector #!optional (size-hint 0)procedure
collect-c64vector #!optional (size-hint 0)procedure
collect-c128vector #!optional (size-hint 0)procedure

Collectors that incrementally aggregate items from the transduction into a vector by pushing elements into the vector in amortized O(1) time. A size-hint can be provided to pre-allocate the capacity of the accumulated vector.

In most instances these collectors are fast enough on their own that one should probably avoid using the size-hint without either a good amount of knowledge or benchmarks to suggest otherwise. No intermediate lists or other collections are used in order to do this collection.

 
(import transducers srfi-4)

(transduce u8vector-fold
           (map exact->inexact)
           (collect-f64vector)
           (u8vector 1 2 3 4 5 6 7 8))

; => #f64(1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0)

flatten-vectorprocedure

A transducer that flattens any and all vectors (recursively) that it encounters. SRFI-4 vector variants of this are not provided because they cannot recursively contain other vectors.

 
(import transducers)

(transduce vector-fold
           flatten-vector
           (collect-vector)
           (vector 1 (vector 2 3) (vector (vector 3 4) (vector 5 6))))

; => #(1 2 3 4 5 6)

chain-vector vecprocedure
chain-u8vector vecprocedure
chain-u16vector vecprocedure
chain-u32vector vecprocedure
chain-u64vector vecprocedure
chain-s8vector vecprocedure
chain-s16vector vecprocedure
chain-s32vector vecprocedure
chain-s64vector vecprocedure
chain-f32vector vecprocedure
chain-f64vector vecprocedure
chain-c64vector vecprocedure
chain-c128vector vecprocedure

A transducer that chains the contents of the provided vector to the end of the current transduction.

 
(import transducers)

(transduce vector-fold
           (chain-u8vector (u8vector 1 2 3))
           (collect-vector)
           (vector 'a 'b 'c))

; => #(a b c 1 2 3)

interleave-vector vecprocedure
interleave-u8vector vecprocedure
interleave-u16vector vecprocedure
interleave-u32vector vecprocedure
interleave-u64vector vecprocedure
interleave-s8vector vecprocedure
interleave-s16vector vecprocedure
interleave-s32vector vecprocedure
interleave-s64vector vecprocedure
interleave-f32vector vecprocedure
interleave-f64vector vecprocedure
interleave-c64vector vecprocedure
interleave-c128vector vecprocedure

A transducer that interleaves the contents of the provided vector through the items in the current transduction. If there aren't enough elements in either the current transduction or the vector being interleaved then the transducer exits early.

 
(import transducers)

(transduce vector-fold
           (interleave-u8vector (u8vector 1 2 3))
           (collect-vector)
           (vector 'a 'b 'c))

; => #(a 1 b 2 c 3)

zip-vector vecprocedure
zip-u8vector vecprocedure
zip-u16vector vecprocedure
zip-u32vector vecprocedure
zip-u64vector vecprocedure
zip-s8vector vecprocedure
zip-s16vector vecprocedure
zip-s32vector vecprocedure
zip-s64vector vecprocedure
zip-f32vector vecprocedure
zip-f64vector vecprocedure
zip-c64vector vecprocedure
zip-c128vector vecprocedure

A transducer that zips the contents of the provided vector through the items in the current transduction. If there aren't enough elements in either the current transduction or the vector being zipd then the transducer exits early.

 
(import transducers)

(transduce vector-fold
           (zip-u8vector (u8vector 1 2 3))
           (collect-vector)
           (vector 'a 'b 'c))

; => #((a . 1) (b . 2) (c . 3))

(transducers ports)

reader-fold f sentinel vecprocedure

Fold operation over reader procedures / generators. Can be used with transduce in the following way:

 
(import (chicken port)
        transducers)

(with-input-from-string "abcd"
  (lambda ()
    (transduce reader-fold
               values
               (collect-list)
               read-char)))

; => (#\a #\b #\c #\d)

To note: (take n) is not greedy / over-eager, so it is possible to read from a reader / generator and continue to read from the same port afterwards:

 
(import (chicken port)
        transducers
        test)

(with-input-from-string "abcd"
  (lambda ()
    (test "List is (a b)"
          (list #\a #\b)
          (transduce reader-fold
                     (take 2)
                     (collect-list)
                     read-char))

    (test "Reader has not yet read #\c"
          #\c
          (read-char)))

(collect-writer writer #!optional (sentinel (void)))procedure

A collector that takes a writer (or an accumulator) and calls the writer with each item successively as they are transduced.

 
(import (chicken port)
        transducers)

(with-output-to-string
  (lambda ()
    (transduce range-fold
               (map integer->char)
               (collect-writer write-char)
               (iota 26 65))))

; => "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

chain-reader readerprocedure

A transducer that chains the contents of reader to the end of the current transduction.

 
(import (chicken port)
        transducers)

(with-input-from-string "abcd"
  (lambda ()
    (transduce list-fold
               (chain-reader read-char)
               (collect-list)
               (list 1 2 3))))

; => (1 2 3 #\a #\b #\c #\d)

interleave-reader readerprocedure

A transducer that interleaves the contents of reader through the current transduction.

 
(import (chicken port)
        transducers)

(with-input-from-string "abcd"
  (lambda ()
    (transduce list-fold
               (interleave-reader read-char)
               (collect-list)
               (list 1 2 3))))

; => (1 #\a 2 #\b 3 #\c)

zip-reader readerprocedure

A transducer that zips the contents of reader to items in the the current transduction.

 
(import (chicken port)
        transducers)

(with-input-from-string "abcd"
  (lambda ()
    (transduce list-fold
               (zip-reader read-char)
               (collect-list)
               (list 1 2 3))))

; => ((1 . #\a) (2 . #\b) (3 . #\c))

License

The code is licensed under the MIT license:

 
Copyright (c) 2022 Jeremy Steward

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Contents »