CODEWITHSUNDEEP
javascriptunderscore.jsreduce
user6378390
user6378390

Reputation:

Creating the underscore reduce function from scratch

I am working on creating my own callback functions and higher order function groups. I am stuck on replicating the underscore reduce function or ._reduce function. Can someone help me understand how it works underneath the hood it has been a few days for me and I am stumped. Here is what I have so far. Please understand I am not utilizing the underscore library, I am trying to replicate it so that I can further my understanding on higher order functions. Thanks.

var reduce = function(collection, iterator, accumulator) {

    var iterator = function(startPoint, combiner){
      for(var i = 0; i <combiner.length; i++){
        startPoint += combiner[i];
    }
    return iterator(accumulator, collection);
}

Upvotes: 7

Views: 1522

Answers (3)

msantos
msantos

Reputation: 791

It's something like it:

function reduce(array, combine, start) {
  for (var i = 0; i < array.length; i++)
    start = combine(start, array[i]);
  return start;
}

console.log(reduce([1, 2, 3, 4], function(a, b) {
  return a + b;
}, 0));

Link Reference: http://eloquentjavascript.net/05_higher_order.html

Upvotes: 1

jds
jds

Reputation: 8259

In the comments of these answers, there has been a lot of confusion between Underscore's reduce and Array.prototype.reduce. Two notes:

  1. Underscore's reduce allows for an empty collection and no seed value. In this case, it will not throw an error but rather returns undefined. naomik has convinced me that this is not safe. For example _([]).reduce(function(a, b) { return a + b}); should either throw an error or return an empty list.
  2. Underscore's reduce works on both objects and arrays.

Now, to my original post:

I actually did the same thing—implement the key functions from Underscore from scratch—a while back, and reduce was probably the trickiest. I think reduce is easier to grok with a non-functional reduce (credit to naomik for this):

function reduce(arr, func, seed) {
    var result = seed,
        len = arr.length,
        i = 0;
    for (; i < len; i++) {
        result = func(result, arr[i])
     }
     return result
 }

Underscore's implementation is a bit more complex, handling objects and arrays, empty collections, and an optional seed value. It also uses each instead of a for loop, since that is more functional in style. This is my implementation of Underscore's reduce:

var reduce = function(coll, func, seed) {
    // `isEmpty` (not shown) handles empty arrays, strings, and objects.
    // Underscore accepts an optional seed value and does not 
    // throw an error if given an empty collection and no seed.
    if (isEmpty(coll)) {
        return coll;
    }
    var noSeed = arguments.length < 3;

    // `each` (not shown) should treat arrays and objects
    // in the same way.
    each(coll, function(item, i) {
        if (noSeed) {
            // This condition passes at most once. If it passes,
            // this means the user did not provide a seed value.
            // Default to the first item in the list.
            noSeed = false;
            seed = item;
        } else {
            seed = func(seed, item, i);
        }
    });

    return seed;
};

Upvotes: -1

Mulan
Mulan

Reputation: 135217

A simple recursive function does the trick

// arr - some array of values
// f   - the reducing function
// acc - initial value for the accumulator
function reduce(arr, f, acc) {
  if (arr.length === 0)
    return acc
  else
    return reduce(arr.slice(1), f, f(acc, arr[0]))
}

// --------------------------------------------------
   
// example 1:
// reduce an array of numbers using an adding function

var ex1 = reduce([1,2,3], function(acc, x) { return acc + x }, 0)

console.log(ex1)
//=> 6

// --------------------------------------------------

// example 2:
// reduce an array of pairs to a mapping object

var ex2 = reduce([['a', 1], ['b', 2], ['c', 3]], function(acc, pair) {
  var key = pair[0]
  var value = pair[1]
  acc[key] = value
  return acc
}, {})

console.log(ex2)
//=> { a: 1, b: 2, c: 3 }

As @torazaburo points out in a comment, if you can use ES6, destructuring assignment cleans up the implementation even more

// ES6
function reduce([x, ...xs], f, acc) {
  if (x === undefined)
    return acc
  else
    return reduce(xs, f, f(acc, x))
}

Or it gets super sugary sweet with arrow functions

// ES6, same as above but using arrow function and ternary expression
const reduce = ([x, ...xs], f, acc)=>
  x === undefined ? acc : reduce(xs, f, f(acc, x))

The Underscore implementation does provide some other conveniences though I'm guessing these are here to maintain compatibility with native Array.prototype.reduce. I personally wouldn't implement reduce this way, but that's beside the point.

  1. Underscore passes an iterator and arr reference to the callback function.
  2. Underscore allows you to change the context for the callback function

Here's a revised implementation which supports these other features

// our reduce version 2.0
function reduce(collection, iterator, memo, context) {
  function loop(memo, i) {
    if (collection.length === i)
      return memo
    else
      return loop(iterator.call(context, memo, collection[i], i, collection), i + 1)
  }
  return loop(memo, 0)
}

You can use it the same as above only now it provides more information to the callback

NOTE

I've purposefully decided not to implement a behaviour of Underscore's reduce that allows you to perform a reduction without an initial value. Supporting this behaviour results in unsafe code and should never have made it into Underscore in the first place.

Upvotes: 5

Related Questions