What is the proper/idiomatic way to filter or map based on surrounding context in functional programming?

Question

In functional programming, filtering based on the characteristics of a single item is relatively straightforward -- e.g., filtering to find only odd numbers:

const arrayOfInfo = [1,2,3,4,5,6,8,10,11,13,15,16,17,19]

const onlyOddNumbers = arrayOfInfo.filter(function(item) {

  return (item % 2 == 1) ? true : false

})

However, I'm not sure what the idiomatic way of doing things is if I need context -- in other words, knowing something about the surrounding items. For example, if I wanted to filter for only the items that were surrounded by odd numbers on either side, I could do this (I'm taking advantage of some JavaScript characteristics and not even bothering to check whether the indexes exist first):

const surroundedByOneOddNumber = arrayOfInfo.filter(function(item,index) {

  const itemBefore = arrayOfInfo[index - 1]
  const itemAfter = arrayOfInfo[index + 1]
  return ((itemBefore % 2 == 1) && (itemAfter % 2 == 1)) ? true : false

})

This becomes more obvious as a problematic or inefficient way to write code if I wanted to find numbers surrounded by two odd numbers on each side:

const surroundedByTwoOddNumbers = arrayOfInfo.filter(function(item,index) {

  const itemBefore = arrayOfInfo[index - 1]
  const itemTwoBefore = arrayOfInfo[index - 2]
  const itemAfter = arrayOfInfo[index + 1]
  const itemTwoAfter = arrayOfInfo[index + 2]
  return ((itemBefore % 2 == 1) && (itemTwoBefore % 2 == 1) && (itemAfter % 2 == 1) && (itemTwoAfter % 2 == 1)) ? true : false

})

Obviously, if I wanted to do something like find only numbers surrounded by 50 odd numbers on each side, this would be completely pointless to write code like this.

Is there a good way to address this with functional programming, or is this a case where it is better to drop down to for/while loop-style?

CodePen to play with the samples: https://codepen.io/jnpdx/pen/MvradM

Answer 1

Here's what I'd do:

const zipperFilter = (p, xs) => {
    const before = [];      // elements before x
    const after  = [...xs]; // x followed by elements after x, shallow copy
    const result = [];

    while (after.length > 0) {
        const x = after.shift(); // remove x; thus, after = elements after x
        if (p(before, x, after)) result.push(x);
        before.unshift(x); // before = x followed by elements before x
    }

    return result;
};

const isOdd = n => n % 2 === 1;

const surroundedByPossiblyNOddNumbers = n => (before, x, after) =>
    before.slice(0, n).every(isOdd) &&
    after.slice(0, n).every(isOdd);

const surroundedByStrictlyNOddNumbers = n => (before, x, after) =>
    before.length >= n &&
    after.length >= n &&
    before.slice(0, n).every(isOdd) &&
    after.slice(0, n).every(isOdd);

const xs = [1,2,3,4,5,6,8,10,11,13,15,16,17,19];

const ys = zipperFilter(surroundedByPossiblyNOddNumbers(1), xs);
const zs = zipperFilter(surroundedByPossiblyNOddNumbers(2), xs);
const as = zipperFilter(surroundedByStrictlyNOddNumbers(1), xs);
const bs = zipperFilter(surroundedByStrictlyNOddNumbers(2), xs);

console.log(JSON.stringify(ys));
console.log(JSON.stringify(zs));
console.log(JSON.stringify(as));
console.log(JSON.stringify(bs));

What is a zipperFilter? It's a context sensitive list filter function based on the zipper data structure for lists. Any time you want to do context sensitive data processing (e.g. image processing) think of zippers.

The advantages of creating a custom zipperFilter function are:

1. It's more efficient than using the native filter method. This is because we don't have to keep using slice to generate the before and after arrays. We keep a running copy of both and update them on every iteration.
2. The before array is maintained in the reverse order. Hence, lower indices always correspond to closer neighbors. This allows us to simply slice the number of closest neighbors we want.
3. It's readable, generic and informs the reader that the filtering is context sensitive.

Hope that helps.

Answer 2

The whole idea of functional programming is to write pure functions without side-effects

Array.filter is functional because it returns a new array, without mutating the original one. You can run that method on the same array millions of times without changing it.

If your logic gets complex, the code gets complex too, there is no functional magic which solves your domain problems.

However, you could make a createFilter function, which would create your filter function based on your domain requirements like:

const createFilter = ({
  before = e => true,
  after = e => true
}) => (entry, idx, entries) => 

before(entries[idx - 1]) && after(entries[idx + 1]) }; }

// This will return [ 4, 4 ] I guess ;)
[1, 3, 3, 3, 2, 4, 5, 2, 4, 7].filter(createFilter({
   before: (e) => e % 2 === 0,
   after: (e) => e % 2 === 1,
}))

The same way you could get only values where the item before is 50 and after 100:

[50, 1, 100, 4, 50, 3, 100].filter(createFilter({
  before: (e) => e === 50,
  after: (e) => e === 100
})) // pretty sure the output is [1, 3] 

So this way you have a reusable filterCreator, extend it to your needs ;)

Update

@Aadit M Shah yes, after reading the OP again, I came to the conclusion, that my method would still work, you just have to write your own filterCreator function. And there is nothing wrong with the Array.filter actually.

const filterBySurrounding = (n, meetCondition) => {
  return (item, idx, array) => {
    return n <= idx && idx + n <= array.length - 1
      ? array.slice(idx - n, idx).every(meetCondition) &&
        array.slice(idx + 1, idx + 1 + n).every(meetCondition)
      : false

  }
}

const isOdd = n => n % 2 === 1
array.filter(filterBySurrounding(50, isOdd))

Answer 3

You could use a closure over the count of the left and right needed odd values, then take the left and right values and check every element and return the result of the check for filtering.

A special case is the count of zero, there you need to check just the actual element.

var array = [1, 2, 3, 4, 5, 6, 8, 10, 11, 13, 15, 16, 17, 19],
    odd = item => item % 2,
    getOdds = count => (a, i, aa) => {
        var temp = aa.slice(i - count, i).concat(aa.slice(i + 1, i + 1 + count));
        return count
            ? temp.length === 2 * count && temp.every(odd)
            : odd(a);
    };

console.log(array.filter(getOdds(0)));
console.log(array.filter(getOdds(1)));
console.log(array.filter(getOdds(2)));

.as-console-wrapper { max-height: 100% !important; top: 0; }

A smarter approach is to count contiguous odd parts and use the array for filtering.

Check if 16 is surrounded by two odd numbers

name   values                                                     comment
-----  ---------------------------------------------------------  --------------------
array  [  1,  2,  3,  4,  5,  6,  8, 10, 11, 13, 15, 16, 17, 19]
left   [  1,  0,  1,  0,  1,  0,  0,  0,  1,  2,  3,  0,  1,  2]
right  [  1,  0,  1,  0,  1,  0,  0,  0,  3,  2,  1,  0,  2,  1]
                                                     16           item to check
                                                  3               left count >= 2
                                                          2       right count >= 2
                                                    true          result for filtering  

var array = [1, 2, 3, 4, 5, 6, 8, 10, 11, 13, 15, 16, 17, 19],
    odd = item => item % 2,
    left = array.reduce((r, a, i) => (r[i] = odd(a) ? (r[i - 1] || 0) + 1 : 0, r), []),
    right = array.reduceRight((r, a, i) => (r[i] = odd(a) ? (r[i + 1] || 0) + 1 : 0, r), []),
    getOdds = count => (a, i) => count
        ? left[i - 1] >= count && right[i + 1] >= count
        : odd(a);

console.log(array.filter(getOdds(0)));
console.log(array.filter(getOdds(1)));
console.log(array.filter(getOdds(2)));

.as-console-wrapper { max-height: 100% !important; top: 0; }