Clarification on reduce to create filter in javascript

Question

My main goal for academic purposes is to solve this problem and for the most part I did. Also I wanted to make sure that I was not missing a fundamental part of reduce by not understanding what is wrong with my code.

This is how I would solve it, I've attached my reduce function as well as filter function. I believe my reduce function works however, my filter function isn't quite working so well as I can't pass my test cases.

1) Why am i not hitting the last element of the array?

I've noticed that prev and curr actually never return 5 at any point of the reduce function. Am I missing something in my reduce function?

myArray = [1,2,3,4,5];

function each(collection, action){
	if(Array.isArray(collection)){
		for(var i = 0; i < collection.length; i ++){
			action(collection[i]);
		}
	}
	else if(typeof(collection) === "object"){
		for (var property in collection){
			action(collection[property]);
		}
	}
}

function reduce(collection, combine, start){
	each(collection, function(element){
		if(start === undefined){
			return start = element;
		}
		else {
			return start = combine(start, element);
		}
	});
	return start;
}


function filterR(collection, predicate){
	var aR = [];
	reduce(collection, function(prev, curr){
		if(predicate(prev)){
			aR.push(prev);
		}
		if(predicate(curr)){
			aR.push(curr);
		}
		
	});
	return aR;
}


console.log(filter(myArray, function(val){return val % 5 === 0;})); //expected [5]
console.log(filter(myArray, function(val){return val <= 5;})); //expected [1,2,3,4,5]

are you going to share your each function

Mulan
– Mulan

2016-05-07 00:11:15 +00:00
Commented May 7, 2016 at 0:11 — Mulan
– Mulan, Commented May 7, 2016 at 0:11
@naomik Thanks for pointing that out!

DanielSD
– DanielSD

2016-05-07 03:13:06 +00:00
Commented May 7, 2016 at 3:13 — DanielSD
– DanielSD, Commented May 7, 2016 at 3:13

Community · Accepted Answer · 2020-06-20 09:12:55Z

I can't diagnose your problem because I don't know what your each procedure is.

Anyway, it doesn't matter; you're overthinking it.

reduce is very simple to implement by hand.

function reduce(f, start, arr) {
  if (arr.length === 0)
    return start;
  else
    return reduce(f, f(start, arr[0]), arr.slice(1));
}

// example
function add(x,y) { return x+y; }
reduce(add, 0, []);      //=> 0
reduce(add, 0, [1,2,3]); //=> 6

I see that you are trying to support a sort of reduce without an optional starting value. That is impossible if your reduce function is to be considered a total function. A starting value is required. Don't try to be clever.

Now a filter implemented using reduce

function filter(f, arr) {
  return reduce(function(result, x) {
    if (f(x))
      return result.concat([x]);
    else
      return result;
  }, [], arr);
}

Your examples

var myArray = [1,2,3,4,5];

filter(function(val){return val % 5 === 0;}, myArray)
//=> [5]

filter(function(val){return val <= 5;}, myArray)
//=> [1, 2, 3, 4, 5]

If you want to learn more...

There are other ways to implement reduce as well. One such improvement you could make is to put the recursion in tail position. When JavaScript engines support tail call elimination (with ES6), this would prevent reduce from stack-overflowing for significantly large values of arr.

function reduce(f, start, arr) {
  function loop(result, arr) {
    if (arr.length === 0)
      return result;
    else
      return loop(f(result, arr[0]), arr.slice(1));
  }
  return loop(start, arr);
}

A blackhole appears...

With reduce and higher-order functions under your belt, you now stand at the shores of the deep, vast sea that is lambda calculus and functional programming. If you're feeling very zealous, you can explore how currying and combinators change this definition even more dramatically.

The following code is written in ES6

// U-combinator
const U = f=> f(f);

// Y-combinator
const Y = U (h=> f=> f (x=> h (h) (f) (x)));

// reduce
const reduce = f=> Y(h=> start=> arr=>
  arr.length === 0
    ? start
    : h (f (start) (arr[0])) (arr.slice(1)));


// filter
const filter = f=>
  reduce(result=> x=>
    f(x) ? result.concat([x]) : result) ([]);

// your examples again...
var myArray = [1,2,3,4,5];
filter (x=> x % 5 === 0) (myArray) //=> [5]
filter (x=> x <= 5) (myArray)      //=> [1, 2, 3, 4, 5]

Thomas · Accepted Answer · 2016-05-07 00:12:15Z

Why am i not hitting the last element of the array?

I don't know. It might be an error in your each-function, wich is not posted here. But since you have some more flaws in boh of your functions, I'll add a working implementation.

I've noticed that prev and curr actually never return 5 at any point of the reduce function.

prev and curr never return anything, they are arguments. And that particular function itself, also doesn't ever return anything.

First start === undefined is no proper check to determine wether yo want to initialize the result-value with the first(current)-element. undefined is an unexpected, even unwanted value in that place, but it is actually perfectly fine. So with that check, your reduce-function might start over again, in the middle of the collection.

Just take a look at the previously mentioned function you utilize in filter. This function does return undefined (as the value for the next iteration) ;) so that prev will always be undefined in your code.

Then, reduce makes no sense in your filter-function, at least the way you use it. You use it as each.

function reduce(collection, combine, start){
    var result = start, hasValue = arguments.length > 2;

    each(collection, function(element){
        if(hasValue){
            result = combine(result, element);
        }else{
            result = element;
            hasValue = true;
        }
    });

    if(!hasValue){
        //no start/default-value, no elements in the collection,
        //what result do you expect from this reduce-task?
        throw new Error("reduce of empty array with no initial value");     
    }
    return result;
}

function filter(collection, predicate){
    return reduce(collection, function(result, elm){
        //the functional-approach: no mutations
        return predicate(elm)?
            result.concat( [elm] ):
            result;

        //or a more sane way to do this in JS
        if( predicate(elm) ) result.push( elm );
        return result;
    }, []);
}

Collectives™ on Stack Overflow

Clarification on reduce to create filter in javascript

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related