# CHICKEN Transducers

Transducers for working with foldable data types.

## Overview

This library provides an abstraction called "transducers." Originally, transducers were a [concept in
Clojure](https://www.youtube.com/watch?v=6mTbuzafcII), 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](https://wiki.call-cc.org/eggref/5/srfi-171), 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:

```bash
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.

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

```scheme
(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.

```scheme
(import transducers)
```

### Reporting issues

Please report issues [in the repository](https://gitlab.com/ThatGeoGuy/chicken-transducers/-/issues)
or on the [CHICKEN bug tracker](https://bugs.call-cc.org).

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

```scheme
(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:

```scheme
(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 &mdash; 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.

```scheme
((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:

```scheme
(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:

```scheme
(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:

```scheme
(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:

```scheme
(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:
  - Filter only the items for which `odd?` is true.
  - Drop the first item (for which `odd?` was true)
  - 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

    [record] <reduced>

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.

    [procedure] (make-reduced value)

Constructs a new `<reduced>` record holding the `value`.

    [procedure] (reduced? value)

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

    [procedure] (unwrap reduced)

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

```scheme
(import transducers)

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

    [procedure] (preserving-reduced transducer)

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](https://gitlab.com/ThatGeoGuy/chicken-transducers/-/blob/main/src/transducers.base.scm) for an
example of how it is used.

#### Collectors

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

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.

```scheme
(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
```
{{ }}

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

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.

```scheme
(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
```
{{ }}

    [procedure] (collect-count #!optional (sentinel 0))

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

```scheme
(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
```
{{ }}

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

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

```scheme
(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:

```scheme
(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:

```scheme
(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:

```scheme
(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:

```scheme
(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.

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

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

```scheme
(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
```
{{ }}

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

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

```scheme
(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
```
{{ }}

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

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:

```scheme
(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

    [procedure] (map f)

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

```scheme
(import transducers)

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

; => (3 6 9)
```
{{ }}

    [procedure] (filter pred?)
    [procedure] (remove pred?)

A transducer that `filter`s for or `remove`s items that satisfy `pred?`.

```scheme
(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)
```
{{ }}

    [procedure] (drop n)
    [procedure] (drop-while pred?)

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

```scheme
(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)
```
{{ }}

    [procedure] (take n)
    [procedure] (take-while n)

`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?`.

```scheme
(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)
```
{{ }}

    [procedure] (chunks n collector)
    [procedure] (chunks-exact n collector)

`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.

```scheme
(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`.

```scheme
(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))
```
{{ }}

    [procedure] enumerate

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

```scheme
(import transducers)

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

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

    [procedure] (inspect f)

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.

```scheme
(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)
```
{{ }}

    [syntax] (define-chain-transducer name folder)

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

```scheme
(import transducers)

(define-chain-transducer chain-list list-fold)
```
{{ }}

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

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.

```scheme
(define-flatten-transducer flatten-list list? list-fold)
```
{{ }}

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

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

```scheme
;; 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:

```scheme
(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.

    [procedure] (transduce folder transducers collector data)

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](https://wiki.call-cc.org/eggref/5/transducers#a-quick-tutorial) for a quick tutorial and a
more complete reference for how to use `transduce`.

    [procedure] (for-each folder transducers data)

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

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

    [procedure] (list-fold f sentinel lst)

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

```scheme
(import transducers)

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

; => (1 2 3)
```
{{ }}

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

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

```scheme
(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)
```
{{ }}

    [procedure] flatten-list

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

```scheme
(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)
```
{{ }}

    [procedure] (chain-list lst)

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

```scheme
(import transducers)

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

; => (a b c 1 2 3)
```
{{ }}

    [procedure] (interleave-list lst)

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.

```scheme
(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)
```
{{ }}

    [procedure] (zip-list lst)

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

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

    [record] <numeric-range>

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

    [procedure] (numeric-range? value)

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

    [procedure] (range-fold f sentinel numeric-range)
    [procedure] (fixnum-range-fold f sentinel numeric-range)

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.

```scheme
(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:

```scheme
(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.

    [procedure] (range start end)

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

    [procedure] (counter start #!optional (step 1))

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`.

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

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.

```scheme
(import transducers)

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

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

    [procedure] flatten-range

A transducer that flattens any ranges found in the transduction.

```scheme
(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)
```
{{ }}

    [procedure] (chain-range numeric-range)

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

```scheme
(import transducers)

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

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

    [procedure] (interleave-range numeric-range)

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.

```scheme
(import transducers)

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

; => (a 0 b 1 c 2)
```
{{ }}

    [procedure] (zip-range numeric-range)

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.

```scheme
(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:

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

    [procedure] (vector-fold f sentinel vec)
    [procedure] (u8vector-fold f sentinel vec)
    [procedure] (u16vector-fold f sentinel vec)
    [procedure] (u32vector-fold f sentinel vec)
    [procedure] (u64vector-fold f sentinel vec)
    [procedure] (s8vector-fold f sentinel vec)
    [procedure] (s16vector-fold f sentinel vec)
    [procedure] (s32vector-fold f sentinel vec)
    [procedure] (s64vector-fold f sentinel vec)
    [procedure] (f32vector-fold f sentinel vec)
    [procedure] (f64vector-fold f sentinel vec)
    [procedure] (c64vector-fold f sentinel vec)
    [procedure] (c128vector-fold f sentinel vec)

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

```scheme
(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.

    [procedure] (reverse-vector-fold f sentinel vec)
    [procedure] (reverse-u8vector-fold f sentinel vec)
    [procedure] (reverse-u16vector-fold f sentinel vec)
    [procedure] (reverse-u32vector-fold f sentinel vec)
    [procedure] (reverse-u64vector-fold f sentinel vec)
    [procedure] (reverse-s8vector-fold f sentinel vec)
    [procedure] (reverse-s16vector-fold f sentinel vec)
    [procedure] (reverse-s32vector-fold f sentinel vec)
    [procedure] (reverse-s64vector-fold f sentinel vec)
    [procedure] (reverse-f32vector-fold f sentinel vec)
    [procedure] (reverse-f64vector-fold f sentinel vec)
    [procedure] (reverse-c64vector-fold f sentinel vec)
    [procedure] (reverse-c128vector-fold f sentinel vec)

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.

```scheme
(import transducers)

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

; => #(3 2 1)
```
{{ }}

    [procedure] (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))

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.

```scheme
(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)
```
{{ }}

    [procedure] flatten-vector

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.

```scheme
(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)
```
{{ }}

    [procedure] (chain-vector vec)
    [procedure] (chain-u8vector vec)
    [procedure] (chain-u16vector vec)
    [procedure] (chain-u32vector vec)
    [procedure] (chain-u64vector vec)
    [procedure] (chain-s8vector vec)
    [procedure] (chain-s16vector vec)
    [procedure] (chain-s32vector vec)
    [procedure] (chain-s64vector vec)
    [procedure] (chain-f32vector vec)
    [procedure] (chain-f64vector vec)
    [procedure] (chain-c64vector vec)
    [procedure] (chain-c128vector vec)

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

```scheme
(import transducers)

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

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

    [procedure] (interleave-vector vec)
    [procedure] (interleave-u8vector vec)
    [procedure] (interleave-u16vector vec)
    [procedure] (interleave-u32vector vec)
    [procedure] (interleave-u64vector vec)
    [procedure] (interleave-s8vector vec)
    [procedure] (interleave-s16vector vec)
    [procedure] (interleave-s32vector vec)
    [procedure] (interleave-s64vector vec)
    [procedure] (interleave-f32vector vec)
    [procedure] (interleave-f64vector vec)
    [procedure] (interleave-c64vector vec)
    [procedure] (interleave-c128vector vec)

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.

```scheme
(import transducers)

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

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

    [procedure] (zip-vector vec)
    [procedure] (zip-u8vector vec)
    [procedure] (zip-u16vector vec)
    [procedure] (zip-u32vector vec)
    [procedure] (zip-u64vector vec)
    [procedure] (zip-s8vector vec)
    [procedure] (zip-s16vector vec)
    [procedure] (zip-s32vector vec)
    [procedure] (zip-s64vector vec)
    [procedure] (zip-f32vector vec)
    [procedure] (zip-f64vector vec)
    [procedure] (zip-c64vector vec)
    [procedure] (zip-c128vector vec)

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.

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

    [procedure] (reader-fold f sentinel vec)

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

```scheme
(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:

```scheme
(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)))
```
{{ }}

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

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

```scheme
(import (chicken port)
        transducers)

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

; => "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
```
{{ }}

    [procedure] (chain-reader reader)

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

```scheme
(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)
```
{{ }}

    [procedure] (interleave-reader reader)

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

```scheme
(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)
```
{{ }}

    [procedure] (zip-reader reader)

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

```scheme
(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:

```text
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.
```