CODEWITHSUNDEEP
javascriptrecursionfunctional-programming
synthet1c
synthet1c

Reputation: 6282

Functional js - cant recursively call own function

I am having trouble with getting an incorrect value from an array flatten function when using functional programming principals to generate the flatten function from a generic reduce function. I believe that this is because there is an issue with the recursion within the call, but am unsure how to move past it as the function signatures for both the working and non working function should be the same.

Thanks for any help.

var data = [['one','two','three'], ['four', 'five', ['six']], 'seven', ['eight', 'nine']];

// here is an example of flatten that works perfectly. it takes an array and reduces 
// the internal arrays to a single flat array
function flatten( arr ){
  return arr.reduce(function( ret, curr ){
    if( Array.isArray( curr ) ){
      ret = ret.concat( flatten( curr ) );
    } else {
      ret.push( curr );
    }
    return ret;
  }, []);
}

// here is what I am trying to achieve. This one combines my reduction functon with the 
// functional `reduceWith` function. The code signature is exactly the same, however the
// end result is different.
// `functionalFlatten` does resolve to the correct function inside
var functionalFlatten = reduceWith(function( ret, curr ){
  if( Array.isArray( curr ) ){
    ret = ret.concat( functionalFlatten( curr ) );
  } else {
    ret.push( curr );
  }
  return ret;
}, []);

// this function will return a functional reduction function 
function reduceWith( fn, initial ) {
  return function _reduceWith( arr ) {
    return Array.prototype.reduce.call(arr, fn, initial || []);
  }
}

console.log('data', data);
console.log('functionalFlatten', functionalFlatten );
console.log('normal', flatten( data ));
console.log('fuctional', functionalFlatten( data ));
<script src="http://codepen.io/synthet1c/pen/WrQapG.js"></script>

Upvotes: 4

Views: 162

Answers (3)

Mulan
Mulan

Reputation: 135257

Here you can write reduceWith as a curried function which gives you better re-use of the overall function.

// ES6
const reduce = f => y => xs => xs.reduce (f, y);

Now we can write flatten as a partially applied reduce function

const flatten = reduce ((y,x) => y.concat (isArray (x) ? flatten (x) : x)) ([]);

That little isArray helper is just

const isArray = Array.isArray;

And it just works. No mutation via .push, no Function.prototype.call. Just folding and concat'ing.

console.log (flatten ([1,2,[3,4,[],6,[7,8,9]]]));
//=> [1,2,3,4,5,6,7,8,9]

Here's the ES5

// ES5
"use strict";

var reduce = function reduce(f) {
  return function (y) {
    return function (xs) {
      return xs.reduce(f, y);
    };
  };
};

var isArray = Array.isArray;

var flatten = reduce(function (y, x) {
  return y.concat(isArray(x) ? flatten(x) : x);
})([]);

console.log(flatten([1, 2, [3, 4, [], 6, [7, 8, 9]]]));
//=> [1,2,3,4,5,6,7,8,9]

Upvotes: 1

demux
demux

Reputation: 4654

I made a few changes to your code. This works:

var data = [
  ['one','two','three'],
  ['four', 'five', ['six']],
  'seven',
  ['eight', 'nine']
]

function flatten(arr) {
  return arr.reduce(function(ret, curr) {
    return ret.concat(Array.isArray(curr) ? flatten(curr) : [curr])
  }, [])
}

var functionalFlatten = reduceWith(function(ret, curr) {
  return Array.prototype.concat.call(ret, Array.isArray(curr) ? functionalFlatten(curr) : [curr])
}, [])

// I assume you want to use .call to keep it functional or what ever
// But I would just do it like this:
var _functionalFlatten = reduceWith(function(ret, curr) {
  return ret.concat(ret, Array.isArray(curr) ? functionalFlatten(curr) : [curr])
}, [])

function reduceWith(fn, initial) {
  return (function (arr) {
    return Array.prototype.reduce.call(arr, fn, initial) 
  })
}

// Again, keep it simple...
function _reduceWith(fn, initial) {
  return (function (arr) {
    return arr.reduce(fn, initial)
  })
}

// You had this...
function reduceWith( fn, initial ) {
  // You don't need to name this function:
  return function _reduceWith( arr ) {
    // Let's keep this in line original function, so remove the default:
    return Array.prototype.reduce.call(arr, fn, initial || []);
  }
}

console.log('data', data)
console.log('functionalFlatten', functionalFlatten)
console.log('normal', flatten(data))
console.log('fuctional', functionalFlatten(data))

Now to the actual problem...

var functionalFlatten = reduceWith(function( ret, curr ){
  if( Array.isArray( curr ) ){
    ret = ret.concat( functionalFlatten( curr ) );
  } else {
    // This is your culprit:
    ret.push( curr ); // push will mutate ret
  }
  return ret;
}, []);
  • reduceWith only gets called once (when functionalFlatten is defined).
  • The inner function will get called every time
  • ... but ret.push(curr) has the potential to mutate initial

Here is proof...

function reduceWithMutationSafe(fn, initial) {
  return (function (arr) {
    // Clone initial, so that the original can't be mutated:
    var clonedInitial = eval(JSON.stringify(initial))
    return arr.reduce(fn, clonedInitial)
  })
}

var functionalFlatten = reduceWithMutationSafe(function(ret, curr) {
  if(Array.isArray(curr)) {
    ret = ret.concat(functionalFlatten(curr))
  } else {
    ret.push(curr)
  }
  return ret
}, [])

This will work, even though functionalFlatten is exactly the same as before
ret.push(curr) will mutate the cloned initial, but the original one won't be touched.

But this last piece of code is just proof. There should be no need to use reduceWithMutationSafe.

Upvotes: 2

user2844991
user2844991

Reputation:

Here's how I fixed your function

var functionalFlatten = reduceWith(function f( ret, curr ){
  if( Array.isArray( curr ) ){
    ret = ret.concat( reduceWith(f, [])( curr ) );
  } else {
    ret.push( curr );
  }
  return ret;
}, []);

The problem with your initial code was the use of the same initial value for both the parent call and the recursive one which made ret to concatenate with itself.

Upvotes: 3

Related Questions