-
-
Save Gozala/2656978 to your computer and use it in GitHub Desktop.
Array.prototype.reduce = this.ArrayReduce || Array.prototype.reduce | |
var console = window.console | |
var global = this | |
function assert(actual, expected) { | |
if (arguments.length < 2 && actual) | |
return actual | |
if (actual === expected) | |
return actual | |
if (JSON.stringify(actual) == JSON.stringify(expected)) | |
return JSON.stringify(actual) | |
throw TypeError('Assertion failed') | |
} | |
// Exploring clojure reducibles | |
// Some helper functions we'll use | |
function increment(x) { return x + 1 } | |
function isOdd(n) { return n % 2 } | |
// Creating generic `reduce` function | |
function reduce(f, items, start) { | |
return items.reduce(f, start) | |
} | |
new function() { | |
// Very basic approach | |
// Implement filter using reduce | |
function filter(f, items) { | |
return reduce(function(result, item) { | |
if (f(item)) result.push(item) | |
return result | |
}, items, []) | |
} | |
assert(filter(isOdd, [ 1, 2, 3, 4 ]), [ 1, 3 ]) | |
// Implement map using reduce | |
function map(f, items) { | |
return reduce(function(result, item) { | |
result.push(f(item)) | |
return result | |
}, items, []) | |
} | |
assert(map(increment, [ 1, 2, 3, 4 ]), [ 2, 3, 4, 5 ]) | |
// You can pipe filter and reduce | |
assert(map(increment, filter(isOdd, [ 1, 2, 3, 4 ])), [ 2, 4 ]) | |
} | |
new function() { | |
// now in previous examples we were pipeing results from | |
// filter to map. This is not very optimal, we could take | |
// a different approach of composing receipts of reduction | |
// instead of performing actual operations. | |
// Let's define "reducible" abstraction, which is an object | |
// implements `reduce` function with a same api as [].reduce | |
({ | |
reduce: function(f, start) { | |
// ... | |
} | |
}) | |
// Les define `reducible` high order function for creating | |
// objects implementing reducible abstraction | |
function reducible(reduce) { | |
return { reduce: reduce } | |
} | |
global.reducible = reducible | |
// Now let's define a function that would allow us to consume | |
// reducibles. | |
function array(reducible) { | |
// reduce reducible and colelect it's | |
// items into array which we return after. | |
return reduce(function(result, item) { | |
result.push(item) | |
return result | |
}, reducible, []) | |
} | |
global.array = array | |
// Array falls into our definition of reducibles so following | |
// should work | |
assert(array([ 1, 2, 3 ], [ 1, 2, 3 ])) | |
// Now we can define filter function, which will create new | |
// reducible instead of acutally performing reduce. | |
function filter(fx, items) { | |
return reducible(function(f, start) { | |
return reduce(function(result, item) { | |
if (fx(item)) return f(result, item) | |
return result | |
}, items, start) | |
}) | |
} | |
// Lets filter same array once again. | |
var filtered = filter(isOdd, [ 1, 2, 3, 4 ]) | |
// This time around we won't get array though. | |
assert(!Array.isArray(filtered)) | |
// But if we reduce it to array we wil get expceted result | |
assert(array(filtered), [ 1, 3 ]) | |
// Now let's define map function in similar manner: | |
function map(fx, items) { | |
return reducible(function(f, start) { | |
return reduce(function(result, item) { | |
return f(result, fx(item)) | |
}, items, start) | |
}) | |
} | |
// lets map same array once again | |
var mapped = map(increment, [ 1, 2, 3, 4 ]) | |
// This time around we won't get array either. | |
assert(!Array.isArray(filtered)) | |
// Although reducing to array will give us same result | |
assert(array(mapped), [ 2, 3, 4, 5 ]) | |
// Finally we can can compose new reducables in a | |
// similar way as we did with pipeing | |
var reduced = map(increment, filter(isOdd, [ 1, 2, 3, 4 ])) | |
// With a difference that no actions will take plase | |
assert(!Array.isArray(filtered)) | |
// Untill we reduce a result | |
assert(array(reduced), [ 2, 4 ]) | |
} | |
new function() { | |
// now most of the code in previous filter and map was | |
// a same boilerplate so we should be able to abstract | |
// it away | |
function reducer(process) { | |
return function(f, items) { | |
return reducible(function(next, start) { | |
return reduce(function(result, item) { | |
return process(f, next, result, item) | |
}, items, start) | |
}) | |
} | |
} | |
// now our filter function is reduced to actual logic | |
var filter = reducer(function(f, next, result, item) { | |
return f(item) ? next(result, item) : result | |
}) | |
// Lets filter same array once again. | |
var filtered = filter(isOdd, [ 1, 2, 3, 4 ]) | |
// This time we'll reducer again. | |
assert(!Array.isArray(filtered)) | |
// which can be reduced to same result | |
assert(array(filtered), [ 1, 3 ]) | |
var map = reducer(function(f, next, result, item) { | |
return next(result, f(item)) | |
}) | |
// lets map same array once again | |
var mapped = map(increment, [ 1, 2, 3, 4 ]) | |
// This time around we won't get array either. | |
assert(!Array.isArray(filtered)) | |
// Although reducing to array will give us same result | |
assert(array(mapped), [ 2, 3, 4, 5 ]) | |
// Finally we can can compose new reducables in a | |
// similar way as we did with pipeing | |
var reduced = map(increment, filter(isOdd, [ 1, 2, 3, 4 ])) | |
// With a difference that no actions will take plase | |
assert(!Array.isArray(filtered)) | |
// Untill we reduce a result | |
assert(array(reduced), [ 2, 4 ]) | |
} | |
new function() { | |
// Now lets reduce amount of arguments passed to reducers | |
function reducer(process) { | |
return function(f, items) { | |
return reducible(function(next, start) { | |
return reduce(function(result, item) { | |
var value = process(f, item) | |
return value !== undefined ? next(result, value) : result | |
}, items, start) | |
}) | |
} | |
} | |
global.reducer = reducer | |
// now our filter function is reduced to actual logic | |
var filter = reducer(function(f, item) { | |
if (f(item)) return item | |
}) | |
// Lets filter same array once again. | |
var filtered = filter(isOdd, [ 1, 2, 3, 4 ]) | |
// This time we'll reducer again. | |
assert(!Array.isArray(filtered)) | |
// which can be reduced to same result | |
assert(array(filtered), [ 1, 3 ]) | |
var map = reducer(function(f, item) { | |
return f(item) | |
}) | |
// lets map same array once again | |
var mapped = map(increment, [ 1, 2, 3, 4 ]) | |
// This time around we won't get array either. | |
assert(!Array.isArray(filtered)) | |
// Although reducing to array will give us same result | |
assert(array(mapped), [ 2, 3, 4, 5 ]) | |
// Finally we can can compose new reducables in a | |
// similar way as we did with pipeing | |
var reduced = map(increment, filter(isOdd, [ 1, 2, 3, 4 ])) | |
// With a difference that no actions will take plase | |
assert(!Array.isArray(filtered)) | |
// Untill we reduce a result | |
assert(array(reduced), [ 2, 4 ]) | |
} | |
new function() { | |
// now lets implement take for example | |
function pick(n, items) { | |
return reducer(function(f, item) { | |
if (n-- > 0) return item | |
})(null, items) | |
} | |
// this version is not very efficennt as it | |
// will reduce the whole thing even when it | |
// could stop half way through it | |
assert(array(pick(2, [ 2, 3, 4, 5 ])), [ 2, 3 ]) | |
} | |
new function() { | |
// Lets improve this so we could interrupt reduction | |
// as necessary. Define `reduced` function that will | |
// wrap result indicating that it's complete. | |
function reduced(value) { | |
return Object.create(reduced.prototype, { value: { value: value } }) | |
} | |
reduced.is = function is(value) { | |
return value && value.constructor === reduced | |
} | |
// Update our reducer implmentation to handel reduction | |
// interruption. | |
function reducer(process) { | |
return function(f, items) { | |
return reducible(function(next, start) { | |
return reduce(function(result, item) { | |
var value = process(f, item, reduced) | |
var ended = reduced.is(value) | |
value = ended ? value.value : value | |
result = value === undefined ? result : next(result, value) | |
return ended ? reduced(result) : result | |
}, items, start) | |
}) | |
} | |
} | |
global.reducer = reducer | |
// Change array reduce to add support for reduce | |
// interrupt. | |
ArrayReduce = Array.prototype.reduce | |
Array.prototype.reduce = function(f, start) { | |
var value, index, result = start | |
for (index = 0; index < this.length; index++) { | |
result = f(result, this[index]) | |
if (reduced.is(result)) return result.value | |
} | |
return result | |
} | |
// Implement take to take advantage of interrupt | |
var take = reducer(function take(f, item, last) { | |
return f(item) ? item : last() | |
}) | |
// Implement pick on top of take. | |
var pick = function(n, items) { | |
var count = n | |
return take(function(item) { | |
return count -- > 0 | |
}, items) | |
} | |
assert(array(pick(2, [ 2, 3, 4, 5 ])), [ 2, 3]) | |
assert(array(take(isOdd, [ 1, 3, 2, 3, 4, ])), [ 1, 3 ]) | |
} |
Resources:
http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html
http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html
clojure/clojure@68ec7ed
clojure/clojure@1f90942
clojure/clojure@f416abb
clojure/clojure@96e8596
https://github.com/clojure/clojure/blob/4a22e3a44df48ea0d37dd034bc3f6cb3092117a9/src/clj/clojure/core/reduce.clj
clojure/clojure@4a22e3a
https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj
Some performance comparison to native arrays http://jsperf.com/reducibles
Ok, so if we leave out interruption for reducibles it can go faster than native implementation:
http://jsperf.com/reducibles/2
And difference is even bigger on bigger data sets http://jsperf.com/reducibles/3
In many ways this seems is similar to my initial draft of streamer which is exciting! Also, I really like how interruption is designed, marking last desired item makes so much more sense! Now one thing that is very interesting to learn is weather it's possible or not to represent pull streams via reducibles. Pause consumption in some way, marking last item before pause may be a one way to do that.