Пары как простейшие структуры данных

Абстракцию объектов, описываемых двумя параметрами возможно реализовать с помощью так называемых пар


Пара — это упорядоченный набор из двух значений, характеризующий какой либо объект, причем в составе этих значений возможно также наличие пары. Таким образом, можно составлять более сложные, вложенные структуры. Само понятие пары основывается на том, что ее нельзя изменить, при любом раскладе нужно будет создать новую такую структуру на основе предыдущей и обойти этот принцип не получится.

Для реализации пары, с точки зрения функционального программирования (и в данном случае в контексте JS), нужно создать функцию-конструктор и функции-селекторы, которые выбирают значения (first, second)

Реализовать пару можно несколькими способами, но на мой взгляд удобнее делать это посредством замыкания:

function pair(f, s) {
    return function (closure) {
        return closure(f, s);
    }
}

Селектор выбора первого значения из пары:

function fs(pair) {
    function closure(f, s) {
        return f;
    }

    try {
        return pair(closure);
    } catch (e) {
        console.log(e.toString());
    }
}

Селектор выбора второго значения из пары:

function sc(pair) {
    function closure(f, s) {
        return s;
    }

    try {
        return pair(closure);
    } catch (e) {
        console.log(e.toString());
    }
}

При создании пары, которая будет заведена в переменную, аргументы, передаваемые функции-конструктору сохранятся в контексте возвращаемой анонимной функции с последующим возвратом вызова этой анонимной функции. Здесь работает классическая схема замыкания, при которой запоминаются переданные значения, для последующего их использования. В данном случае мы на основе этого механизма объявляем функции-селекторы.

На основе этого подхода можно строить не только пары, но и конструкции, хранящие три и более значения. Для этого замыкаются, например, три переменные и пишется еще один селектор, выбирающий третье значение.

Как и для чего практически применяются пары? Возможно их использовать где угодно, где для идентификации какой либо сущности вам необходимо хранить в переменной несколько значений. Например, абстракция точки на координатной плоскости с абциссой Х и ординатой Y. Двигаясь в направлении от пар к определенным реализациям на них каких либо предметных областей, мы повышаем уровень абстракции.

Примеры

Реализуйте следующие функции для работы с точками:

quadrant — функция, которая вычисляет квадрант, в котором находится точка. Ниже приведена схема, показывающая номера квадрантов на плоскости:

quadrant

const point = makePoint(1, 5);
quadrant(point); // 1
quadrant(makePoint(3, -3)); // 4

Если точка не принадлежит ни одному квадранту, то функция должна возвращать null.

symmetricalPoint — функция, возвращающая новую точку, симметричную относительно начала координат. Такая симметричность означает, что меняются знаки у x и y.

symmetricalPoint(makePoint(1, 5)); // makePoint(-1, -5)

distance — функция, вычисляющая расстояние между точками по формуле: d = sqrt((x2−x1)^2+(y2−y1)^2)

distance(makePoint(-2, -3), makePoint(-4, 4)); // ≈ 7.28

Будем считать, что интерфейс точек под капотом построен на наших парах:

function makePoint(x, y) {
    return pair(x, y);
}

function getX(pair) {
    return fs(pair);
}

function getY(pair) {
    return sc(pair);
}
// ES6
const quadrant = (p) => {
    if (getX(p) > 0 && getY(p) > 0) {
        return 1;
    } else if (getX(p) < 0 && getY(p) > 0) {
        return 2;
    } else if (getX(p) < 0 && getY(p) < 0) {
        return 3;
    } else if (getX(p) > 0 && getY(p) < 0) {
        return 4;
    } else {
        return null;
    }
}

const symmetricalPoint = (p) => makePoint(-getX(p), -getY(p));

const distance = (p1, p2) => Math.sqrt(Math.pow(getX(p2) - getX(p1), 2) + Math.pow(getY(p2) - getY(p1), 2));

Реализуйте функцию reversePair, которая принимает на вход пару и возвращает другую, в которой значения переставлены местами:

// ES6
const reversePair = (pair) => pair(sc(pair), fs(pair));

Реализуйте функцию sumOfPairs, которая принимает на вход две пары и возвращает новую пару, в элементах которой находятся суммы элементов из исходных пар:

// ES6
const sumOfPairs = (pair1, pair2) => pair(fs(pair1) + fs(pair2), sc(pair1) + sc(pair2));

Однажды вы сидели дома, когда курьер Василий принес вам коробку. С коробкой шла записка следующего содержания:

Коробка состоит из двух отсеков, в одном из которых пусто, а в другом лежит еще одна коробка, в которой также два отсека и точно также один отсек пустой, а в другом - коробка. Коробки могут быть вложены друг в друга сколько угодно раз. Вам нужно добраться до коробки, внутри которой нет вложенной коробки, и отдать ее курьеру.

Подчеркну, что во всех коробках, кроме той последней, в одном отсеке пусто, а в другом - всегда коробка, но никогда не две коробки одновременно и никогда не две пустоты. Сами отсеки при этом могут меняться, то есть в одной коробке пустым отсеком может быть первый, а в другой - последний.

Реализуйте рекурсивную функцию findPrimitiveBox, которая принимает на вход "коробку" (пару), находит внутри нее пару без вложенных пар (как описано выше) и возвращает наружу.

// ES6
// TODO реализовать проверку isPair( )
const findPrimitiveBox = (pair) => {
  let f = fs(pair),
      s = sc(pair);
  if (!isPair(f) && !isPair(s) ) {
    return pair;
  } else {
      if (isPair(f)) {
        return findPrimitiveBox(f);
      } else {
        return findPrimitiveBox(s);
      }
  }
}

Рассмотрим задачу представления отрезков на прямой плоскости. Каждый отрезок представляется как пара точек: начало и конец. Он может быть быть описан, например, так: [(1, 3), (5, 4)]. Это означает, что наш отрезок начинается в точке (1, 3) и заканчивается в точке (5, 4) координатной плоскости.

В этом задании необходимо разработать абстракцию для работы с отрезками (англ. сегмент), которая позволяет строить их из точек, извлекать из отрезков составные части (начало или конец сегмента), а так же получать текстовое представление сегмента.

Абстракция заключается в том, что конкретное представление сегмента определяется внутри функций, описывающих работу с отрезками и зависит от создателя библиотеки. С точки зрения клиента библиотеки (кода который ее вызывает), не важно как конкретно устроен сегмент, важно только то, что есть некоторый набор функций (абстракция), позволяющий работать с ним.

  • Конструктор makeSegment, который принимает на вход две точки и возвращает сегмент. Первая точка это начало сегмента, вторая это конец.
  • Селекторы startSegment и endSegment, которые извлекают из сегмента его начальную и конечную точку соответственно.
  • Вспомогательную функцию segmentToString, которая возвращает текстовое представление сегмента: [(1, 2), (-4, -2)].
  • Функцию midpointSegment, которая находит точку на середине отрезка по формулaм: x = (x1 + x2) / 2 и y = (y1 + y2) / 2.
// ES6
// TODO реализовать строковое представление pointToString
const makeSegment = (point1, point2) => pair(point1, point2);
const startSegment = (segment) => fs(segment);
const endSegment = (segment) => sc(segment);
const segmentToString = (segment) => '[' + pointToString(startSegment(segment)) + ', ' + pointToString(endSegment(segment)) + ']';
const midpointSegment = (segment) => pair((fs(startSegment(segment)) + fs(endSegment(segment))) / 2, (sc(startSegment(segment)) + sc(endSegment(segment))) / 2);

Реализуйте абстракцию (набор функций) для работы с прямоугольниками, стороны которого всегда параллельны осям. При такой постановке, достаточно знать только три параметра для однозначного задания прямоугольника на плоскости: координаты левой-верхней точки, ширину и высоту. Зная их, мы всегда можем построить прямоугольник одним единственным способом.

rectangle

Основной интерфейс:

  • makeRectangle (конструктор) - создает прямоугольник. Принимает параметры: левую-верхнюю точку, ширину и высоту.
  • Селекторы startPoint, width и height

Вспомогательные функции для выполнения расчетов:

  • square — возвращает площадь прямоугольника (a * b).
  • perimeter — возвращает периметр прямоугольника (2 * (a + b)).
  • containsTheOrigin — проверяет, принадлежит ли центр координат прямоугольнику (не лежит на границе прямоугольника, а находится внутри). Чтобы в этом убедиться, достаточно проверить, что все точки прямоугольника лежат в разных квадрантах.
// ES6
const unique = (arr) => {
    let obj = {};
    for (let i = 0; i < arr.length; i++) {
        let str = parseInt(arr[i]);
        obj[str] = true;
    }
    return Object.keys(obj);
};
const makeRectangle = (p, w, h) => pair(p, pair(w, h));
const startPoint = (rect) => fs(rect);
const width = (rect) => fs(sc(rect));
const height = (rect) => sc(sc(rect));
const square = (rect) => width(rect) * height(rect);
const perimeter = (rect) => 2 * (width(rect) + height(rect));
const containsTheOrigin = (rect) => {
    let start = startPoint(rect),
        x_topLeft = fs(start),
        y_topLeft = sc(start),
        topLeft = quadrant(start),
        topRight = quadrant(makePoint(x_topLeft + width(rect), y_topLeft)),
        bottomLeft = quadrant(makePoint(x_topLeft, y_topLeft - height(rect))),
        bottomRight = quadrant(makePoint(x_topLeft + width(rect), y_topLeft - height(rect)));
    topLeft = (typeof(topLeft) === "object") ? 0 : topLeft;
    topRight = (typeof(topRight) === "object") ? 0 : topRight;
    bottomLeft = (typeof(bottomLeft) === "object") ? 0 : bottomLeft;
    bottomRight = (typeof(bottomRight) === "object") ? 0 : bottomRight;
    if (unique([topLeft, topRight, bottomLeft, bottomRight]).length
        !== [topLeft, topRight, bottomLeft, bottomRight].length)
        return false;
    return true;
};

Пары интересная вещь, если рассматривать их в контексте изучения концепций, позволяющих из простых типов данных составлять более сложные данные, необходимые для решения конкретной задачи и для реализации конкретной программы.



Похожие заметки:

Прелоадер до загрузки страницы

Показываем прелоадер на страницах сайта, до его полной загрузки, реализация плавного исчезновения гифки и появление контента

Открыть здесь

1700

Найти сумму произведений всех простых чисел

Найдите сумму произведений всех простых чисел, меньших 200, на их порядковые номера, считая, что первым простым числом является 2

Открыть здесь

521

Простое модальное окно на jQuery

Простой пример реализации модального окна, которое должно закрываться по клику вне области окна и быть открытым при кликах в нем

Открыть здесь

3318


Перед тем как писать комментарии, рекомендую ознакомиться:

Markdown синтаксис »

Оформление кода »

Нужна аватарка »

Комментарии