Forem: Marwan El Boussarghini

Exercise - Array.prototype methods with reduce

Marwan El Boussarghini — Tue, 05 Nov 2019 10:02:37 +0000

For those who read my previous articles, you might know my fascination for the Array.prototype method reduce (Click here to find out more about this function).

Talking with a colleague of mine, we actually realised that it was so flexible we could probably implement all the other Array.prototype methods using it instead. Let's try that together in this article!

Quick overview of what we will do:

Only write pure functions. It is a "must do" if you interested in declarative and functional programming and I find reduce() really helpful when you go on that route.
Re-implement all the accessor and iteration methods. Not that I'm not interested in mutations but I don't use them on regular basis (see 1.).
Only use one reduce.

But first, I would really advise you to DO IT YOURSELF. You don't really have to write them all down but I found this exercise really interesting for few reasons.

It is a great way to learn reduce() if you're not too familiar with it.
I found myself rediscovering some Array.prototype methods like some that I haven't used for ages and could be really interesting to use in my day to day code.

Accessor methods

Array.prototype.length

Link

The length property of an object which is an instance of type Array sets or returns the number of elements in that array. The value is an unsigned, 32-bit integer that is always numerically greater than the highest index in the array.

Yes, I know Array.prototype.length is a property. I still find this property quite magic since - unlike most other properties you would find - it automatically mutates based on the length of your array and therefore could belong to this analysis.

const length = arr => () => arr.reduce((acc) => acc + 1, 0);

Array.prototype.concat()

Link

The concat() method is used to merge two or more arrays. This method does not change the existing arrays, but instead returns a new array.

const concat = arr1 => arr2 => arr2.reduce((acc, el) => [...acc, el], arr1);

Array.prototype.includes()

Link

The includes() method determines whether an array includes a certain value among its entries, returning true or false as appropriate.

const includes = arr => element => arr.reduce((acc, el) => acc || (el === element), false);

Array.prototype.indexOf()

Link

The indexOf() method returns the first index at which a given element can be found in the array, or -1 if it is not present.

const indexOf = arr => element => arr.reduce((acc, el, index) => (
  (acc === -1 && el === element) ? index : -1),
  -1,
);

Array.prototype.join()

Link

The join() method creates and returns a new string by concatenating all of the elements in an array (or an array-like object), separated by commas or a specified separator string. If the array has only one item, then that item will be returned without using the separator.

const join = arr => (separator = '') => arr.reduce((acc, el) => `${acc}${separator}${el}`);

Array.prototype.lastIndexOf()

Link

The lastIndexOf() method returns the last index at which a given element can be found in the array, or -1 if it is not present. The array is searched backwards, starting at fromIndex.

const lastIndexOf = arr => element => arr.reduce((acc, el, index) => (el === element ? index : -1), -1);

Array.prototype.slice()

Link

The slice() method returns a shallow copy of a portion of an array into a new array object selected from begin to end (end not included) where begin and end represent the index of items in that array. The original array will not be modified.

const isBetween = i => (begin, end) => i >= begin && i < end;
const slice = arr => (begin, end) => arr.reduce((acc, el, index) => isBetween(index)(begin, end) ? [...acc, el] : acc, []);

Array.prototype.toString()

Link

The toString() method returns a string representing the specified array and its elements.

const toString = arr => () => arr.reduce((acc, el) => `${acc},${el}`);

Array.prototype.toLocaleString()

Link

The toLocaleString() method returns a string representing the elements of the array. The elements are converted to Strings using their toLocaleString methods and these Strings are separated by a locale-specific String (such as a comma “,”).

const toLocaleString = arr => () => arr.reduce((acc, el, index) => `${acc}${index === 0 ? '' : ','}${el.toLocaleString()}`, '');

Iteration methods

Array.prototype.entries()

Link

The entries() method returns a new Array Iterator object that contains the key/value pairs for each index in the array.

const entries = arr => () => arr.reduce((acc, el, index) => [...acc, [index, el]], []);

Array.prototype.every()

Link

The every() method tests whether all elements in the array pass the test implemented by the provided function. It returns a Boolean value.

Note: This method returns true for any condition put on an empty array.

const every = arr => predicate => arr.reduce((acc, ...rest) => acc && predicate(...rest), true);

Array.prototype.filter()

Definition: The filter() method creates a new array with all elements that pass the test implemented by the provided function.

const every = arr => predicate => arr.reduce((acc, el, ...rest) => (predicate(el, ...rest) ? [...acc, el] : acc), []);

Array.prototype.find()

Definition: The find() method returns the value of the first element in the provided array that satisfies the provided testing function.

This one is quite tricky: my first reaction was to write down this code.

const find = arr => predicate => arr.reduce(
  (acc, el, index, array) => (acc === undefined && predicate(el, index, array)) ? el : undefined,
  undefined,
);

Then I realised an edge case that would actually make this function behave differently from the original find method. Here is the edge case:

console.log([undefined, null].find(el => !el)); // Returns: undefined
console.log(find([undefined, null])(el => !el)) // Returns: null

How to solve this edge case? Well looks like our only source of truth will be the index of the found element. Let's try that one instead:

const find = arr => predicate => arr.reduce(
  (acc, el, index, array) => (acc[1] === -1 && predicate(el, index, array)) ? [el, index] : acc,
  [undefined, -1],
)[0];

This way we are sure that the first element that is found will be returned by our function.

Array.prototype.findIndex()

Definition: The findIndex() method returns the index of the first element in the array that satisfies the provided testing function. Otherwise, it returns -1, indicating that no element passed the test.

This one should be quite straight forward considering the code written above

const findIndex = arr => predicate => arr.reduce(
  (acc, el, index, array) => (acc[1] === -1 && predicate(el, index, array)) ? [el, index] : acc,
  [undefined, -1],
)[1];

Array.prototype.forEach()

Definition: The forEach() method executes a provided function once for each array element.

const forEach = arr => callback => arr.reduce(
  (_, ...rest) => { callback(...rest); },
  [],
);

Array.prototype.keys()

Definition: The keys() method returns a new Array Iterator object that contains the keys for each index in the array.

const keys = arr => () => arr.reduce((acc, _, index) => [...acc, index], []);

Array.prototype.map()

Definition: The map() method creates a new array with the results of calling a provided function on every element in the calling array.

const map = arr => callback => arr.reduce((acc, ...rest) => [...acc, callback(...rest)], []);

Array.prototype.some()

Definition: The some() method tests whether at least one element in the array passes the test implemented by the provided function. It returns a Boolean value.

Note: This method returns false for any condition put on an empty array.

const some = arr => predicate => arr.reduce((acc, ...rest) => acc || predicate(el, ...rest), false);

Array.prototype.values()

Definition: The values() method returns a new Array Iterator object that contains the values for each index in the array.

const values = arr => () => arr.reduce((acc, el) => [...acc, el], []);

Array.prototype.reduceRight()

Definition: The reduceRight() method applies a function against an accumulator and each value of the array (from right-to-left) to reduce it to a single value.

For this one, my first idea was obviously to reverse the array and then apply a reduce(). Lol funny but not optimal as we are iterating twice on the array 🙃.

const reduceRight = arr => (...params) => arr.reduce((acc, el) => [el, ...acc]).reduce(...params);

After searching for ages, I must say I'm quite disappointed on this one... I have not been able to find a short and clean way to implement reduceRight() with only one reduce()... It is extremely frustrating and I would love to hear someone who has a suggestion regarding it!

Conclusion

Among a lot of trivial methods to implement, several one have been interesting to implement:

find(): this edge-case actually made the implementation a bit stiffer than I thought. It really pushed me to have a critical eye on when it comes to the predicates I'm using.
reduceRight(): this is actually my biggest frustration. I would be really interested to know if one of you can solve it and how to!

Tip - Chain Promises synchronously

Marwan El Boussarghini — Wed, 30 Oct 2019 09:50:01 +0000

On one my company's project, we faced a non-trivial issue that I find could be really interesting to solve together. This article will basically give you an overview of the problem and how I solved it using the Array.prototype method reduce.

Here is a quick overview of the context around my issue.

I needed for one of my projects to create a state machine that would asynchronously process a string character by character.

const initialState = { /* Initial state of the state machine */ };

// processCharacter :: (State) -> (character) -> Promise(State)
const processCharacter = (state) => async (character) => {
  // ...asynchronously process the character
  return newState;
};

// (State) -> Promise(Result)
const getResultFromState = (state) => {
  // ...converts the state to a result
  return result;
}

// Function to implement.
// :: string -> Promise(Result)
const processString = async (string) => {
  // ?
  return result
}

In a nutshell, here are the different step given an initialState:

Split the string into an array of characters.
For each character, call await processCharacter(character)(state) and assign it to state.
Call getResultFromState to the last version of the state.

TL;DR Go straight to the solution by clicking here.

Practical example

To illustrate this problem, let's define a practical example:

// Simulates different processing time based on character.
const calculateTimeout = character => character.charCodeAt(0) * 10;
// Allows to set to use setTimeout with await.
const timeout= async (ms) => new Promise(rs => setTimeout(rs, ms));
// :: string -> [character]
const stringToArray = string => [...string];

const initialState = { stringProcessed: '' };

const processCharacter = ({ stringProcessed }) => async (character) => {
  const ms = calculateTimeout(character);
  await timeout(ms);
  return { stringProcessed: `${stringProcessed}${character}`};
};

const getResultFromState = ({ stringProcessed }) => {
  return stringProcessed;
}

const processString = async (string) => {
  // ?
  return result
}

Solution

Let me show you two approaches to the problem: one purely imperative - which does makes sense but lacks of elegance - and a far more concise solution.

First approach: imperative way

With an imperative approach, we want to describe each step of the function as it is describe in problem.

const processString = async (string) => {
  let state = initialState;
  const stringArray = stringToArray(string);
  for (let i = 0; i < stringArray.length; i++) {
    state = await processCharacter(state)(stringArray[i]);
  }
  return getResultFromState(result);
}

To be fair, this works and it will return you exactly what you're looking for.
I still have several issues with this code:

I like the functional programming approach and re-assigning state at each step kills me a bit more every time,
the old fashioned for loop is extremely verbose and I don't think I've used it since I learned how to use map and forEach.

"But Marwan, why can't we use a forEach ?" you may ask.

Let's try (and forget my first point, nvm).

const processString = async (string) => {
  let state = initialState;
  stringToArray(string).forEach(async (character) => {
    state = await processCharacter(state)(stringArray[i]);
  });
  return getResultFromState(result);
}

Brilliant! But if you run this in a gist for the string "Test", you receive ... "". Wait what?

Indeed... This will not work because of the definition of forEach: you could basically reimplement it as below.

Array.prototype.forEach = function(fn) {
  for(let i = 0; i < this.length; i++) {
    fn(i);
  }
}

Do you see where the issue comes from?
Yes! From the await!
In fact this particular point differentiate forEach() and our good old for loop.
If you wanted to make that work, you would probably want to start the code by this:

Array.prototype.forEach = function(fn) {
  for(let i = 0; i < this.length; i++) {
    await fn(i);
  }
}

But please don't that...

Instead let run you through a more elegant solution.

Using reduce()

For those who have read some articles on my blog, you might know about my fascination for the reduce() function and how powerful it can be. Here is one the example of why I think so.

Think of the problem like this: what we want to do can be also written as below (let's take the string "monster").

processCharacter(initialState)('m')
  .then(state => processCharacter('o')(state))
  .then(state => processCharacter('n')(state))
  .then(state => processCharacter('s')(state))
  .then(state => processCharacter('t')(state))
  .then(state => processCharacter('e')(state))
  .then(state => processCharacter('r')(state));

This way to iterate a pattern over a number of element usually pushes me toward reduce().

Let's define our reducer: we basically want our accumulator and for each character to apply processCharacter.

const reducer = (accumulator, character) => accumulator.then(state => processCharacter(character)(state));

As our initial value, we still want to have a Promise to be able to apply .then to it. Here it is: Promise.resolve(initialState) that is basically a promise that will resolve our initial state and start to make our dominoes fall.

Final solution

// :: string -> [character]
const stringToArray = string => [...string];
const processString = async (string) => getResultFromState(
  stringToArray(string).reduce(
    (acc, character) => acc.then((state) => processCharacter(state)(character)),
    Promise.all(initialState),
  )
);

I hope you enjoyed reading this article!

I really wanted to highlight the way I think about a problem and try to solve it and to give you a glance of the beauty of declarative programming (that I will probably cover in a future article).

Toolkit - map / filter / reduce in arrays

Marwan El Boussarghini — Tue, 22 Oct 2019 11:38:15 +0000

In the last year, I have been extremely interested in functional and declarative programming.
In fact after practising and learning how to write functional JavaScript, I find this code extremely smooth to read, very compact and easy to change (probably a nice subject for a future article).

On my journey, I have found myself chaining a lot of functions as in the below example and I thought it would be interesting to summarize the three main methods that I use with arrays.

randomElement
  .method1(callBack1) // do this
  .method2(callBack2) // then do that
  .method3(callBack3) // ...

"Why arrays?" you might ask. Well I think that's probably the data structure that I find myself manipulating the most with objects (and when I need to iterate on objects, I tend to use Object.keys() or Object.entries() that will basically convert my object to an array).

An other thing that I find extremely really important with those three methods is that they are pure (as long as the callback you give them is pure) which means that they:

have no side-effects on your code;
won't modify the initial array and create a brand new array (or value).

Map

The map() method creates a new array with the results of calling a provided function on every element in the calling array.

In a nutshell, map accepts as an argument a function that will transform each element of the array. It takes 2 arguments as below:

arr.map(
  (element, index, array) => // element of the array,
  thisArgument, // In case you use "this" inside the function above. I totally DISSUADE you from using it.
);

map has a lot of use when it comes to formatting elements of an array and it's probably one of function that I use the most on a daily basis. Here are below few examples of map usage.

// Format an object.

const users = [
  { id: 1, firstName: "Charles", lastName: "Winston" },
  { id: 2, firstName: "Brad", lastName: "Dai" },
  { id: 4, firstName: "John", lastName: "Doe" },
];

const getId = ({ id }) => id;
users.map(getId); // [1, 2, 4]

const formatNames = ({ firstName, lastName, ...rest }) => ({
  ...rest,
  fullName: `${firstName} ${lastName}`,
});
users.map(formatNames);
/*
[
  { id: 1, fullName: "Charles Winston" },
  { id: 2, fullName: "Brad Dai" },
  { id: 4, fullName: "John Doe" },
]
*/

// Iterate to generate different element like with JSX and React.

const users = [
  { id: 1, firstName: "Charles", lastName: "Winston", companyId: 1 },
  { id: 2, firstName: "Brad", lastName: "Dai", companyId: 12 },
  { id: 4, firstName: "John", lastName: "Doe", companyId: 19 },
];

const renderUser = (
  { id, firstName, lastName },
  index
) => (
  <li key={id}>{index} - {firstName} {lastName}</li>
);
const UserList = <ul>{users.map(renderUser)}</ul>;
/*
<ul>
  <li key={1}>1 - Charles Winston</li>
  <li key={2}>2 - Brad Dai</li>
  <li key={4}>3 - John Doe</li>
</ul>
*/

// To add information to an object.

const companies = [{ id: 1, name: "Apple" }, { id: 19, name: "Google" }]
const addCompanyToUser = ({ companyId, ...rest }) => ({
  ...rest,
  company: companies.find(({ id }) => companyId === id) || null,
});

users.map(addCompanyToUser)
/*
[{
  id: 1, firstName: 'Charles', lastName: 'Winston', company: { id: 1, name: 'Apple' },
},{
  id: 2, firstName: 'Brad', lastName: 'Dai', company: null,
}, {
  id: 4, firstName: 'John', lastName: 'Doe', company: { id: 19, name: 'Google' },
}]
 */

Filter

The filter() method creates a new array with all elements that pass the test implemented by the provided function.

filter() is a simpler function: it allows to create a new sub-array based on a predicate (function that returns a boolean) and filter (wow) your array.

const messages = [
  { id: 1, message: 'Hello Johnny', recipientId: 3 },
  { id: 2, message: 'Hey Nick!', recipientId: 80 },
  { id: 3, message: 'How are you doing?', recipientId: 3 },
  { id: 4, message: 'See you around sis!', recipientId: 99 },
];

const isMessageForUser = id => ({ recipientId }) => id === recipientId;

messages.filter(isMessageForUser(3));
/*
[
  { id: 1, message: 'Hello Johnny', recipientId: 3 },
  { id: 3, message: 'How are you doing?', recipientId: 3 },
]
*/

const messages = [
  { id: 1, message: 'Hello Johnny', recipientId: 3 },
  { id: 2, message: 'Hey Nick!', recipientId: 80 },
  { id: 3, message: 'How are you doing?', recipientId: 3 },
  { id: 4, message: 'See you around sis!', recipientId: 99 },
  { id: 5, message: 'See you around bro!', recipientId: 80 },
];

const isMessageInPage = (pageSize, offset) => (_, index) =>
  (offset * pageSize <= index) && (index < (offset + 1) * pageSize);

messages.filter(isMessageInPage(2, 1));
/*
[
  { id: 3, message: 'How are you doing?', recipientId: 3 },
  { id: 4, message: 'See you around sis!', recipientId: 99 },
]
*/

Real world example with Map and Filter

What I find really interesting in this functions is the way you can chain them. It makes the code really easy to debug, to read and to make evolve.

Here is for example a sample of code to parse logs coming for example from a CloudWatch instance:

const logExample = '{"messageType":"DATA_MESSAGE","owner":"123456789123","logGroup":"testLogGroup","logStream":"testLogStream","subscriptionFilters":["testFilter"],"logEvents":[{"id":"id1","timestamp":1440442987000,"message":"[INFO] First test message", origin: "application", "level": "INFO" },{"id":"id2","timestamp":1440442987001,"message":"[ERROR] Second test message", "origin": "nginx", "level": "ERROR" },{"id":"id3","timestamp":1440442987000,"message":"[INFO] Third test message", "origin": "application", "level": "INFO" }]}';

const getLogEvents = logStream => {
  try { return JSON.parse(logStream).logEvents; }
  catch(e) { return []; }
};
/*
Expected output:
[
  { id:"id1", timestamp:1440442987000, message:"[INFO] First test message", origin: "nginx", level: "INFO" },
  { id:"id2", timestamp:1440442987001, message:"[ERROR] Second test message", origin: "application", level: "ERROR" },
  { id:"id3", timestamp:1440442987000, message:"[WARN] Third test message", origin: "application", level: "WARNING" },
]
*/

const isOriginExcluded = excludedOrigins => ({ origin }) => !excludedOrigins.includes(origin);
const isLevelInList = levelList => ({ level }) => levelList.includes(level);
const formatLog = ({ message }) => message;

const errorMessages = getLogEvents(logExample)
  .filter(isOriginExcluded(['nginx', 'syslog'])) // Exclude system logs.
  .filter(isLevelInList(['ERROR'])) // Only keep error logs
  .map(formatLog); // Extract the messages.
// Output: ["[ERROR] Second test message"]

With this kind of code, I find extremely clear how the logs are processed and the shape of the different outputs.
This is particularly helpful when someone else comes and want to make some modifications.

Reduce: sometimes simple is not enough

The reduce() method executes a reducer function (that you provide) on each element of the array, resulting in a single output value.

Here comes the final boss of the array methods. Before digging in why this function is so powerful, let's have a look at its parameters.

arr.reduce(
  (accumulator, currentValue, index, initialValue) => { /* should return the new value of the accumulator */ }, // reducer that will be applied to each element.
  initialValue, // First value of the accumulator (by default the first value of the array).
);

The best way I found to understand what it does is actually to write it down in a imperative way:

const arr;
const reducer;
const initialValue;

const result = arr.reduce(reducer, initialValue);

// Is basically equivalent to the code below.

if (initialValue === undefined && !arr.length) { throw new TypeError(); }
let result = initialValue || arr[0];

arr.forEach((element, index) => {
  result = reducer(result, element, index, arr);
});

This method enables among other things to combine elements of a list...

// Sum all the element of a list.
[1,2,3,4].reduce((acc, el) => acc + el) // 10

// Or something more complex like gathering purchases in a list of objects.
const purchases = [
  { id: 1, userId: 53, apples: 1 },
  { id: 2, userId: 90, apples: 3 },
  { id: 3, userId: 53, apples: 5 },
  { id: 4, userId: 90, apples: 2 },
];

const replaceElementAtIndex = arr => (el, index) => [
  ...arr.slice(0, index), el, ...arr.slice(index + 1),
];
purchases.reduce(
  (acc, ({ userId, apples })) => {
    const userIndex = acc.findIndex(el => el.userId === userId);
    return userIndex === -1
      ? [...acc, { userId, apples }]
      : replaceElementInArray(acc)({
        ...acc[userIndex],
        apples: acc[userIndex].apples + apples,
      }, userIndex);
  }, []); // [ { userId: 53, apples: 6 }, { userId: 90, apples: 5 } ]

... but can also be used in a lot of different context. Since the output is not defined, you have limitless possibilities (you can even reimplement all the pure methods of Array prototype with it).

I would however not use this method in all situations: here is a pros / cons of the reduce() method and when to use it over map() / filter().

Pros

Can return something else an array.
Implements any behaviour (even some more complex manipulating objects, promises ...)

Cons

Less descriptive than map() and filter().
Harder to read on a first look (probably because it's exposing the logic around the accumulator).
Usually needs few back and forth to find the optimal way to write the reducer.

That being said, I totally advise you to start playing it - you will see, power is enjoyable 😉.

Cheat sheet

Method	Expected output	Example
map()	Array with the same number of elements.	[1,2,3].map(x => x * 2) // [2, 4, 6]
filter()	Array with less elements.	[1,2,3].filter(x => x > 1) // [2, 3]
reduce()	Anything else.	[1,2,3].reduce((acc, x) => acc + x) // 6

Resources

This post has been originally posted my blog: click here if you want to read more articles 🙂