Experimenting with clojure reducers

reducers.js

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