Использование неизменяемых структур данных #

Васильев Андрей Михайлович, 2022

Версии презентации

• Интерактивная презентация
• Текстовая версия

Содержание #

• Применение техники копирование при записи для обеспечения неизменяемости данных
• Разработка операций копирования при записи для массивов и объектов в JavaScript
• Доработка операций копирования при записи для работы с вложенными структурами данных

Применение неизменяемых структур данных #

• Обновление количества по наименованию работает над вложенными данными
• Вложенными данными называются структуры данных, которые вложены в другие структуры данных
• Данные могут быть глубоко вложенными, если есть несколько уровней вложения
• Можно ли применить неизменяемые данные для реализации №5?

Категоризация операций по действиям #

Каждую операцию с переменными можно разделить по операциям чтения и записи

• Чтение не изменяет данные, операции чтения являются вычислениями
• Запись изменяет данные каким-либо образом и требуют специального обращения

Проведём разделение для операций над корзиной

• Операции чтения: количество товаров, получение товара по названию
• Операции записи: добавление товара, удаление товара, изменение товара

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

В языке JavaScript структуры данных изменяемы по умолчанию, поэтому необходимо выполнять дополнительные явные действия, чтобы поддержать неизменность

Языки с неизменяемыми данными по умолчанию: Clojure, Elm, Haskell, Elixir, Erlang, PureScript

Три шага копирования при записи #

Техника копирование при записи (КПЗ) состоит всего из трёх шагов. Если применить технику КПЗ ко всем операциям при работе с корзиной, то она будет неизменяемой

function add_last(array, elem) {
  var new_array =
      array.slice();
  new_array.push(elem);
  return new_array;
}

1. Выполняется копия массива, оригинал не изменяется
2. Копия изменяется в локальном пространстве функции, недоступном для других
3. Возвращённая копия массива в дальнейшем не меняется

Данный метод не модифицирует переданные данные, возвращает информацию, значит это операция чтения. С помощью техники КПЗ можно преобразовать запись данных в чтение.

Применение КПЗ #

Рассмотрим следующий метод, который удаляет товар из корзины:

function remove_item_by_name(cart, name) {
  var index = null;
  for(var i = 0; i < cart.length; i++) {
    if(cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    cart.splice(index, 1); // Модификация
}

Метод Array.splice() позволяет удалять элементы из массива, она модифицирует массив, на котором была вызвана

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

Применение КПЗ #

// Оригинал
function remove_item_by_name(cart, name) {
  var index = null;
  for(var i = 0; i < cart.length; i++) {
    if(cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    cart.splice(index, 1);
}

// Шаг №1: создание копии данных
function remove_item_by_name(cart, name) {
  var new_cart = cart.slice();
  var index = null;
  for(var i = 0; i < cart.length; i++) {
    if(cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    cart.splice(index, 1);
}

// Шаг №2: модификация копии
function remove_item_by_name(cart, name) {
  var new_cart = cart.slice();
  var index = null;
  for(var i = 0; i < new_cart.length; i++) {
    if(new_cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    new_cart.splice(index, 1);
}


// Шаг №3: Возвращение копии
function remove_item_by_name(cart, name) {
  var new_cart = cart.slice();
  var index = null;
  for(var i = 0; i < new_cart.length; i++) {
    if(new_cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    new_cart.splice(index, 1);
  return new_cart;
}

Сам метод теперь работает согласно подходу копирование при записи

Осталось только изменить все места вызова данного метода

Рассмотрим работу обработчика события нажатия на кнопку удаления товара

// Оригинал
function delete_handler(item_name) {
  remove_item_by_name(shopping_cart, item);
  var total = calc_total(shopping_cart);
  set_cart_total_dom(total);
  update_shipping_icons(shopping_cart);
  update_tax_dom(total);
}

// Вызов изменённой функции
function delete_handler(item_name) {
  shopping_cart = remove_item_by_name(shopping_cart, item);
  var total = calc_total(shopping_cart);
  set_cart_total_dom(total);
  update_shipping_icons(shopping_cart);
  update_tax_dom(total);
}

Обобщение операций КПЗ #

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

function removeItems(array, index, count) {
  var copy = array.slice();
  copy.splice(index, count);
  return copy
}

// Применим данный метод
function remove_item_by_name(cart, name) {
  var new_cart = cart.slice();
  var index = null;
  for(var i = 0; i < new_cart.length; i++) {
    if(new_cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    new_cart.splice(index, 1);
  return new_cart;
}

function remove_item_by_name(cart, name) {
  var index = null;
  for(var i = 0; i < cart.length; i++) {
    if(cart[i].name === name)
      index = i;
  }
  if(idx !== null)
    return removeItems(cart, index, 1);
  return cart;
}

Краткий обзор массивов в JavaScript #

Массивы в JavaScript описываются с помощью класса Array

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

Обращение к элементу, [index] #

Получает ссылку на элемент, хранящийся по индексу. Номера начинаются с нуля

> var array = [1, 2, 3, 4];
> array[2]
3

Установить значение, [] = #

Оператор присваивания заменяет объект по индексу, изменяет массив

> var array = [1, 2, 3, 4];
> array[2] = "abc"
> array
[1, 2, "abc", 4]

Количество элементов, .length #

Содержит количество элементов в массиве, является свойством, а не методом

> var array = [1, 2, 3, 4];
> array.length
4

Копирование массива, .slice() #

Создаёт и возвращает неглубокую копию массива

> var array = [1, 2, 3, 4];
> array.slice()
[1, 2, 3, 4]

Добавление в конец, .push(element) #

Изменяет массив, добавляя элемент в его конец, возвращает новую длину массива

> var array = [1, 2, 3, 4];
> array.push(10)
5
> array
[1, 2, 3, 4, 5]

Удаление из конца массива, .pop() #

Изменяет массив, удаляя у него последний элемент. Возвращает значение удалённого элемента

> var array = [1, 2, 3, 4];
> array.pop();
4
> array
[1, 2, 3]

Добавление элемента в начало, .unshift(el) #

Изменяет массив, добавляя элемент в его начало. Возвращает новую длину

> var array = [1, 2, 3, 4];
> array.unshift(10);
5
> array
[5, 1, 2, 3, 4]

Удаление элемента из начала, .shfit() #

Изменяет массив, удаляет первый элемент массива. Возвращает значение удалённого элемента

> var array = [1, 2, 3, 4];
> array.shift()
1
> array
[2, 3, 4]

Удаление последовательности элементов, .splice(idx, num) #

Изменяет массив, удаляя указанные num элементов, начиная с номера idx. Возвращает удалённые элементы

> var array = [1, 2, 3, 4, 5, 6];
> array.splice(2, 3);
[3, 4, 5]
> array
[1, 2, 6]

Практикум по КПЗ #

Рассмотрим операцию добавления нового почтового адреса в список контактов

var mailing_list = [];

function add_contact(email) {
  mailing_list.push(email);
}

function submit_form_handler(event) {
  var form = event.target;
  var email = form.element["email"].value;
  add_contact(email);
}

Преобразуйте код add_contact, чтобы он использовал подход КПЗ

Вариант решения #

var mailing_list = [];

function add_contact(mailing_list, email) {
  var list_copy = mailing_list.slice();
  list_copy.push(email);
  return list_copy;
}

function submit_from_handler(event) {
  var form = event.target;
  var email = form.elements["email"].value;
  mailing_list = add_contact(mailing_list, email);
}

Что делать, если операция одновременно и чтения, и записи? #

Иногда функция выполняет одновременно две роли: она модифицирует значение и возвращает значение. Пример такой функции: .shift()

var array = [1, 2, 3, 4];
var element = array.shift();

Данный метод модифицирует массив и возвращает значение

Для его преобразования можно воспользоваться двумя подходами:

• Разделение функции на две: на запись и на чтение
• Возвращение нескольких значений из функций

Рассмотрим оба данных подхода, однако первый является предпочтительным

Разделение функции #

Данный подход состоит из двух этапов: выделение чтения из функции и преобразование записи в операцию копирования при записи

Выделение чтения для .shift() #

Логика чтения в методе .shift() заключается в получении первого элемента массива

function first_elemnet(array) {
  return array[0];
}

Преобразование функции в КПЗ #

function drop_first(array) {
  var array_copy = array.slice();
  array_copy.shift();
  return array_copy;
}

Возвращение двух значений из метода #

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

Оборачивание операции в функцию #

function shift(array) {
  return array.shift();
}

КПЗ-преобразование метода #

function shift(array) {
  var array_copy = array.slice();
  var first = array_copy.shift();
  return {
    first: first,
    array: array_copy
  };
}

Реализация shift-метода на основе разделённых методов #

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

function shift(array) {
  return {
    first: first_element(array),
    array: drop_first(array)
  }
}

Практикум #

Преобразуйте метод pop() в метод только для чтения двумя способами, которые были рассмотрены для метода shift()

Пример реализации #

Разделение на два метода #

function last_element(array) {
  return array[array.length - 1];
}
function drop_last(array) {
  var array_copy = array.slice();
  array_copy.pop();
  return array_copy;
}

Возвращение двух значений #

function pop(array) {
  var array_copy = array.slice();
  var last = array_copy.pop();
  return {
    last: last,
    array: array_copy
  };
}

Обсуждение #

Почему КПЗ-метод add_element_to_cart является чтением? #

Данный метод применяет технику КПЗ, не модифицирует свои аргументы и возвращает новый результат на их основании. Этот метод является методом-чтением (вычислением) по определению

Для реализации корзины использован массив, а для определения элемента используется поле «имя». Наверное ассоциативный массив (объект) был бы лучше в данном случае? #

Да, в данном случае это верно

Однако в рамках примеров мы продолжим использовать массивы, так как многие части существующего кода знают, что корзина — это массив

Кажется, что для преобразования данных к неизменяемым требуется много работы. Оно того стоит? Может ли это быть проще? #

В современном мире распределённых вычислений и многопоточного выполнения приложений использование неизменяемых данных позволяет снизить риск возникновения проблем

Язык JavaScript действительно плохо приспособлен к использованию таких данных: нет поддержки ни на уровне языка, ни на уровне среды исполнения

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

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

Практикум #

Реализация КПЗ-метода #

Реализуйте КПЗ-версию метода .push() для массива. Данный метод добавляет элемент в конец массива

Применение КПЗ-метода #

Используйте реализованный метод push в коде по добавлению контакта

function add_contact(mailing_list, email) {
  var list_copy = mailing_list.slice();
  list_copy.push(email);
  return list_copy;
}

Реализация КПЗ-метода #

Реализуйте КПЗ-метод, который позволит устанавливать значения элементам массива

function arraySet(array, index, value) {
  ...
}

Свойства функций-чтений #

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

Состояние приложения #

Предположим, что мы сможем преобразовать все операции записи в операции чтения. В таком случае встаёт вопрос: если все данные стали неизменными, то как приложение может отслеживать изменения, которые происходят? Как пользователь может добавить товар в корзину, если ничего не изменяется?

. . .

В приложении нам потребуется место для хранения изменяемых данных

В примере с корзиной таким местом является глобальная переменная shopping_cart

Значение данной переменной подменяется на новое после его вычисления

shopping_cart = add_item(shopping_cart, shoes);
shopping_cart = remove_item_by_name(shopping_cart, "shirt");

Шаблон подмены значения переменной часто применяется в ФЯП. Он позволяет реализовывать сложные операции, например операции отмены действия

Скорость работы приложения #

В общем случае применение неизменяемых структур данных потребует большего объёма оперативной памяти и будет работать медленнее по сравнению с применением изменяемых структур данных

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

Избегайте ранней оптимизации #

На ранних этапах разработки зачастую трудно узнать о проблемных с точки зрения производительности местах. Это верно вне зависимости от используемого подхода к разработке ПО

В большинстве промышленных ФЯП можно при необходимости выполнить оптимизацию с помощью изменяемых данных

Сборщики мусора очень быстрые #

В большинстве сред выполнения языков программирования была проведена большая работа по улучшению работы сборщиков мусора. Слушателям рекомендуется самостоятельно изучить выработанные техники

Объём копируемых данных не настолько велик #

Если мы рассмотрим функции, реализующие КПЗ, то увидим, что объём копирования на самом деле не большой. Например при работе над корзиной из 100 товаров при копировании происходит только создание массива со 100 ссылками

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

ФЯП предоставляют оптимизированные методы #

Текущие методы опираются на систему типов JavaScript, используя самую простую реализацию. Для приложения-примера этого достаточно

В специализированных языках применяются специально разработанные методы, которые эффективно используют оперативную память для реализации шаблона КПЗ

КПЗ для объектов #

Мы рассмотрели вариант реализации КПЗ для массивов в JavaScript. Однако нам необходимо выполнять операции над товарами, которые представлены в виде объектов

Общая структура действий остаётся одинаковой: сделать копию, модифицировать копию, возвратить копию

Копирование объектов в JavaScript #

Для решения задачи с массивами мы использовали метод .slice(). Для объектов такого метода нет, поэтому мы воспользуемся другим подходом - копированием всех ключей и значений

var object = {a: 1, b: 2};
var object_copy = Object.assign({}, object);

Изменение цены товара #

Для изменения цены товара реализуем метод setPrice

function setPrice(item, new_price) {
  var item_copy = Object.assign({}, item);
  item_copy.price = new_price;
  return item_copy;
}

Поверхностное копирование #

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

Данные массивы будут совместно использовать объекты, на которые они ссылаются. Если оба массива остаются неизменяемыми, то разделение не является проблемой

Краткий обзор объектов в JavaScript #

Объекты в JavaScript представляют собой ассоциативные массивы, которые содержат пары ключ-значение и у который ключи являются уникальными

Получение значения по ключу, [key] #

Данный метод получает значение по ключу. Если ключа нет, то возвращает undefined

> var object = {a: 1, b: 2};
> object["a"]
1

Получение значения по ключу, .key #

Альтернативный синтаксис для получения значения

> var object = {a: 1, b: 2};
> object.a
1

Установка значения .key = или [key] = #

Можно установить значение по ключу, изменив объект. Если ключ уже существует, то старое значение будет заменено

> var object = {a: 1, b: 2};
> object["a"] = 7;
7
> object
{a: 7, b: 2}
> object.c = 10;
10
> object
{a: 7, b: 2, c: 10}

Удаление пары ключ-значение, delete #

Данный метод изменяет объект. После его вызова указанная пара ключ-значение удаляется из указанного объекта

> var object = {a: 1, b: 2};
> delete object["a"];
1
> object
{b: 2}

Копирование объекта Object.assign(a, b) #

Данный метод копирует все пары ключ-значения из объекта b в объект a, изменяя его

> var object = {x: 1, y: 2};
> Object.assign({}, object);
{x: 1, y: 2}

Получение списка ключей Object.keys() #

Данный метод удобно применять, если мы хотим пройти по всем парам объекта. Сначала получаем массив ключей, а затем используем значения из него, чтобы получить все значения

> var object = {a: 1, b: 2};
> Object.keys(object);
["a", "b"]

Создание КПЗ-методов для работы с объектами #

Реализуйте КПЗ-методы для рассмотренных ранее методов модифицирования

Установка значения #

Установка значения: function objectSet(object, key, value)

Используйте метод для установки цены для объекта:

function setPrice(item, new_price) {
  var item_copy = Object.assign({}, item);
  item_copy.price = new_price;
  return item_copy;
}

И для метода установки количества:

function setQuantity(item, new_quantity) {}

Удаление пары ключ-значение #

Реализуйте КПЗ-метод для удаления пары ключ-значение

function objectDelete(object, key) {}

Преобразование вложенных записей в чтение #

Даже после применения всех созданных методов операция изменения цены осталась операцией-записью. Она изменяет объект, вложенный в массив корзины

У нас уже есть КПЗ-опреация для вложенного объекта, осталось её применить

function setPriceByName(cart, name, price) {
  for(var i = 0; i < cart.length; i++) {
    if(cart[i].name === name) {
      cart[i].price = price;
    }
  }
}

function setPriceByName(cart, name, price) {
  var cartCopy = cart.slice();
  for(var i = 0; i < cartCopy.length; i++) {
    if(cartCopy[i].name === name) {
      cartCopy[i] = setPrice(cartCopy[i], price);
    }
  }
  return cartCopy;
}

Операции над вложенными данными работают по схожей технологии: сделать копию, модифицировать её, вернуть копию

Единственное отличие - выполнение КПЗ над вложенной структурой данных

• Если мы будем просто модифицировать вложенную структуру, тогда и вся структура корзины становится изменяемой
• Вся структура данных, включая вложенные типы, должна оставаться без изменений, чтобы быть неизменяемой

Что копируется? #

Предположим, что у нас есть три элемента в корзине: футболка, носки и ботинки. В результате у нас есть 1 массив и 3 объекта

Мы установим цену для футболки в 700 рублей, вызываем метод setPriceByName

function setPriceByName(cart, name, price) {
  var cartCopy = cart.slice(); // Копируем массив
  for(var i = 0; i < cartCopy.length; i++) {
    if(cartCopy[i].name === name) {
      cartCopy[i] = setPrice(cartCopy[i], price); // Копируем объект
    }
  }
  return cartCopy;
}

Были скопированы только массив и объект, так как делаются поверхностные копии

Практикум #

Предположим, что корзина состоит из четырёх элементов:

var shopping_cart = [
  {name: "shoes", price: 10},
  {name: "socks", price: 3},
  {name: "pants", price: 27},
  {name: "t-shirt", price: 7}
]

И мы выполним следующий код:

setPriceByName(shopping_cart, "socks", 2);

Какие объекты будут скопированы? Какие будут заменены?

Реализация КПЗ для установки числа #

Преобразуйте следующий метод с помощью техники КПЗ

function setQuantityByName(cart, name, quantity) {
  for(var i = 0; i < cart.length; i++) {
    if(cart[i].name === name)
      cart[i].quantity = quantity;
  }
}

Заключение #

• В ФЯП стремяться использовать неизменяемые структуры данных. Невозможно реализовать вычисления на изменяемых данных
• Дисциплина КПЗ позволяет добиться неизменности данных. Изменение происходит на копии
• В рамках КПЗ мы делаем поверхностные копии данных перед изменением копии и возвращения её. Она применима для реализации неизменности на исходном коде, который вы контролируете
• Можно реализовать КПЗ-операции для базовых типов массивов и объектов, чтобы уменьшить количество повторений в коде