[!NOTE]
This is one of 199 standalone projects, maintained as part
of the @thi.ng/umbrella monorepo
and anti-framework.
🚀 Please help me to work full-time on these projects by sponsoring me on
GitHub. Thank you! ❤️
About
Collection of ~170 lightweight, composable transducers, reducers, generators, iterators for functional data transformations.
This library provides altogether ~170 transducers, reducers, sequence generators
(ES6 generators/iterators) and additional supporting functions for composing
data transformation pipelines.
The overall concept and many of the core functions offered here are directly
inspired by the original Clojure implementation by Rich Hickey, though the
implementation does heavily differ (also in contrast to some other JS based
implementations) and dozens of less common, but generally highly useful
operators have been added. See full list below.
Furthermore, most transducers & reducers provided here accept an optional input
iterable, which allows them to be used directly as transformers instead of
having to wrap them in one of the execution functions (i.e.
transduce()
/transduceRight()
, reduce()
/reduceRight()
, iterator()
,
run()
, step()
). If called this way, transducer functions will return a
transforming ES6 iterator (generator) and reducing functions will return a
reduced result of the given input iterable.
Status
STABLE - used in production
Search or submit any issues for this package
9.0.0 release
This release corrects a longstanding stylistic issue regarding the order of
generic type args given to Reducer<A, B>
, which now uses the
swapped & more logical order (i.e. reduce from A
to B
) and is the same order
of generic type args for Transducer
and AsyncTransducer
/ AsyncReducer
(in
the thi.ng/transducers-async
package).
Most userland code should be unimpacted by this change - this is only a breaking
change for custom reducer impls.
Support packages
Related packages
Blog posts
Installation
yarn add @thi.ng/transducers
ESM import:
import * as tx from "@thi.ng/transducers";
Browser ESM import:
<script type="module" src="https://esm.run/@thi.ng/transducers"></script>
JSDelivr documentation
For Node.js REPL:
const tx = await import("@thi.ng/transducers");
Package sizes (brotli'd, pre-treeshake): ESM: 9.05 KB
Dependencies
Note: @thi.ng/api is in most cases a type-only import (not used at runtime)
Usage examples
72 projects in this repo's
/examples
directory are using this package:
Screenshot | Description | Live demo | Source |
---|
| Interactive image processing (adaptive threshold) | Demo | Source |
| ASCII art raymarching with thi.ng/shader-ast & thi.ng/text-canvas | Demo | Source |
| Large ASCII font text generator using @thi.ng/rdom | Demo | Source |
| Figlet-style bitmap font creation with transducers | Demo | Source |
| Self-modifying, animated typographic grid with emergent complex patterns | Demo | Source |
| 2D transducer based cellular automata | Demo | Source |
| Heatmap visualization of this mono-repo's commits | | Source |
| Filterable commit log UI w/ minimal server to provide commit history | Demo | Source |
| Basic crypto-currency candle chart with multiple moving averages plots | Demo | Source |
| Color palette generation via dominant color extraction from uploaded images | Demo | Source |
| Interactive visualization of closest points on ellipses | Demo | Source |
| Interactive inverse FFT toy synth | Demo | Source |
| Fiber-based cooperative multitasking basics | Demo | Source |
| Shape conversions & operations using polygons with holes | Demo | Source |
| Piechart visualization of CSV data | Demo | Source |
| Hex grid generation & tessellations | Demo | Source |
| GPU-based data reduction using thi.ng/shader-ast & WebGL multi-pass pipeline | Demo | Source |
| Visualization of different grid iterator strategies | Demo | Source |
| hdom update performance benchmark w/ config options | Demo | Source |
| Realtime analog clock demo | Demo | Source |
| Interactive pattern drawing demo using transducers | Demo | Source |
| Various hdom-canvas shape drawing examples & SVG conversion / export | Demo | Source |
| Custom dropdown UI component w/ fuzzy search | Demo | Source |
| Isolated, component-local DOM updates | Demo | Source |
| Basic hiccup-based canvas drawing | Demo | Source |
| Canvas based Immediate Mode GUI components | Demo | Source |
| Animated sine plasma effect visualized using contour lines | Demo | Source |
| Transforming JSON into UI components | Demo | Source |
| Randomized space-filling, nested grid layout generator | Demo | Source |
| Browser REPL for a Lispy S-expression based mini language | Demo | Source |
| Worker based, interactive Mandelbrot visualization | Demo | Source |
| Mastodon API feed reader with support for different media types, fullscreen media modal, HTML rewriting | Demo | Source |
| CLI util to visualize umbrella pkg stats | | Source |
| Parser grammar livecoding editor/playground & codegen | Demo | Source |
| RGB waveform image analysis | Demo | Source |
| Polygon to cubic curve conversion & visualization | Demo | Source |
| Animated, iterative polygon subdivisions & visualization | Demo | Source |
| Procedural stochastic text generation via custom DSL, parse grammar & AST transformation | Demo | Source |
| Unison wavetable synth with waveform editor | Demo | Source |
| Demonstates various rdom usage patterns | Demo | Source |
| Minimal rdom-canvas animation | Demo | Source |
| rstream & transducer-based FSM for converting key event sequences into high-level commands | Demo | Source |
| rdom & hiccup-canvas interop test | Demo | Source |
| Full umbrella repo doc string search w/ paginated results | Demo | Source |
| rdom powered SVG graph with draggable nodes | Demo | Source |
| Defining & using basic Web Components (with shadow DOM) via @thi.ng/rdom & @thi.ng/meta-css | Demo | Source |
| Responsive image gallery with tag-based Jaccard similarity ranking | Demo | Source |
| Generative audio synth offline renderer and WAV file export | Demo | Source |
| Animated Voronoi diagram, cubic splines & SVG download | Demo | Source |
| Minimal rstream dataflow graph | Demo | Source |
| Minimal demo of using rstream constructs to form an interceptor-style event loop | Demo | Source |
| Interactive grid generator, SVG generation & export, undo/redo support | Demo | Source |
| rstream based UI updates & state handling | Demo | Source |
| Minimal rstream sync() example using rdom | Demo | Source |
| 2D scenegraph & shape picking | Demo | Source |
| Shader-AST meta-programming techniques for animated function plots | Demo | Source |
| Fork-join worker-based raymarch renderer (JS/CPU only) | Demo | Source |
| Simplistic SVG bar chart component | Demo | Source |
| SVG path parsing & dynamic resampling | Demo | Source |
| Additive waveform synthesis & SVG visualization with undo/redo | Demo | Source |
| hdom based slide deck viewer & slides from my ClojureX 2018 keynote | Demo | Source |
| Tree-based UI to find & explore thi.ng projects via their associated keywords | Demo | Source |
| Multi-layer vectorization & dithering of bitmap images | Demo | Source |
| Triple store query results & sortable table | Demo | Source |
| Interactive ridge-line plot | Demo | Source |
| rdom & WebGL-based image channel editor | Demo | Source |
| WebGL multi-colored cube mesh | Demo | Source |
| Drawing to floating point offscreen / multi-pass shader pipeline | Demo | Source |
| WebGL instancing, animated grid | Demo | Source |
| WebGL MSDF text rendering & particle system | Demo | Source |
| 1D Wolfram automata with OBJ point cloud export | Demo | Source |
| XML/HTML/SVG to hiccup/JS conversion | Demo | Source |
Basic usage patterns
import { comp, distinct, filter, map } from "@thi.ng/transducers";
xform = comp(
filter((x) => (x & 1) > 0),
distinct(),
map((x) => x * 3)
);
import { transduce, push } from "@thi.ng/transducers";
transduce(xform, push(), [1, 2, 3, 4, 5, 4, 3, 2, 1]);
transduce(xform, conj(), [1, 2, 3, 4, 5, 4, 3, 2, 1]);
import { iterator } from "@thi.ng/transducers";
[...iterator(xform, [1, 2, 3, 4, 5])]
[...filter((x) => /[A-Z]/.test(x), "Hello World!")]
import { step } from "@thi.ng/transducers";
f = step(xform);
f(1)
f(2)
f(3)
f(4)
f = step(take)
Interpolation & SVG generation
This example uses the
@thi.ng/geom
package for quick SVG generation.
import { asSvg, svgDoc, circle, polyline } from "@thi.ng/geom";
const values = [5, 10, 4, 8, 20, 2, 11, 7];
const vertices = [...iterator(
comp(
interpolateHermite(10),
mapIndexed((x, y) => [x, y])
),
extendSides(values, 1, 2)
)];
asSvg(
svgDoc(
{ width: 800, height: 200, "stroke-width": 0.1 },
polyline(vertices, { stroke: "red" }),
...values.map((y, x) => circle([x * 10, y], 0.2))
)
)
Fuzzy search
import { filterFuzzy } from "@thi.ng/transducers";
[...filterFuzzy("ho", ["hello", "hallo", "hey", "heyoka"])]
[...filterFuzzy("hlo", ["hello", "hallo", "hey", "heyoka"])]
[...filterFuzzy(
[1, 3],
{ key: (x) => x.tags },
[
{ tags: [1, 2, 3] },
{ tags: [2, 3, 4] },
{ tags: [4, 5, 6] },
{ tags: [1, 3, 6] }
]
)]
Histogram generation & result grouping
import { frequencies, map, reduce, transduce } from "@thi.ng/transducers";
transduce(map((x) => x.toUpperCase()), frequencies(), "hello world");
reduce(frequencies(), [1, 1, 1, 2, 3, 4, 4]);
frequencies([1, 1, 1, 2, 3, 4, 4]);
frequencies(
(x) => x.length,
"my camel is collapsing and needs some water".split(" ")
);
import { groupByMap } from "@thi.ng/transducers";
groupByMap(
{ key: (x) => x.length },
"my camel is collapsing and needs some water".split(" ")
);
import { page, comp, iterator, map, padLast, range } from "@thi.ng/transducers";
[...page(0, 5, range(12))]
[...iterator(comp(page(1, 5), map(x => x * 10)), range(12))]
[...iterator(comp(page(2, 5), padLast(5, "n/a")), range(12))]
[...page(3, 5, range(12))]
Multiplexing / parallel transducer application
multiplex
and multiplexObj
can be used to transform values in
parallel using the provided transducers (which can be composed as usual)
and results in a tuple or keyed object.
import { map, multiplex, multiplexObj, push, transduce } from "@thi.ng/transducers";
transduce(
multiplex(
map((x) => x.charAt(0)),
map((x) => x.toUpperCase()),
map((x) => x.length)
),
push(),
["Alice", "Bob", "Charlie"]
);
transduce(
multiplexObj({
initial: map((x) => x.charAt(0)),
name: map((x) => x.toUpperCase()),
len: map((x) => x.length)
}),
push(),
["Alice", "Bob", "Charlie"]
);
Moving average using sliding window
import { comp, map, mean, partition, push, reduce transduce } from "@thi.ng/transducers";
transduce(
comp(
partition(5, 1),
map(x => reduce(mean(), x))
),
push(),
[1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10]
)
This combined transducer is also directly available as:
import { movingAverage } from "@thi.ng/transducers";
[...movingAverage(5, [1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10])]
Benchmark function execution time
import { benchmark, mean, repeatedly, transduce } from "@thi.ng/transducers";
fn = () => {
let x;
for (i = 0; i < 1e6; i++) {
x = Math.cos(i);
}
return x;
};
transduce(benchmark(), mean(), repeatedly(fn, 100));
Apply inspectors to debug transducer pipeline
import { comp, filter, map, push, trace, transduce } from "@thi.ng/transducers";
transduce(
comp(
trace("orig"),
map((x) => x + 1),
trace("mapped"),
filter((x) => (x & 1) > 0)
),
push(),
[1, 2, 3, 4]
);
Stream parsing / structuring
The struct
transducer is simply a composition of: partitionOf -> partition -> rename -> mapKeys
. See code
here.
import { struct } from "@thi.ng/transducers";
[
...struct(
[["id", 1, (id) => id[0]], ["pos", 2], ["vel", 2], ["color", 4]],
[0, 100, 200, -1, 0, 1, 0.5, 0, 1, 1, 0, 0, 5, 4, 0, 0, 1, 1]
)
];
CSV parsing
import { comp, map, mapcat, push, rename, transduce } from "@thi.ng/transducers";
transduce(
comp(
mapcat((x) => x.split("\n")),
map((x) => x.split(",")),
rename({ id: 0, name: 1, alias: 2, num: "length" })
),
push(),
["100,typescript\n101,clojure,clj\n110,rust,rs"]
);
Early termination
import { comp, flatten, push, take, transduce } from "@thi.ng/transducers";
transduce(comp(flatten(), take(7)), push(), [
1,
[2, [3, 4, [5, 6, [7, 8], 9, [10]]]]
]);
Scan operator
import {
comp, count, iterator, map, push, pushCopy, repeat, scan, transduce
} from "@thi.ng/transducers";
xform = comp(
scan(count()),
map(x => [...repeat(x,x)]),
scan(pushCopy())
)
[...iterator(xform, [1, 1, 1, 1])]
transduce(comp(scan(count()), scan(pushCopy())), push(), [1,1,1,1])
Weighted random choices
import { choices, frequencies, take, transduce } from "@thi.ng/transducers";
[...take(10, choices("abcd", [1, 0.5, 0.25, 0.125]))]
transduce(
take(1000),
frequencies(),
choices("abcd", [1, 0.5, 0.25, 0.125])
);
Keyframe interpolation
See
tween()
docs for details.
import { tween } from "@thi.ng/transducers";
[
...tween(
10,
0,
100,
(a, b) => [a, b],
([a, b], t) => Math.floor(a + (b - a) * t),
[20, 100],
[50, 200],
[80, 0]
)
];
API
Generated API docs
Types
Apart from type aliases, the only real types defined are:
Reducer
Reducers are the core building blocks of transducers. Unlike other
implementations using OOP approaches, a Reducer
in this lib is a simple
3-element array of functions, each addressing a separate processing step.
The bundled reducers are all wrapped in functions to provide a uniform API (and
some of them can be preconfigured and/or are stateful closures). However, it's
completely fine to define stateless reducers as constant arrays.
A Reducer
is a 3-tuple of functions defining the different stages of a
reduction process: A Reducer<A, B>
reduces values of type A to a single value
of type B.
The tuple items/functions in order:
- Initialization function used to produce an initial default result (only used
if no such initial result was given by the user)
- Completion function to post-process an already reduced result (for most
reducers this is merely the identity function)
- Accumulation function, merging a new input value with the currently existing
(partially) reduced result/accumulator
type Reducer<A, B> = [
() => B,
(x: B) => B,
(acc: B, x: A) => B
];
const push: Reducer<any, any[]> = [
() => [],
(acc) => acc,
(acc, x) => (acc.push(x), acc)
];
Reduced
Simple type wrapper to mark & identify a reducer's early termination. Does not
modify wrapped value by injecting magic properties.
import type { IDeref } from "@thi.ng/api";
class Reduced<T> implements IDeref<T> {
protected value: T;
constructor(val: T);
deref(): T;
}
Instances can be created via reduced(x)
and handled via these helper
functions:
reduced(x: any): any
isReduced(x: any): boolean
ensureReduced(x: any): Reduced<any>
unreduced(x: any): any
IReducible
By default reduce()
consumes inputs via the standard ES6 Iterable
interface,
i.e. using a for..of..
loop, but the function also supports optimized routes
for some types: Array-like inputs are consumed via a traditional for
-loop and
custom optimized iterations can be provided via implementations of the
IReducible
interface in the source collection type. Examples can be found
here:
Note: The IReducible
interface is only used by reduce()
, transduce()
and run()
.
Transducer
From Rich Hickey's original definition:
A transducer is a transformation from one reducing function to another
As shown in the examples above, transducers can be dynamically composed (using
comp()
) to form arbitrary data transformation pipelines without causing large
overheads for intermediate collections.
type Transducer<A, B> = (rfn: Reducer<B, any>) => Reducer<A, any>;
function map<A, B>(fn: (x: A) => B): Transducer<A, B> {
return ([init, complete, reduce]: Reducer<B, any>) => {
return <Reducer<A, any>>[
init,
complete,
(acc, x: A) => reduce(acc, fn(x))
];
};
}
function dedupe<T>(): Transducer<T, T> {
return ([init, complete, reduce]: Reducer<T, any>) => {
let prev = {};
return <Reducer<T, any>>[
init,
complete,
(acc, x) => {
if (prev !== x) acc = reduce(acc, x);
prev = x;
return acc;
}
];
};
}
IXform interface
Interface for types able to provide some internal functionality (or derive some
related transformation) as Transducer
. Implementations of this interface can
be directly passed to all functions in this package where a Transducer
arg is
expected.
import { map, push, range, transduce, type IXform } from "@thi.ng/transducers";
class Mul implements IXform<number, number> {
constructor(public factor = 10) {}
xform() {
return map((x) => this.factor * x);
}
}
transduce(new Mul(11), push(), range(4))
import { comp, drop, push, range, takeNth, transduce } from "@thi.ng/transducers";
transduce(
comp(drop(1), new Mul(11), takeNth(2)),
push(),
range(4)
)
Composition & execution
comp
comp(f1, f2, ...)
Returns new transducer composed from given transducers. Data flow is from left
to right. Offers fast paths for up to 10 args. If more are given, composition is
done dynamically via for loop.
compR
compR(rfn: Reducer<any, any>, fn: (acc, x) => any): Reducer<any, any>
Helper function to compose reducers.
iterator
iterator<A, B>(tx: Transducer<A, B>, xs: Iterable<A>): IterableIterator<B>
Similar to transduce()
, but emits results as ES6 iterator (and hence doesn't
use a reduction function).
reduce
reduce<A, B>(rfn: Reducer<A, B>, acc?: A, xs: Iterable<B>): A
Reduces xs
using given reducer and optional initial accumulator/result. If
xs
implements the IReducible
interface, delegates to that implementation.
Likewise, uses a fast route if xs
is an ArrayLike
type.
reduceRight
reduceRight<A, B>(rfn: Reducer<A, B>, acc?: A, xs: ArrayLike<B>): A
Similar to reduce
, however only accepts ArrayLike
sources and reduces them
into right-to-left order.
transduce
transduce<A, B, C>(tx: Transducer<A, B>, rfn: Reducer<C, B>, acc?: C, xs: Iterable<A>): C
Transforms iterable using given transducer and combines results with given
reducer and optional initial accumulator/result.
transduceRight
transduceRight<A, B, C>(tx: Transducer<A, B>, rfn: Reducer<C, B>, acc?: C, xs: ArrayLike<A>): C
Similar to transduce
, however only accepts ArrayLike
sources and processes
them into right-to-left order.
run
run<A, B>(tx: Transducer<A, B>, fx: (x: B) => void, xs: Iterable<A>)
Transforms iterable with given transducer and optional side effect without any
reduction step. If fx
is given it will be called with every value produced by
the transducer. If fx
is not given, the transducer is assumed to include at
least one sideEffect()
step itself. Returns nothing.
consume
consume(src: Iterable<any>): void
Similar to run()
, consumes given iterable, presumably for any implicit
side-effects. Iterable MUST be finite!
import { consume, repeatedly2d } from "@thi.ng/transducers";
consume(repeatedly2d((x, y) => console.log("output:", [x, y]), 2, 3));
Transducers
All of the following functions can be used and composed as transducers. With a
few exceptions, most also accept an input iterable and then directly yield a
transforming iterator, e.g.
import { map, push, range, transduce } from "@thi.ng/transducers";
transduce(map((x) => x*10), push(), range(4))
[...map((x) => x*10, range(4))]
Generators / Iterators
Reducers
As with transducer functions, reducer functions can also given an optional input
iterable. If done so, the function will consume the input and return a reduced
result (as if it would be called via reduce()
).
Authors
If this project contributes to an academic publication, please cite it as:
@misc{thing-transducers,
title = "@thi.ng/transducers",
author = "Karsten Schmidt and others",
note = "https://thi.ng/transducers",
year = 2016
}
License
© 2016 - 2024 Karsten Schmidt // Apache License 2.0