Get best of the week

Theoretical data structures and their application in JavaScript. P1. Couples

“Bad programmers think about code. Good programmers think about data structures and their relationships, ”Linus Torvalds, creator of Linux.
We take as an axiom that very often the solution to any problem in programming comes down to choosing the right data structure. This axiom can be proved, but it is a long time and the article is a little about another. Today we will talk about one of the simplest theoretical structures, about the pair.

A pair is a data structure that stores any two data elements in itself, implying that we want to somehow logically combine them into one. It solves precisely this problem, i.e. if there are some data elements and bwe need to present them in the form b, then we can implement this design in pairs.

If you think that you have never encountered or will not encounter something like this, then this is not so.

Here is the simplest example of a computed property from the VUE documentation:

var vm = new Vue({
  el: '#demo',
  data: {
    firstName: 'Foo',
    lastName: 'Bar'
  },
  computed: {
    fullName: function () {
      return this.firstName + ' ' + this.lastName
    }
  }
})

From the point of view of theory, fullNamethis is a couple. And there are countless such examples in technology and the real world, which we often model with program code.

You can rightly notice that we can logically combine any number of elements and you will be right. This brings us to a more complex structural concept of composite data , one of which is a couple . We will deal with the composite data a little later, now we will focus on the pair.

The theory tells us that pairs have the following properties:

  • , .. - , , . , ( - . , )
  • . . . , , , , , .

    :

    pair = { a, b }

    If in the calling code we will work with the pair directly in this style: pair.athen changing the implementation of the pair we will be forced to rewrite the calling code wherever the call to the pair appears. This is not great!

    A couple is an abstraction (even a low level), so it would be wrong to work directly with its components. When working with the constituent parts of any abstraction, we must use the abstraction interface, otherwise the code will turn into chaos (it will become harder to read, easier to make a mistake, but most importantly more difficult to change, because one change will have to be made in different parts of the code).


Pairs can be implemented in very different ways. In any programming language, there is more than one opportunity to implement this data structure.
For example, you can implement a pair for arbitrary data types:

//       
//      
const pair = (first, second) => (elementType) => {
  switch(elementType) {
    case 'first':
     return first;
   case 'second':
     return second;
  }
};
//    ,      ,
//    
const getFirstElement = (pair) => (pair('first'));
const getSecondElement = (pair) => (pair('second'));

This way of working is called sending messages. Oddly enough, but it was this way of interaction between entities that was once called OOP before C / C ++.

Do we have to use the design switch ? Of course, not necessarily. These are the details of the technical implementation, and there can be a great many implementations!

The most important thing is to make the couple mutable!

For example, you can implement the same functionality using Map

//     
//  ,       
const pair = (first, second) => (
  new Map([
    ['first', first],
    ['second', second],
  ])
);
//    
const getFirst = (pair) => (pair.get('first'));
const getSecond = (pair) => (pair.get('second'));

Note that the first implementation can easily be replaced with the second. and the second to the first! The calling code will not change. This is an important advantage of abstractions. We can easily change the implementation of abstraction in the program, but the code working with this abstraction will not know about these changes. We will not need to edit the code that works with these abstractions if we want to change the implementation of the abstractions themselves. This is very important because saves customer money and raises developer bonuses.

By the way, let's say we don’t know about the existence of Mapov in js, but we can work with objects.

//       
//   
const pair = (first, second) => (
  Object.freeze({
    'first': first,
    'second': second,
  })
);
//    ,       
const getFirst = (pair) => (pair.first);
const getSecond = (pair) => (pair.second);

As you can easily guess, both previous implementations can also be replaced by a third one and nothing will change from this ( Actually, there is some difference. Maps do not throw exceptions when trying to change properties directly, but they throw “frozen objects” TypeError: Cannot assign to read only property. However, in the context of the article, this is not important. ).

Why do we need knowledge of theoretical data structures?


If we look at the work of a programmer from a bird's eye view, we will see that in essence he is engaged in that. which creates tools that manipulate certain data sets. Therefore, we constantly have to select some kind of storage structure for the data and come up with ways to work with them or give the chaotic data set a specific structure. Understanding the typical data structures allows us to own a set of ready-made solutions for different typical tasks and simply choose the most convenient way for a specific task.

Let

's analyze an example: “Implement a mechanism for working with fractions. Fractions should be stored in the usual format. those. in the form of 1/2. It is also necessary to implement basic operations (addition, subtraction, multiplication, division). Normalization needs to be provided. ”

Let's make sense of the condition of the problem! We need to implement an abstraction for some mathematical entity, therefore it is reasonable to refer to the original source . Of course, if experienced programmers read this text, then they must have immediately imagined the solution in code without reading the article on fractions in mathematics, but we will assume. that we faintly imagine how fractions work and illustrate the whole course of reasoning.

Wikipedia material tells us that fractions are ordinary (1/4) and decimal (0.1). Obviously, by the condition of the problem, we need to work with fractions in the usual presentation format.

We also see that the ordinary fraction is a logical union of twonumbers (numerator and denominator), this is the surest signal about the need to use a pair as a data structure for this task.

In the code, we could describe this structure as follows:

//        ,
//  ,    
//          ,
//     
const makeRational = (num, denom) => (
  new Map([
    ['num', num],
    ['denom', denom],
  ])
);

//  ,    
//   ,      ,    
//    
const getNumer = (rat) => (rat.get('num'));
const getDenom = (rat) => (rat.get('denom'));

Next, we should analyze the situation with fractions of such a plan 8/4, 6/9. The condition of the task says about the need to provide for normalization. The normalization of a fraction is the removal of the largest common divisor (GCD) from it.

We implement a function to search for GCD two numbers:

//Gcd     
const getGcd = (a, b) => ((a % b) ? getGcd(b, a % b) : Math.abs(b));

If the text of the function is not clear to you, then I advise you to read about recursion .

To normalize the fraction, we need to divide its numerator and denominator by GCD. We write the normalization function:

const normalize = (n1, n2) => {
  const commonDivisor = getGcd(n1, n2);
  return [n1 / commonDivisor, n2 / commonDivisor];
};

It would be logical to put normalization in the makeRational constructor to always normalize the data when creating the fraction.

const makeRational = (num, denom) => {
  const [normalizeNum, normalizeDenom] = normalize(num, denom);
  return new Map([
    ['num', normalizeNum],
    ['denom', normalizeDenom],
  ]);
};

Next, we’ll work on the operations interface.

1) Addition

To add two ordinary fractions, you should bring them to a common denominator. Then add the numerators and leave the denominator unchanged.

//..       ,
//       ,
//         
const add = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getDenom(rat2) + getNumer(rat2) * getDenom(rat1),
    getDenom(rat1) * getDenom(rat2),
  ));

2) Subtraction

In order to get the difference of fractions, they also need to be reduced to a common denominator, and then the numerators should be subtracted, the denominator should be left unchanged.

//    
//     
const sub = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getDenom(rat2) - getNumer(rat2) * getDenom(rat1),
    getDenom(rat1) * getDenom(rat2),
  ));

3) Multiplication

To multiply two ordinary fractions, you need to multiply their numerators and denominators.

const multi = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getNumer(rat2),
    getDenom(rat1) * getDenom(rat2),
  ));

4) Division

In order to divide one ordinary fraction into another, you need to multiply the first fraction by the fraction inverse of the second. The inverse is called a fraction whose numerator is equal to the denominator of the original, and the denominator is the numerator of the original.

const div = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getDenom(rat2),
    getDenom(rat1) * getNumer(rat2),
  ));

As you can see, in each operation we create a new entity. This is a consequence of the immutability rule. Note that in math operations do not change the original number of numbers, and create new: 1 + 2 = 3.

Should pay attention. that we can change the implementation makeRationalto any other, but the calling code will not know about it and will continue to work. This is a consequence of the fact that we correctly implemented the abstraction and work with its components through the interface, and not directly.

It is also important that the user can get their data in the usual way, so we introduce one additional function.

const ratToString = (rat) => `${getNumer(rat)}/${getDenom(rat)}`;

I will enclose a listing of tests:

describe('normalize', () => {
  test('should work', () => {
    expect(normalize(21, 6)).toEqual([7, 2]);
    expect(normalize(2, 3)).toEqual([2, 3]);
  });
});


describe('rational', () => {
  test('getters', () => {
    const rat1 = makeRational(3, 9);
    expect(getNumer(rat1)).toBe(1);
    expect(getDenom(rat1)).toBe(3);

    const rat3 = makeRational(-4, 16);
    expect(getNumer(rat3)).toBe(-1);
    expect(getDenom(rat3)).toBe(4);
  });

  test('add&sub', () => {
    const rat1 = makeRational(3, 9);
    const rat2 = makeRational(10, 3);
    expect(add(rat1, rat2)).toEqual(makeRational(11, 3));
    expect(sub(rat1, rat2)).toEqual(makeRational(-3, 1));

    const rat4 = makeRational(12, 5);
    const rat3 = makeRational(-4, 16);
    expect(add(rat3, rat4)).toEqual(makeRational(43, 20));
    expect(sub(rat3, rat4)).toEqual(makeRational(-53, 20));

    const rat5 = makeRational(1, 15);
    const rat6 = makeRational(4, 25);
    expect(add(rat5, rat6)).toEqual(makeRational(17, 75));
    expect(sub(rat5, rat6)).toEqual(makeRational(-7, 75));
  });

  test('multi&div', () => {
    const rat1 = makeRational(1, 2);
    const rat2 = makeRational(2, 3);
    expect(multi(rat1, rat2)).toEqual(makeRational(2, 6));

    const rat3 = makeRational(1, 3);
    const rat4 = makeRational(1, 2);
    expect(div(rat3, rat4)).toEqual(makeRational(2, 3));
  });

  test('ratToString', () => {
    const rat1 = makeRational(3, 9);
    const rat3 = makeRational(-4, 16);
    expect(ratToString(rat1)).toBe('1/3');
    expect(ratToString(rat3)).toBe('-1/4');
  });
});

Conclusion


The text turned out to be quite voluminous, but I hope it is clear. To summarize:

  1. We can use the steam data structure whenever we need to logically combine two unrelated values
  2. The couple must be immune
  3. The couple must provide an interface for working with their components

I apologize in advance if the article seemed overloaded to someone. I mainly focus on not very experienced developers, so I try to write in such a way that the logic of my reasoning and the choice of this or that solution are extremely clear.

If the article is of interest to the community. then the direction of typical data structures will continue. The next topic is related lists.

More articles:


All Articles