Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

filter and map in same iteration

I have this simple situation where I want to filter and map to the same value, like so:

 const files = results.filter(function(r){
      return r.file;
    })
    .map(function(r){
       return r.file;
    });

To save lines of code, as well as increase performance, I am looking for:

const files = results.filterAndMap(function(r){
  return r.file;
});

does this exist, or should I write something myself? I have wanted such functionality in a few places, just never bothered to look into it before.

like image 732
Alexander Mills Avatar asked Jul 18 '17 05:07

Alexander Mills


People also ask

Can we use filter and map together?

You can combine filter() and map() to clean an array of unwanted values before transforming the leftover items.

Can you explain the filter () map () and reduce () functions?

The functions map(), filter(), and reduce() all do the same thing: They each take a function and a list of elements, and then return the result of applying the function to each element in the list. As previously stated, Python has built-in functions like map(), filter(), and reduce().

Can we use map to filter in JavaScript?

Map, reduce, and filter are all array methods in JavaScript. Each one will iterate over an array and perform a transformation or computation. Each will return a new array based on the result of the function.


1 Answers

Transducers

In its most generic form, the answer to your question lies in transducers. But before we go too abstract, let's see some basics first – below, we implement a couple transducers mapReduce, filterReduce, and tapReduce; you can add any others that you need.

const mapReduce = map => reduce =>
  (acc, x) => reduce (acc, map (x))
  
const filterReduce = filter => reduce =>
  (acc, x) => filter (x) ? reduce (acc, x) : acc
  
const tapReduce = tap => reduce =>
  (acc, x) => (tap (x), reduce (acc, x))

const tcomp = (f,g) =>
  k => f (g (k))

const concat = (xs,ys) =>
  xs.concat(ys)
  
const transduce = (...ts) => xs =>
  xs.reduce (ts.reduce (tcomp, k => k) (concat), [])

const main =
  transduce (
    tapReduce (x => console.log('with:', x)),
    filterReduce (x => x.file),
    tapReduce (x => console.log('has file:', x.file)),
    mapReduce (x => x.file),
    tapReduce (x => console.log('final:', x)))
      
const data =
  [{file: 1}, {file: undefined}, {}, {file: 2}]
  
console.log (main (data))
// with: { file: 1 }
// has file: 1
// final: 1
// with: { file: undefined }
// with: {}
// with: { file: 2 }
// has file: 2
// final: 2
// => [ 1, 2 ]

Chainable API

Maybe you're satisfied with the simplicity of the code but you're unhappy with the somewhat unconventional API. If you want to preserve the ability to chain .map, .filter, .whatever calls without adding undue iterations, we can make a generic interface for transducing and make our chainable API on top of that – this answer is adapted from the link I shared above and other answers I have about transducers

// Trans Monoid
const Trans = f => ({
  runTrans: f,
  concat: ({runTrans: g}) =>
    Trans (k => f (g (k)))
})

Trans.empty = () =>
  Trans(k => k)

// transducer "primitives"
const mapper = f =>
  Trans (k => (acc, x) => k (acc, f (x)))
  
const filterer = f =>
  Trans (k => (acc, x) => f (x) ? k (acc, x) : acc)
  
const tapper = f =>
  Trans (k => (acc, x) => (f (x), k (acc, x)))
  
// chainable API
const Transduce = (t = Trans.empty()) => ({
  map: f =>
    Transduce (t.concat (mapper (f))),
  filter: f =>
    Transduce (t.concat (filterer (f))),
  tap: f =>
    Transduce (t.concat (tapper (f))),
  run: xs =>
    xs.reduce (t.runTrans ((xs,ys) => xs.concat(ys)), [])
})

// demo
const main = data =>
  Transduce()
    .tap (x => console.log('with:', x))
    .filter (x => x.file)
    .tap (x => console.log('has file:', x.file))
    .map (x => x.file)
    .tap (x => console.log('final:', x))
    .run (data)
    
const data =
  [{file: 1}, {file: undefined}, {}, {file: 2}]

console.log (main (data))
// with: { file: 1 }
// has file: 1
// final: 1
// with: { file: undefined }
// with: {}
// with: { file: 2 }
// has file: 2
// final: 2
// => [ 1, 2 ]

Chainable API, take 2

As an exercise to implement the chaining API with as little dependency ceremony as possible, I rewrote the code snippet without relying upon the Trans monoid implementation or the primitive transducers mapper, filterer, etc – thanks for the comment @ftor.

This is a definite downgrade in terms of overall readability. We lost that ability to just look at it and understand what was happening. We also lost the monoid interface which made it easy for us to reason about our transducers in other expressions. A big gain here tho is the definition of Transduce is contained within 10 lines of source code; compared to 28 before – so while the expressions are more complex, you can probably finish reading the entire definition before your brain starts struggling

// chainable API only (no external dependencies)
const Transduce = (t = k => k) => ({
  map: f =>
    Transduce (k => t ((acc, x) => k (acc, f (x)))),
  filter: f =>
    Transduce (k => t ((acc, x) => f (x) ? k (acc, x) : acc)),
  tap: f =>
    Transduce (k => t ((acc, x) => (f (x), k (acc, x)))),
  run: xs =>
    xs.reduce (t ((xs,ys) => xs.concat(ys)), [])
})

// demo (this stays the same)
const main = data =>
  Transduce()
    .tap (x => console.log('with:', x))
    .filter (x => x.file)
    .tap (x => console.log('has file:', x.file))
    .map (x => x.file)
    .tap (x => console.log('final:', x))
    .run (data)
    
const data =
  [{file: 1}, {file: undefined}, {}, {file: 2}]

console.log (main (data))
// with: { file: 1 }
// has file: 1
// final: 1
// with: { file: undefined }
// with: {}
// with: { file: 2 }
// has file: 2
// final: 2
// => [ 1, 2 ]

> Talks about performance

When it comes to speed, no functional variant of this is ever going to beat a static for loop which combines all of your program statements in a single loop body. However, the transducers above do have the potential to be faster than a series of .map/.filter/.whatever calls where multiple iterations thru a large data set would be expensive.

Coding style & implementation

The very essence of the transducer lies in mapReduce, which is why I chose to introduce it first. If you can understand how to take multiple mapReduce calls and sequence them together, you'll understand transducers.

Of course you can implement transducers in any number of ways, but I found Brian's approach the most useful as it encodes transducers as a monoid – having a monoid allows us make all sorts of convenient assumptions about it. And once we transduce an Array (one type of monoid), you might wonder how you can transduce any other monoid... in such a case, get reading that article!

like image 66
Mulan Avatar answered Oct 13 '22 01:10

Mulan