Функциональное итерирование #

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

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

Содержание #

  • Изучение трёх функциональных инструментов: map, filter и reduce
  • Рассмотрение вопроса применения данных инструментов для замены простых циклов
  • Рассмотрение реализации трёх функциональных инструментов

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

Новое подразделение компании #

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

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

Основная проблема — надо посылать письма именно заинтересованным пользователям, а не всем сразу и тем более не неправильным адресатам

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

Задача № 1: реализовать процесс отправки купонов из лекции № 3 # 

function emailsForCustomers(customers, goods, bests) {
  var emails = [];
  for(var i = 0; i < customers.length; i++) {
    var customer = customers[i];
    var email = emailForCustomer(customer, goods, bests);
    emals.push(email);
  }
  return emails;
}
  • Это уже вычисление, не действие
  • Однако команде потребуется написать ещё десятки (или сотни) таких функций
  • Можно избавиться от итерирования с помощью forEach
function emailsForCustomers(customers, goods, bests) {
  var emals = [];
  forEach(customers, function(customer) {
    var email = emailForCustomer(customer, goods, bests);
    emails.push(email);
  });
  return emails;
}
  • Функция стала короче, для написания требуется меньше усилий
  • Однако тут ещё присутствует много элементов, которые надо будет повторять в подобных функциях

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

Для решения этой задачи в ФЯП используется функция map(). Она принимает 2 аргумента: массив и функцию, которая формирует элементы нового массива

Создание map() из примеров # 

function emailsForCustomers(customers, goods, bests) {
  var emals = [];
  forEach(customers, function(customer) {
    var email = emailForCustomer(customer, goods, bests);
    emails.push(email);
  });
  return emails;
}

function customerFullNames(customers) {
  var fullNames = [];
  forEach(customers, function(customer) {
    var name = customer.name + ' ' + customer.lastName;
    fullNames.push(name);
  });
  return fullNames;
}
function biggestPurchasePerCustomer(customers) {
  var purchases = [];
  forEach(customers, function(customer)) {
    var purchase = biggestPurchase(customer);
    purchases.push(purchase);
  });
  return purchases;
}

function customerCities(customers) {
  var cities = [];
  forEach(customers, function(customer) {
    var city = customer.address.city;
    cities.push(city);
  });
  return cities;
}

Дублирование в этих функциях можно исправить с помощью рефакторинга замены тела функции с помощью функции обратного вызова

// Оригинал
function emailsForCustomers(customers, goods, bests) {
  var emals = [];
  forEach(customers, function(customer) {
    var email = emailForCustomer(customer, goods, bests);
    emails.push(email);
  });
  return emails;
}

// Создаём функцию, содержащую общие элементы
function map(array, f) {
  var newArray = [];
  forEach(array, function(element) {
    newArray.push(f(element)); // Вызов
  });
  return newArray;
}
// Используем данную функцию
function emailsForCustomers(custmers, goods, bests) {
  return map(customers, function(customer) {
    return emailForCustomer(customer, goods, bests);
  });
}

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

Инструмент ФЯП: map() # 

function map(array, f) { // Принимает массив и функцию
  var newArray = [];     // Создаёт новый массив
  forEach(array, function(element) {
    newArray.push(f(element)); // Создаёт новый элемент
                               // и записывает в массив
  });
  return newArray;       // Возвращает созданный массив
}

Функция map() создаёт новый массив на основании существующего массива и правила генерации. Обе части функции map() передаёт пользователь

Наиболее просто применять map() на функциях-вычислениях, так как переданная функция будет вызываться функцией map()

Применение функции map() # 

function emailForCustomers(customers, goods, bests) {
  // Передаём массив и функцию-генератор новых значений
  return map(cestomers, function(customer) {
    return emailForCustomer(customer, goods, bests);
  });
}

Почему мы называли переменную customer?

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

Три способа описать функцию в JavaScript #

Глобально определённые функции #

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

function greet(name) {
  return "Hello, " + name;
}
var friendsGreetings = map(friendsNames, greet);

Анонимные встроенные функции #

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

var friendsGreetings = map(friendsNames, function(name) {
  return "Hello, " + name;
});

Локально определённая функция #

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

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

function greetEverybody(friends) {
  var greeting;
  if(language === "English")
    greeting = "Hello, ";
  else
    greeting = "Salut, ";

  var greet = function(name) {
    return greeting + name;
  };
  return map(friends, greet);
}

Пример применения map() #

Предположим, что нам необходимо сформировать список email-адресов всех клиентов

map(customers, function(customer) {
  return customer.email;
});

Нам де-факто потребовалось только реализовать функцию, которая получает данные одного покупателя и формирует на её основе email-адрес

Потенциальные проблемы данного определения:

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

Практика #

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

Входные данные:

  • customers — массив из объектов, описывающих покупателей
  • customer.firstName, customer.lastName, customer.address содержат необходимую информацию

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

map(customers, function(customer) {
  return {
    firstName: customer.firstName,
    lastName: customer.lastName,
    address: customer.address
  }
});

Новый запрос: список лучших клиентов #

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

Для решения задачи нельзя использовать map(), так как данный метод всегда возвращает новый массив, количество элементов которого совпадает с изначальным массивом

Рассмотрим императивную реализацию:

function selectBestCustomers(customers) {
  var newArray = [];
  forEach(customers, function(customer) {
    if(customer.purchases.length >= 3)
      newArray.push(customer);
  });
  return newArray;
}

Функция очень похожа на map() однако она не создаёт новый элемент, а создаёт новый массив, в который входят только искомые элементы

Создание filter() на основании примеров # 

function selectBestCustomers(customers) {
  var newArray = [];
  forEach(customers, function(customer) {
    if(customer.purchases.length >= 3)
      newArray.push(customer);
  });
  return newArray;
}

function selectCustomersBefore(customers, date) {
  var newArray = [];
  forEach(customers, function(customer) {
    if(customer.signupDate < date)
      newArray.push(customer);
  });
  return newArray;
}
function selectCustomersAfter(customers, date) {
  var newArray = [];
  forEach(customers, function(customer) {
    if(customer.signupDate > date)
      newArray.push(customer);
  });
  return newArray;
}

function singlePurchaseCustomers(customers) {
  var newArray = [];
  forEach(customers, function(customer) {
    if(customer.purchases.length === 1)
      newArray.push(customer);
  });
  return newArray;
}
function selectBestCustomers(customers) { // Общий заголовок
  var newArray = [];                      //
  forEach(customers, function(customer) { //
    if(customer.purchases.length >= 3)
      newArray.push(customer);            // Общее окочнание
  });                                     //
  return newArray;                        //
}

Замена функцией обратного вызова # 

function selectBestCustomers(customers) {
  return filter(customers, function(customer) {
    return customer.purchases.length >= 3;
  });
}

function filter(array, f) {
  var newArray = [];
  forEach(array, function(element) {
    if(f(element))
      newArray.push(element);
  });
  return newArray;
}
  • Функция filter() представляет общий интерфейс для итерирования по элементам массива
  • Функция-фильтр может быть определена локально, глобально, встроенной

Инструмент ФЯП: filter() # 

function filter(array, f) { // Принимает массив и функцию
  var newArray = [];        // Создаёт новый массив
  forEach(array, function(element) {
    if(f(element)) // Вызвает f для принятия решения
      newArray.push(element); // Добавляет элемент в новый массив
  });
  return newArray;          // Возвращает новый массив
}
  • Сигнатура метода очень похожа на map()
  • filter() делает выборку из оригинального массива согласно правилу, определённому внутри функции-аргумента
  • Функция принимает решение путём преобразования элемента массива к логическому значению: если значение правдиво, то элемент выбирается
  • Такие функции называются предикатами
  • Удобнее всего работать с filter(), если ей в качестве аргумента передавать функцию-вычисление

Пример: покупатели без покупок #

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

  • Вход: список покупателей
  • Выход: список покупателей, которые не совершили покупки
  • Функция-предикат: принимает покупателя и возвращает правду, если нет покупок
filter(customers, function(customer) {
  return customer.purchases.length === 0;
});

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

Пример: фильтр null-значений #

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

var allEmails = map(customers, function(customer) {
  return customer.email; // Данное поле может быть null
});

var emailsWithoutNulls = filter(allEmails, function(email) {
  return email !== null; // Выбираем не null-значения
});

Функции map() и filter() успешно дополняют друг друга

Практика #

Команде маркетинга необходимо сделать выборку из всех клиентов, чтобы проверить свою новую стратегию. Им необходимо выбрать примерно треть клиентов

Для решения данной задачи достаточно выбрать клиентов, чей ID делится без остатка на 3

Входные данные:

  • Список всех клиентов хранится в массиве customers
  • Для получения идентификатора необходимо обратиться к идентификатору, id: customer.id
  • Для получения остатка от деления можно воспользоваться %

Результат:

  • testGroup содержит массив клиентов, вошедших в тестовую выборку
  • nonTestGroup содержит массив клиентов, не вошедших в тестовую выборку

Пример решения

var testGroup = filter(customers, function(customer) {
  return customer.id % 3 === 0;
});

var nonTestGroup = filter(customers, function(customer) {
  return customer.id % 3 !== 0;
});

Запрос: количество всех покупок всех клиентов #

Необходимо вычислить число покупок для всех клиентов, то есть общую характеристику для всего массива, а не для определённого элемента

Для решения задачи нельзя использовать map() или filter(), которые возвращают массив на основании существующего массива, а нам необходимо число

Рассмотрим императивную реализацию:

function countAllPurchases(customers) {
  var total = 0;
  forEach(customers, function(customer) {
    total = total + customer.purchaces.length;
  });
  return total;
}

Данная функция проходит по массиву как map() и filter(), но внутри происходит агрегированное вычисление значения на основе элементов массива

Создание reduce() на основании примеров # 

function countAllPurchases(customers) {
  var total = 0;
  forEach(customers, function(customer) {
    total = total + customer.purchaces.length;
  });
  return total;
}

function customersPerCity(customers) {
  var cities = {};
  forEach(customers, function(customer) {
    cities[customer.address.city] += 1;
  });
  return cities;
}
function concatenateArrays(arrays) {
  var result = [];
  forEach(arrays, function(array) {
    result = result.concat(array);
  });
  return result;
}

function biggestPurchase(purchaces) {
  var biggest = {total:0};
  forEach(purchaces, function(purchase) {
    biggest = biggest.total > purchase.total ?
              biggest : purchase;
  });
  return total;
}
function countAllPurchases(customers) {   // Общее начало
  var total = 0;                          // Уникальная инициализация
  forEach(customers, function(customer) { //
    total = total + customer.purchases.length;
  });                                     // Общее окончание
  return total;                           //
}

Замена функцией обратного вызова # 

function countAllPurchases(customers) {
  return reduce(customers, 0, function(total, customers) {
    return total + customers.purchase.length;
  });
}

function reduce(array, init, f) {
  var accum = init;
  forEach(array, function(element) {
    accum = f(accum, element);
  });
  return accum;
}
  • Функция reduce() предоставляет общий интерфейс итерирования
  • В отличие от предыдущих функций добавился ещё 1 аргумент - изначальное значение
  • Вызываемая функция принимает 2 аргумента: наработанное значение и текущее значение из массива

Инструмент ФЯП: функция reduce() # 

function reduce(array, init, f) { // Массив, изначальное значение, функция
  var accum = init;               // Инициализация накопителя
  forEach(array, function(element) {
    accum = f(accum, element);    // Вычисление следующего значения
                                  // переменной-накопителя
  });
  return accum;                   // Вернуть вычисленное значение
}
  • Функция reduce() вычисляет значение путём обхода массива
  • Значение может быть вычислено разными способами: сложение элементов, умножение, конкатенация строк, запись в ассоциативный массив
  • Функция-аргумент определяет подход к формированию значения накопителя
  • Функция-аргумент принимает 2 аргумента: текущее значение накопителя и текущее значение элемента массива. Её задача — вычислить новое значение
  • Функция-аргумент будет применена к каждому элементу массива

Пример: конкатенация строк #

Допустим, что у нас есть массив из строк и нам необходимо конкатенировать их

  • Вход: массив строк
  • Выход: строка, состоящая из соединённых вместе строк
  • Функция: принимает накопленную строку и текущую строку из массива для конкатенации
reduce(strings, "", function(accum, string) {
  return accum + string;
});

Особенности применения reduce() #

Функция принимает 3 аргумента, разных по своей природе. Функция-аргумент принимает 2 аргумента, что усложняет работу с данной функцией

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

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

Другая проблема — определение изначального значения

  • С чего начинается вычисление? Для сложения — с нуля, для умножения — с единицы
  • Какое значение должно вернуться при работе с пустым массивом? В случае конкатенации строк — пустая строка

Практика: сложение и умножение #

Бухгалтерскому отделу в рамках своей работы необходимо складывать и перемножать числа. Реализуйте методы sum(numbersn) и product(numbers), выполняющие данные операции над массивами из чисел numbers

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

function sum(numbers) {
  return reduce(numbers, 0, function(total, num) {
    return total + num;
  });
}

function product(numbers) {
  return reduce(numbers, 1, function(total, num) {
    return total * num;
  });
}

Практика: минимум и максимум #

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

Входные данные:

  • Number.MAX_VALUE — наибольшее число в языке JavaScript
  • Number.MIN_VALUE — наименьшее число в языке JavaScript
function min(numbers) {
  return reduce(numbers, Number.MAX_VALUE, function(m, n) {
    if(m < n) return m;
    else      return n;
  });
}

function max(numbers) {
  return reduce(numbers, Number.MIN_VALUE, function(m, n) {
    if(m > n) return m;
    else      return n;
  });
}

Практика: анализ вызовов функций #

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

  1. Что вернёт map(), если ей передать пустой массив: map([], xToY)?
  2. Что вернёт filter(), если ей передать пустой массив: filter([], isGood)?
  3. Что вернёт reduce(), если ей передать пустой массив: reduce([], init, combine)?
  4. Что вернёт map(), если ей передать функцию, которая возвращает оригинальный элемент: map(array, function(x) { return x; })?
  5. Что вернёт filter(), если ей передать функцию, которая всегда возвращает true: filter(array, function(_x) { return true; })?
  6. Что вернёт filter(), если ей передать функцию, которая всегда возвращает false: filter(array, function(_x) { return false; })?
  1. []
  2. []
  3. init
  4. Поверхностную копию array
  5. Поверхностную копию array
  6. []

Применение reduce() #

Данная функция является настолько мощной, что с её помощью можно реализовать map() и filter(), но не наоборот

Отмена / повтор #

Если спроектировать действия пользователей как список действий, то реализация функций «отмена» и «повтор» сводится к изменению списка и выполнению reduce()

Повтор действий пользователя для тестирования #

При использовании модели из предыдущего пункта легко реализовать просмотр действий пользователя — начинаем с пустого состояния и «проигрываем» действия пользователя с помощью reduce()

Редактирование кода в режиме отладки #

В ряде сред программирования во время точки остановки можно изменять предыдущие фреймы. После исправления ошибки в одном из фреймов можно продолжить выполнение приложения. Эта функция реализована с помощью reduce()

Практика: реализация map() и filter() #

Реализуйте методы map() и filter() с помощью reduce()

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

function map(array, f) {
  return reduce(array, [], function(ret, item) {
    return ret.concat([f(item)]); // Не изменяем аргумент
  });
}

function map(array, f) {
  return reduce(array, [], function(ret, item) {
    ret.push(f(item)); // Изменяем аргумент, более эффективная
    return ret;        // реализация
  });
}
function filter(array, f) {
  return reduce(array, [], function(ret, item) {
    if(f(item)) return ret.concat([item]); // Не изменяем аргумент
    else        return ret;
  });
}

function filter(array, f) {
  return reduce(array, [], function(ret, item) {
    if(f(item))
      ret.push(item); // Изменяем аргумент, более эффективно
    return ret;
  });
}

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

В данном случае это нормально, т.к. функция-действие определена и используется исключительно внутри методов map() и filter()

Сравнение функциональных инструментов #

map() трансформирует массив в новый массив путём применения функции к каждому элементу # 

map(array, function(element) {
  ...

return newElement; // Надо вернуть новый элемент
});

filter() выбирает подмножество элементов массива в новый массив # 

filter(array, function(element) {
  ...
  return true; // Надо вернуть true или false
});

reduce() вычисляет агрегированное значение по элементам массива # 

reduce(array, 0, function(accum, element) {
  ...
  return combine(accum, element); // Вернуть следующее значение накопителя
});

Заключение #

  • Рассмотренные функции map(), filter() и reduce() являются наиболее часто используемыми инструментами ФЯП
  • map(), filter() и reduce() являются специализированными «циклами» по массивам. Они заменяют циклы на более специфичные версии, у которых определены чёткие цели
  • map() преобразовывает массив в новый массив. Каждый элемент массива преобразовывается с помощью переданной функции
  • filter() выбирает подмножество оригинального массива в новый массив. Критерии выбора описаны в переданной функции
  • reduce() комбинирует элементы массива и переданное изначальное значение в результирующее значение