@thi.ng/transducers

Lightweight transducer implementations for ES6 / TypeScript (7.6KB minified).

The library provides 28 transducers and 14 reducers for composing data transformation pipelines (more to come).

Installation

yarn add @thi.ng/transducers

Usage

import * as tx from "@thi.ng/transducers";

xform = tx.comp(
    tx.filter(x => (x & 1) > 0), // odd numbers only
    tx.distinct(),               // distinct numbers only
    tx.map(x=> x * 3)            // times 3
);

tx.transduce(xform, tx.push, [1, 2, 3, 4, 5, 4, 3, 2, 1]);
// [ 3, 9, 15 ]

tx.transduce(xform, tx.conj, [1, 2, 3, 4, 5, 4, 3, 2, 1]);
// Set { 3, 9, 15 }

for(let x of tx.iterator(xform, [1, 2, 3, 4])) {
    console.log(x);
}
// 3
// 9
// 15

tx.transduce(tx.map(x => x.toUpperCase()), tx.frequencies, "hello world")
// Map { 'H' => 1, 'E' => 1, 'L' => 3, 'O' => 2, ' ' => 1, 'W' => 1, 'R' => 1, 'D' => 1 }

tx.reduce(tx.frequencies, "hello world")
// Map { 'h' => 1, 'e' => 1, 'l' => 3, 'o' => 2, ' ' => 1, 'w' => 1, 'r' => 1, 'd' => 1 }

// early termination:
// result is realized after max. 7 values, irrespective of nesting
tx.transduce(
    tx.comp(tx.flatten(), tx.take(7)),
    tx.push,
    [1, [2, [3, 4, [5, 6, [7, 8], 9, [10]]]]]
)
// [1, 2, 3, 4, 5, 6, 7]

// this transducer uses 2 scans (a scan = inner reducer per item)
// 1) counts incoming values
// 2) forms an array of the current counter value `x` & repeated `x` times
// 3) emits results as series of reductions in the outer array produced
//    by the main reducer
// IMPORTANT: since arrays are mutable we use `pushCopy` as the inner reducer
// instead of `push` (the outer reducer)
xform = tx.comp(
    tx.scan(tx.count),
    tx.map(x => [...tx.iterator(tx.repeat(x), [x])]),
    tx.scan(tx.pushCopy)
);

tx.transduce(xform, tx.push, [1, 1, 1, 1]);
// [ [ [ 1 ] ],
//   [ [ 1 ], [ 2, 2 ] ],
//   [ [ 1 ], [ 2, 2 ], [ 3, 3, 3 ] ],
//   [ [ 1 ], [ 2, 2 ], [ 3, 3, 3 ], [ 4, 4, 4, 4 ] ] ]

// more simple & similar to previous, but without the 2nd xform step
tx.transduce(tx.comp(tx.scan(tx.count), tx.scan(tx.pushCopy)), tx.push, [1,1,1,1])
// [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 2, 3, 4 ] ]

f = tx.step(tx.dedupe());
f(1); // 1
f(2); // 2
f(2); // undefined -> skip repetiton
f(3); // 3
f(3); // undefined
f(3); // undefined
f(1); // 1

API

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.

interface Reducer<A, B> extends Array<any> {
    /**
     * Initialization, e.g. to provide a suitable accumulator value,
     * only called when no initial accumulator has been provided by user.
     */
    [0]: () => A,
    /**
     * Completion. When called usually just returns `acc`, but stateful
     * transformers should flush/apply their outstanding results.
     */
    [1]: (acc: A) => A,
    /**
     * Reduction step. Combines new input with accumulator.
     * If reduction should terminate early, wrap result via `reduced()`
     */
    [2]: (acc: A, x: B) => A | Reduced<A>,
}

// A concrete example:
const push: Reducer<any[], any> = [
    // init
    () => [],
    // completion
    (acc) => acc,
    // step
    (acc, x) => (acc.push(x), acc),
];

Currently only partition & partitionBy make use of the 1-arity completing function.

Reduced

class Reduced<T> implements IDeref<T> {
    protected value: T;
    constructor(val: T);
    deref(): T;
}

Simple type wrapper to identify early termination of a reducer. Does not modify wrapped value by injecting magic properties. 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

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<any, B>) => Reducer<any, A>;

// concrete example of stateless transducer (expanded for clarity)
function map<A, B>(fn: (x: A) => B): Transducer<A, B> {
    return (rfn: Reducer<any, B>) => {
        return [
            () => rfn[0](),
            (acc) => rfn[1](acc),
            (acc, x: A) => rfn[2](acc, fn(x))
        ];
    };
}

// stateful transducer
// removes successive value repetitions
function dedupe<T>(): Transducer<T, T> {
    return (rfn: Reducer<any, T>) => {
        // stateful initialization
        let prev = {};
        return [
            () => rfn[0](),
            (acc) => rfn[1](acc),
            (acc, x) => {
                acc = prev === x ? acc : rfn[2](acc, x);
                prev = x;
                return acc;
            }
        ];
    };
}

Transformations

reduce<A, B>(rfn: Reducer<A, B>, acc: A, xs: Iterable<B>): A

transduce<A, B, C>(tx: Transducer<A, B>, rfn: Reducer<C, B>, acc: C, xs: Iterable<A>): C

iterator<A, B>(tx: Transducer<A, B>, xs: Iterable<A>): IterableIterator<B>

comp(f1, f2, ...)

compR(rfn: Reducer<any, any>, fn: (acc, x) => any): Reducer<any, any>

Transducers

map<A, B>(fn: (x: A) => B): Transducer<A, B>

mapIndexed<A, B>(fn: (i: number, x: A) => B): Transducer<A, B>

mapcat<A, B>(fn: (x: A) => Iterable<B>): Transducer<A, B>

cat<A>(): Transducer<A[], A>

flatten<T>(): Transducer<T | Iterable<T>, T>

flattenOnly<T>(pred: Predicate<T>): Transducer<T | Iterable<T>, T>

selectKeys(...keys: PropertyKey[]): Transducer<any, any>

scan<A, B>(rfn: Reducer<B, A>, acc?: B): Transducer<A, B>

filter<T>(pred: Predicate<T>): Transducer<T, T>

throttle<T>(delay: number): Transducer<T, T>

delayed<T>(t: number): Transducer<T, Promise<T>>

distinct<T>(mapfn?: (x: T) => any): Transducer<T, T>

dedupe<T>(equiv?: (a: T, b: T) => boolean): Transducer<T, T>

interpose<A, B>(sep: B | (() => B)): Transducer<A, A | B>

interleave<A, B>(sep: B | (() => B)): Transducer<A, A | B>

take<T>(n: number): Transducer<T, T>

takeWhile<T>(pred: Predicate<T>): Transducer<T, T>

takeNth<T>(n: number): Transducer<T, T>

drop<T>(n: number): Transducer<T, T>

dropWhile<T>(pred: Predicate<T>): Transducer<T, T>

dropNth<T>(n: number): Transducer<T, T>

repeat<T>(n: number): Transducer<T, T>

sample<T>(prob: number): Transducer<T, T>

partition<T>(size: number, step?: number, all?: boolean): Transducer<T, T[]>

partitionBy<T>(fn: (x: T) => any): Transducer<T, T[]>

chunkSort<T>(n: number, key?: ((x: T) => any), cmp?: Comparator<any>): Transducer<T, T>

streamSort<T>(n: number, key?: ((x: T) => any), cmp?: Comparator<any>): Transducer<T, T>

streamShuffle<T>(n: number, maxSwaps?: number): Transducer<T, T>

Reducers

push: Reducer<any[], any>

pushCopy: Reducer<any[], any>

conj: Reducer<Set<any>, any>

assocObj: Reducer<any, [PropertyKey, any]>

assocMap: Reducer<Map<any, any>, [any, any]>

add: Reducer<number, number>

count: Reducer<number, number>

mul: Reducer<number, number>

min: Reducer<number, number>

max: Reducer<number, number>

frequencies: Reducer<Map<any, number>, any

Authors

• Karsten Schmidt

License

© 2016-2018 Karsten Schmidt // Apache Software License 2.0