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

• base: All of the common transducers, transduce operation, and common collectors that can be used across any collection.
• lists: fold operations over lists, list collection, and flatten / chain / interleave / zip transducers for lists.
• numbers: fold operations over numeric ranges, and flatten / chain / interleave / zip transducers for ranges.
• vectors: fold operations over vector types (including Scheme's vector and SRFI-4 vector types), vector collection, and flatten / chain / interleave / zip transducers for vectors.
• ports: fold operations over reader procedures (including SRFI-158 generators), collection into writer procedures (e.g. write, write-char, write-byte), and chain / interleave / zip transducers for readers.
• mappings: fold and transducer procedures over SRFI-146 mappings and hashmaps.

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)
        (transducers mappings))

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:

• Folder: This is a procedure that can fold over a given type. A fold operation is one that takes the form (fold f sentinel data). More on these in the section below. One thing to remember is that your fold procedure must match the type of your Data. You cannot, for example, use vector-fold on a list. You must use list-fold on a list and vector-fold on a vector. Note that fold procedures always take f with the argument order (f collection item). This is different from "cons" ordering folders such as the fold from SRFI-1, which takes a function of the form (f item collection), similar to (cons 1 '()).
• Transducer: This is a procedure that tells us what we want to do to each item in our data. This can be anything like mapping (using map), filtering (using filter or remove), zipping, and more. Look at the API reference for more details on what transducers are available. Note that values is special — this transducer does nothing and just passes the values through.
• Collector: This is a procedure that "collects" items that are transformed by our transducers. They are all named collect-XXX for some XXX, whether that be a list (if you want to collect everything into a list), a vector (if you want a vector as output), or otherwise. Collectors tell us what we want as output from our process.
• Data: Data is whatever data we want to fold through with our Folder. This can be a list, a vector, an SRFI-4 vector, and more. As long as the Folder matches the Data then it should be fine.

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

Transducible type-classes

Some of the sets of transducer procedures comprise what is called a transducible type-class. This is a type-class pattern over some sets of procedures that helps group this collection of procedures together of a given type. This can be useful if you need to work with transducers across a variety of types and want to collectively store these types' relevant procedures so that you can polymorphically dispatch to the correct procedures every time.

A direct example might be where you store either a list or a vector within some record type, and know that you want to be able to do the following:

1. Extract the list / vector from the record type
2. Use that extracted list / vector in a transduction

By storing the transducible type-class next to the list / vector, you can reduce branching by merely calling into the correct set of interfaces:

 
(define-record-type <my-record>
  (make-my-record transducible xs)
  my-record?
  (transducible my-record-transducible)
  (xs my-record-seq))

(define my-list
  (make-my-record list-transducible (list 1 2 3 4 5)))
(define my-vec
  (make-my-record vector-transducible (vector 1 2 3 4 5)))

;; Because we don't know whether my-rec stores a list or a
;; vector, we use the inner transducible type-class to tell
;; us which procedure to use.
(define (sum-all-values my-rec)
  (transduce (transducible-folder (my-record-transducible my-rec))
             values
             (collect-sum)
             (my-record-seq my-rec)))

(sum-all-values my-list) ; => 15
(sum-all-values my-vec)  ; => 15

In this way, one can leverage polymorphism instead of performing type-tests for every possible collection that could be stored inside some record, map, etc. We avoid explicit branching in the code by leveraging a kind of runtime polymorphism. Not only do we always leverage the correct folding operation (or collecting, zipping, etc.), but our code remains cleaner as there is only one path to execute.

One question to be raised from this is: "why this particular set of procedures?" This is a valid question, as many useful programs may want to define a type class over a subset / superset of the procedures defined in <transducible>s. I've opted to define transducibles in terms of the procedures below (i.e. fold, collect, flatten, chain, interleave, zip) to restrict transducible type-classes to cover only groups of types which are bounded and concrete in representation.

This somewhat limits the kinds of transducible type-classes that can be expressed. For example, although (transducers numbers) defines a folder (range-fold), a flattener (flatten-range), a chainer (chain-range), an interleaver (interleave-range), and a zipper (zip-range), it defines no collector. That is because numeric ranges can't really be "collected" in any single way that represents a single range.

I've opted not to define default transducible type-classes in the library where all these procedures cannot be defined, because while the defaults provided are useful, it is likely that downstream users may find default transducibles less useful if certain procedures were optional or not included (thus forcing one to have to check if they exist / can be used before calling them, which defeats the whole point about using polymorphism over explicit branching).

Of course, all the tools available for working with transducibles will work if you define your own. There is also nothing in the code that prevents one from setting any of the given procedures to #f if they want to indicate that a procedure is not available:

 
(define range-transducible
  (make-transducible range-fold
                     #f
                     flatten-range
                     chain-range
                     interleave-range
                     zip-range))

Likewise, substitute #f above for collect-vector, collect-list, etc. if you believe you always want to collect into a single type. The default transducibles in this library should be treated as reference examples, and not prescriptive in how they are used or in how one defines their APIs.

make-transducible folder collector flattener chainer interleaver zipperprocedure

Creates a new transducible type-class comprising the provided fold / collect / flatten / chain / interleave / zip procedures.

 
(define list-transducible
  (make-transducible list-fold
                     collect-list
                     flatten-list
                     chain-list
                     interleave-list
                     zip-list))

transducible? valueprocedure

A predicate for checking if value is a transducible type-class.

transducible-folder transducibleprocedure

A procedure which takes a transducible type-class and returns its folding operation. E.g. for the default list-transducible this would return list-fold.

transducible-collector transducibleprocedure

A procedure which takes a transducible type-class and returns its collecting operation. E.g. for the default list-transducible this would return collect-list.

transducible-flattener transducibleprocedure

A procedure which takes a transducible type-class and returns its flattening operation. E.g. for the default list-transducible this would return flatten-list.

transducible-chainer transducibleprocedure

A procedure which takes a transducible type-class and returns its chaining operation. E.g. for the default list-transducible this would return chain-list.

transducible-interleaver transducibleprocedure

A procedure which takes a transducible type-class and returns its interleave operation. E.g. for the default list-transducible this would return interleave-list.

transducible-zipper transducibleprocedure

A procedure which takes a transducible type-class and returns its zip operation. E.g. for the default list-transducible this would return zip-list.

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

list-transducibleconstant

A transducible type-class over lists.

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

vector-transducibleconstant

u8vector-transducibleconstant

u16vector-transducibleconstant

u32vector-transducibleconstant

u64vector-transducibleconstant

s8vector-transducibleconstant

s16vector-transducibleconstant

s32vector-transducibleconstant

s64vector-transducibleconstant

f32vector-transducibleconstant

f64vector-transducibleconstant

c64vector-transducibleconstant

c128vector-transducibleconstant

Transducible type-classes over the various vector kinds.

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

(transducers mappings)

This module provides folders, collectors, and transducers for SRFI-146 mappings and SRFI-146 hashmaps. See the egg documentation for more information on SRFI-146.

Note that unlike SRFI-146, this egg doesn't make any module distinction between the hashmap and mapping imports. If you import (transducers mappings), you'll get all the bindings below regardless.

mapping-fold f sentinel mappingprocedure

hashmap-fold f sentinel hashmapprocedure

Fold operation over SRFI-146 mappings. Replaces the fold operation provided by the (srfi 146) module. These can be used with transducers in the following way:

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146)
        (srfi 146 hash)
        transducers)

(transduce mapping-fold
           values
           (collect-list)
           (mapping (make-default-comparator)
                    'a 1
                    'b 2
                    'c 3
                    'd 4))

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

reverse-mapping-fold f sentinel mappingprocedure

Like mapping-fold, but folds over the keys in reverse-order.

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146)
        transducers)

(transduce mapping-fold
           values
           (collect-list)
           (mapping (make-default-comparator)
                    'a 1
                    'b 2
                    'c 3
                    'd 4))

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

(collect-mapping #!optional (comparator (make-default-comparator)))procedure

(collect-hashmap #!optional (comparator (make-default-comparator)))procedure

Collects elements from a transduction into either a mapping or a hashmap with a given comparator. If no comparator is provided, the default comparator from SRFI-128 is used.

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146 hash)
        transducers)

(define hm
  (transduce list-fold
             (zip-list (list 'alpha 'beta 'gamma))
             (collect-hashmap (make-default-comparator))
             (list "asdf" "foo" "bar")))

;; We convert to an alist here purely for the sake of demonstrating the inner values.
;;
;; Otherwise srfi-146 would just print something like #<srfi.146.hash#<hashmap>>
(hashmap->alist hm)

; => (("foo" . beta) ("bar" . gamma) ("asdf" . alpha))

Note that you may find that the ordering of the final alist in the above example doesn't match 1:1 with how that hashmap is traversed locally. That is because no order is specified or assumed.

flatten-mappingprocedure

flatten-hashmapprocedure

A transducer that flattens any and all mappings or hashmaps (recursively) that it encounters, forwarding (key . value) pairs onto future transducers.

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146)
        transducers)

(define comp (make-default-comparator))

(transduce list-fold
           flatten-mapping
           (collect-list)
           (list (alist->mapping comp '((a . 1) (b . 2) (c . 3)))
                 (alist->mapping comp '((d . 4) (e . 5) (f . 6)))
                 (alist->mapping comp '((g . 7) (h . 8) (i . 9)))))

; => ((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6) (g . 7) (h . 8) (i . 9))

chain-mapping mappingprocedure

chain-reverse-mapping mappingprocedure

chain-hashmap hashmapprocedure

A transducer that chains all the (key . value) pairs in the relevant mapping / hashmap onto the current transduction.

chain-reverse-mapping chains the mapping in the reverse order of the keys, similar to how reverse-mapping-fold folds over the keys and values in a mapping in reverse order.

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146)
        (srfi 146 hash)
        transducers)

(transduce mapping-fold
           (chain-hashmap (hashmap (make-default-comparator)
                                   "foo" 'bar
                                   "fzz" 'baz))
           (collect-list)
           (mapping (make-default-comparator)
                    "abc" 'def
                    "eef" 'ghi))

; => (("abc" . def) ("eef" . ghi) ("fzz" . baz) ("foo" . bar))

interleave-mapping mappingprocedure

interleave-hashmap hashmapprocedure

A transducer that interleaves each of the (key . value) pairs in the relevant mapping / hashmap into the current transduction.

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146)
        (srfi 146 hash)
        transducers)

(transduce mapping-fold
           (interleave-hashmap (hashmap (make-default-comparator)
                               "foo" 'bar
                               "fzz" 'baz))
           (collect-list)
           (mapping (make-default-comparator)
                    "abc" 'def
                    "eef" 'ghi))

; => (("abc" . def) ("fzz" . baz) ("eef" . ghi) ("foo" . bar))

zip-mapping mappingprocedure

zip-hashmap hashmapprocedure

A transducer that zips each of the (key . value) pairs in the relevant mapping / hashmap over the current transduction.

 
(import (only (srfi 128)
              make-default-comparator)
        (srfi 146)
        (srfi 146 hash)
        transducers)

(transduce mapping-fold
           (zip-hashmap (hashmap (make-default-comparator)
                                 "foo" 'bar
                                 "fzz" 'baz))
           (collect-list)
           (mapping (make-default-comparator)
                    "abc" 'def
                    "eef" 'ghi))

; => ((("abc" . def) "fzz" . baz) (("eef" . ghi) "foo" . bar))

mapping-transducibleconstant

hashmap-transducibleconstant

Transducible type-classes over mappings and hashmaps.

License

The code is licensed under the MIT license:

 
Copyright (c) 2022-2023 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.