CODEWITHSUNDEEP
javascriptarraysfunctional-programmingramda.js
uylmz
uylmz

Reputation: 1562

How to merge N array of tuples on a common key by functional programming?

I have 3 arrays, all of them containing tuples. First value is a timestamp (ts), second is an event count occured at that time. Individual arrays are sorted based on timestamp.

var arr1 = [{ts: 1000, val: 1},{ts: 1001, val: 2},{ts: 1002, val: 3}];
var arr2 = [{ts: 1001, val: 4},{ts: 1002, val: 5},{ts: 1005, val: 6}];
var arr3 = [{ts: 1003, val: 8},{ts: 1007, val: 8},{ts: 1008, val: 8}];

I want to merge them into a single timeline, in a 4xN array such that it becomes:

[
    [1000, 1, 0, 0],
    [1001, 2, 4, 0],
    [1002, 3, 5, 0],
    [1003, 0, 0, 8],
    [1005, 0, 6, 0],
    [1007, 0, 0, 8],
    [1008, 0, 0, 8],
]

where 1st column is timestamp, second column is first array value, third column is second array value...

I tried to do it in non-functional ways, but couldn't come up with an elegant-clear solution that doesn't involve looking up timestamps in arrays repeatedly to find corresponding values. I felt there should be a relatively simple way to do this functionally, since I'm basically converting row based data to columnar one.

If solving it for N arrays is problematic I can live with a 3 array solution too!

Upvotes: 0

Views: 687

Answers (2)

Ori Drori
Ori Drori

Reputation: 193037

Flatten the arrays, while adding the original array's index to each item. Then, group by ts, reduce each array of objects to an array of numbers, add the key (original ts) to each array, and convert to an array of array with R.values:

const { addIndex, map, pipe, chain, groupBy, prop, reduce, set, lensIndex, mapObjIndexed, values } = R;

const mapIndexed = addIndex(map);
const fill0 = map(() => 0);

const extract = (...xss) => pipe(
  chain(mapIndexed((o, idx) => ({ ...o, idx }))), // add column index to each object
  groupBy(prop('ts')),
  map(reduce((acc, { idx, val }) => set(lensIndex(idx), val, acc), fill0(xss))), //fill the numbers in the index place
  mapObjIndexed((vals, k) => [k, ...vals]), // create the row array
  values
)(xss)


const arr1 = [{ts: 1000, val: 1}, {ts: 1001, val: 2}, {ts: 1002, val: 3}];
const arr2 = [{ts: 1001, val: 4}, {ts: 1002, val: 5}, {ts: 1005, val: 6}];
const arr3 = [{ts: 1003, val: 8}, {ts: 1007, val: 8}, {ts: 1008, val: 8}];

const result = extract(arr1, arr2, arr3);

console.log(result);
.as-console-wrapper {max-height: 100% !important; top: 0}
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.js" integrity="sha512-3sdB9mAxNh2MIo6YkY05uY1qjkywAlDfCf5u1cSotv6k9CZUSyHVf4BJSpTYgla+YHLaHG8LUpqV7MHctlYzlw==" crossorigin="anonymous"></script>

Using vanilla JS, you can reduce the array of arrays to a Map, iterate the values of each array, if the key doesn't exist in the Map set an array of 0, and update the value at the relevant index. Use Array.from() to convert the entries of the Map to an array of rows:

const extract = (...xss) => Array.from(
   xss.reduce((acc, o, i) => {
    o.forEach(({ ts, val }) => { // iterate each array
      if (!acc.has(ts)) acc.set(ts, [...xss].fill(0)); // if the key (ts) doesn't exist set it as an array of 0s
      
      acc.get(ts)[i] = val; // replace the 0 with a value
    });
    
    return acc;
   }, new Map())
).map(([k, values]) => [k, ...values]); // convert the Map to an array of arrays


const arr1 = [{ts: 1000, val: 1}, {ts: 1001, val: 2}, {ts: 1002, val: 3}];
const arr2 = [{ts: 1001, val: 4}, {ts: 1002, val: 5}, {ts: 1005, val: 6}];
const arr3 = [{ts: 1003, val: 8}, {ts: 1007, val: 8}, {ts: 1008, val: 8}];

console .log (extract (arr1, arr2, arr3))
.as-console-wrapper {max-height: 100% !important; top: 0}

Upvotes: 1

Scott Sauyet
Scott Sauyet

Reputation: 50807

I don't see anything better than your discarded notion of looking up timestamps in the arrays. If the data is really large, then you can make an index of it. But the code would not likely be pretty.

Here's an ES6 version:

const extract = (...xss) => 
  [... new Set (xss .flatMap (xs => xs .map (x => x .ts)))]
    .map (t => [t, ... xss .map (xs => (xs.find(({ts}) => t == ts) || {val: 0}).val)])


const arr1 = [{ts: 1000, val: 1}, {ts: 1001, val: 2}, {ts: 1002, val: 3}];
const arr2 = [{ts: 1001, val: 4}, {ts: 1002, val: 5}, {ts: 1005, val: 6}];
const arr3 = [{ts: 1003, val: 8}, {ts: 1007, val: 8}, {ts: 1008, val: 8}];

console .log (extract (arr1, arr2, arr3))
.as-console-wrapper {max-height: 100% !important; top: 0}

As to Ramda, we could certainly use Ramda here. That first line could be replaced with

  uniq (chain (pluck ('ts')) (xss))

and we could similarly replace the maps and find with Ramda equivalents, and we could use a defaultTo in place of || {val: 0}. If you are using Ramda, you can probably continue that way for a while, and I urge you to try it. But I think if you're looking for an entirely point-free solution, most likely it will quickly end up unreadable.

Upvotes: 2

Related Questions