@thi.ng/transducers - npm Package Compare versions

Comparing version 0.3.2 to 0.4.0

index.d.ts

@@ -1,2 +0,2 @@
-import { IDeref, Predicate } from "@thi.ng/api";
+import { Comparator, IDeref, Predicate } from "@thi.ng/api";
 export declare type Transducer<A, B> = (rfn: Reducer<any, B>) => Reducer<any, A>;
@@ -27,4 +27,9 @@ export interface Reducer<A, B> extends Array<any> {
 export declare function map<A, B>(fn: (x: A) => B): Transducer<A, B>;
+export declare function selectKeys(...keys: PropertyKey[]): Transducer<any, any>;
 export declare function mapIndexed<A, B>(fn: (i: number, x: A) => B): Transducer<A, B>;
 export declare function mapcat<A, B>(fn: (x: A) => Iterable<B>): Transducer<A, B>;
+export declare function cat<T>(): Transducer<T[], T>;
+export declare function flatten<T>(): Transducer<T | Iterable<T>, T>;
+export declare function flattenOnly<T>(pred: Predicate<T>): Transducer<T | Iterable<T>, T>;
+export declare function scan<A, B>(inner: Reducer<B, A>, acc?: B): Transducer<A, B>;
 export declare function filter<T>(pred: Predicate<T>): Transducer<T, T>;
@@ -47,5 +52,7 @@ export declare function throttle<T>(delay: number): Transducer<T, T>;
 export declare function partitionBy<T>(fn: (x: T) => any): Transducer<T, T[]>;
-export declare function chunkSort<T>(n: number, key?: ((x) => any)): Transducer<T, T>;
-export declare function streamSort<T>(n: number, key?: ((x) => any)): Transducer<T, T>;
+export declare function chunkSort<T>(n: number, key?: ((x: T) => any), cmp?: Comparator<any>): Transducer<T, T>;
+export declare function streamSort<T>(n: number, key?: ((x: T) => any), cmp?: Comparator<any>): Transducer<T, T>;
+export declare function streamShuffle<T>(n: number, maxSwaps?: number): Transducer<T, T>;
 export declare const push: Reducer<any[], any>;
+export declare const pushCopy: Reducer<any[], any>;
 export declare const conj: Reducer<Set<any>, any>;
@@ -55,4 +62,9 @@ export declare const assocObj: Reducer<any, [PropertyKey, any]>;
 export declare const add: Reducer<number, number>;
+export declare const count: Reducer<number, number>;
 export declare const mul: Reducer<number, number>;
+export declare const min: Reducer<number, number>;
+export declare const max: Reducer<number, number>;
+export declare function minCompare<T>(ident: () => T, cmp?: Comparator<T>): Reducer<T, T>;
+export declare function maxCompare<T>(ident: () => T, cmp?: Comparator<T>): Reducer<T, T>;
 export declare const frequencies: Reducer<Map<any, number>, any>;
-export declare const noop: Reducer<any, any>;
+export declare const last: Reducer<any, any>;

index.js

@@ -76,3 +76,3 @@ "use strict";
 function step(tx) {
-    const rfn = tx(exports.noop)[2];
+    const rfn = tx(exports.last)[2];
     return (x) => rfn(undefined, x);
@@ -144,2 +144,25 @@ }
 exports.map = map;
+function selectKeys(...keys) {
+    const [a, b, c] = keys;
+    switch (keys.length) {
+        case 0:
+            throw new Error(`no keys given`);
+        case 1:
+            return map((x) => x[a]);
+        case 2:
+            return map((x) => ({ [a]: x[a], [b]: x[b] }));
+        case 3:
+            return map((x) => ({ [a]: x[a], [b]: x[b], [c]: x[c] }));
+        default:
+            return map((x) => {
+                const res = {};
+                for (let i = keys.length - 1; i >= 0; i--) {
+                    const k = keys[i];
+                    res[k] = x[k];
+                }
+                return res;
+            });
+    }
+}
+exports.selectKeys = selectKeys;
 function mapIndexed(fn) {
@@ -154,8 +177,11 @@ return (rfn) => {
 function mapcat(fn) {
+    return comp(map(fn), cat());
+}
+exports.mapcat = mapcat;
+function cat() {
     return (rfn) => {
         const r = rfn[2];
         return compR(rfn, (acc, x) => {
-            const xs = fn(x);
-            if (xs) {
-                for (let y of xs) {
+            if (x) {
+                for (let y of x) {
                     acc = r(acc, y);
@@ -171,3 +197,39 @@ if (isReduced(acc)) {
 }
-exports.mapcat = mapcat;
+exports.cat = cat;
+function flatten() {
+    return flattenOnly((x) => x != null && x[Symbol.iterator] && typeof x !== "string");
+}
+exports.flatten = flatten;
+function flattenOnly(pred) {
+    return (rfn) => {
+        const r = rfn[2], fn = (acc, x) => {
+            if (pred(x)) {
+                for (let y of x) {
+                    acc = fn(acc, y);
+                    if (isReduced(acc)) {
+                        break;
+                    }
+                }
+                return acc;
+            }
+            return r(acc, x);
+        };
+        return compR(rfn, fn);
+    };
+}
+exports.flattenOnly = flattenOnly;
+function scan(inner, acc) {
+    return (outer) => {
+        acc = acc || inner[0]();
+        const ri = inner[2], ro = outer[2];
+        return compR(outer, (_acc, x) => {
+            acc = ri(acc, x);
+            if (isReduced(acc)) {
+                return ensureReduced(ro(_acc, acc.deref()));
+            }
+            return ro(_acc, acc);
+        });
+    };
+}
+exports.scan = scan;
 function filter(pred) {
@@ -403,11 +465,11 @@ return (rfn) => {
 exports.partitionBy = partitionBy;
-function chunkSort(n, key = identity) {
-    return comp(partition(n, n, true), mapcat((chunk) => chunk.sort((a, b) => compare_1.compare(key(a), key(b)))));
+function chunkSort(n, key = identity, cmp = compare_1.compare) {
+    return comp(partition(n, n, true), mapcat((chunk) => chunk.sort((a, b) => cmp(key(a), key(b)))));
 }
 exports.chunkSort = chunkSort;
-function binarySearch(arr, key, x) {
+function binarySearch(arr, key, cmp, x) {
     const kx = key(x);
     let low = 0, high = arr.length - 1;
     while (low <= high) {
-        const mid = (low + high) >>> 1, c = compare_1.compare(key(arr[mid]), kx);
+        const mid = (low + high) >>> 1, c = cmp(key(arr[mid]), kx);
         if (c < 0) {
@@ -425,3 +487,3 @@ low = mid + 1;
 }
-function streamSort(n, key = identity) {
+function streamSort(n, key = identity, cmp = compare_1.compare) {
     return ([i, c, r]) => {
@@ -439,3 +501,3 @@ const buf = [];
             (acc, x) => {
-                buf.splice(binarySearch(buf, key, x), 0, x);
+                buf.splice(binarySearch(buf, key, cmp, x), 0, x);
                 if (buf.length === n) {
@@ -450,2 +512,36 @@ acc = r(acc, buf.shift());
 exports.streamSort = streamSort;
+function shuffle(buf, n) {
+    const l = buf.length;
+    n = n < l ? n : l;
+    while (--n >= 0) {
+        const a = (Math.random() * l) | 0, b = (Math.random() * l) | 0, t = buf[a];
+        buf[a] = buf[b];
+        buf[b] = t;
+    }
+}
+function streamShuffle(n, maxSwaps = n) {
+    return ([i, c, r]) => {
+        const buf = [];
+        return [
+            () => i(),
+            (acc) => {
+                while (buf.length && !isReduced(acc)) {
+                    shuffle(buf, maxSwaps);
+                    acc = r(acc, buf.shift());
+                }
+                acc = c(acc);
+                return acc;
+            },
+            (acc, x) => {
+                buf.push(x);
+                shuffle(buf, maxSwaps);
+                if (buf.length === n) {
+                    acc = r(acc, buf.shift());
+                }
+                return acc;
+            }
+        ];
+    };
+}
+exports.streamShuffle = streamShuffle;
 exports.push = [
@@ -456,2 +552,7 @@ () => [],
 ];
+exports.pushCopy = [
+    () => [],
+    (acc) => acc,
+    (acc, x) => ((acc = acc.slice()).push(x), acc)
+];
 exports.conj = [
@@ -474,10 +575,41 @@ () => new Set(),
     () => 0,
-    (x) => x,
-    (x, y) => x + y,
+    (acc) => acc,
+    (acc, x) => acc + x,
 ];
+exports.count = [
+    () => 0,
+    (acc) => acc,
+    (acc, _) => acc + 1,
+];
 exports.mul = [
     () => 1,
-    (x) => x,
-    (x, y) => x * y,
+    (acc) => acc,
+    (acc, x) => acc * x,
 ];
+exports.min = [
+    () => Number.POSITIVE_INFINITY,
+    (acc) => acc,
+    (acc, x) => Math.min(acc, x),
+];
+exports.max = [
+    () => Number.NEGATIVE_INFINITY,
+    (acc) => acc,
+    (acc, x) => Math.max(acc, x),
+];
+function minCompare(ident, cmp = compare_1.compare) {
+    return [
+        ident,
+        (acc) => acc,
+        (acc, x) => cmp(acc, x) <= 0 ? acc : x
+    ];
+}
+exports.minCompare = minCompare;
+function maxCompare(ident, cmp = compare_1.compare) {
+    return [
+        ident,
+        (acc) => acc,
+        (acc, x) => cmp(acc, x) >= 0 ? acc : x
+    ];
+}
+exports.maxCompare = maxCompare;
 exports.frequencies = [
@@ -488,3 +620,3 @@ () => new Map(),
 ];
-exports.noop = [
+exports.last = [
     () => undefined,
@@ -491,0 +623,0 @@ (acc) => acc,

package.json

 {
     "name": "@thi.ng/transducers",
-    "version": "0.3.2",
+    "version": "0.4.0",
     "description": "Lightweight transducer implementations for ES6 / TypeScript",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -5,4 +5,7 @@ # @thi.ng/transducers
 
-Lightweight transducer implementations for ES6 / TypeScript (6KB minified).
+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
@@ -12,3 +15,2 @@
 yarn add @thi.ng/transducers
-yarn run build
 ```
@@ -33,2 +35,9 @@
 
+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")
@@ -40,10 +49,38 @@ // Map { 'H' => 1, 'E' => 1, 'L' => 3, 'O' => 2, ' ' => 1, 'W' => 1, 'R' => 1, 'D' => 1 }
 
-for(let x of tx.iterator(xform, [1, 2, 3, 4])) {
-    console.log(x);
-}
+// 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
+f(2); // undefined -> skip repetiton
 f(3); // 3
@@ -56,11 +93,58 @@ f(3); // undefined
 ### API
+### Types
 
-TODO
+Apart from type aliases, the only real types defined are:
 
-#### `reduce<A, B>(rfn: Reducer<A, B>, acc: A, xs: Iterable<B>): A`
+#### Reducer
 
-#### `transduce<A, B, C>(tx: Transducer<A, B>, rfn: Reducer<C, B>, acc: C, xs: Iterable<A>): C`
+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.
 
-#### `iterator<A, B>(tx: Transducer<A, B>, xs: Iterable<A>): IterableIterator<B>`
+```typescript
+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
+
+```typescript
+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`
@@ -74,2 +158,53 @@
 
+### 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.
+
+```typescript
+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, ...)`
@@ -87,2 +222,12 @@
 
+#### `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>`
@@ -122,6 +267,8 @@
 
-#### `chunkSort<T>(n: number, key?: (x) => any): Transducer<T, T>`
+#### `chunkSort<T>(n: number, key?: ((x: T) => any), cmp?: Comparator<any>): Transducer<T, T>`
 
-#### `streamSort<T>(n: number, key?: (x) => 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
@@ -131,2 +278,4 @@
 
+#### `pushCopy: Reducer<any[], any>`
+
 #### `conj: Reducer<Set<any>, any>`
@@ -140,4 +289,10 @@
 
+#### `count: Reducer<number, number>`
+
 #### `mul: Reducer<number, number>`
 
+#### `min: Reducer<number, number>`
+
+#### `max: Reducer<number, number>`
+
 #### `frequencies: Reducer<Map<any, number>, any`
@@ -144,0 +299,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

28756

increased by45.2%

Lines of code

681

increased by26.82%

Number of lines in readme file

296

increased by109.93%

No dependency changes