Автор статьи: Дмитрий Володин

Analytics Engineer в Trafficstars

"На небе только и разговоров, что о функциональном программировании."

Всем привет. Меня зовут Дмитрий Володин, я Analytics Engineer в TrafficStars. Сегодня я хочу рассказать вам о приёмах ФП в R. Исходить я постараюсь из более-менее реальных задач, а не учебных, чтобы показать, что элементам ФП вполне есть место в вашем ящике с инструментами.

Структуры данных в R

Надо немного сказать про структуры данных в R и про то, как объекты хранятся в памяти. В R нет скалярных структур. Даже если сделать x <- 42, всё равно это будет вектор, просто с длиной 1. И он хранится в определённой области памяти. Любое изменение с ним ведёт к тому, что весь измененный вектор будет храниться уже в другой области памяти.

Списки ведут себя немного иначе. Списки - это коллекция векторов (все датафреймы и прочее - просто вариации списков по сути). Список - сам по себе занимает область памяти, в которой хранятся ссылки на элементы списка. Если изменить элемент списка - и элемент и сам список сменят прописку. Неизменённые объекты останутся на своих местах. Довольно похоже на привычную вещь в ФП: объекты по большей части имутабельны.

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

*Надо оговориться, что под капотом в любом случае (если не явно, то на уровне машины) у вас будет цикл. Но цикл оптимизированный и написанный со знанием дела специалистами в области computer science. Можно и нужно им довериться.

Функции высших порядков

Если мы посмотрим на синтаксис создания функции в R

my_func <- funciton(a, b = 1) {
	a / b - b
}

то заметим, что они создаются также, как и другие объекты: оператором присваивания. Функции в R - граждане первого класса и с ними можно делать тоже самое, что и с другими объектами. Например, передавать в качестве аргументов в другие функции. Функции, которые используют другие функции в качестве аргументов, называются функциями высшего порядка.

В R есть классические функции высших порядков: Map, Reduce, Filter. Я специально не буду рассматривать *apply функции, потому что про них довольно много сказано.

• Map(f, ...) (можно перевести как отображение) - применение функции f к элементам списков в ... поэлементно. Возвращает список длиной согласно правилам рециркуляции векторов.

• Reduce(f, x, init, right = FALSE, accumulate = FALSE) - редукция списка x через функцию f. Функция принимает два аргумента. Первый - результат вычисления функции на предыдущей операции, второй - текущий элемент списка. Проще понять будет на примере.

• Filter(f, x) - фильтрация списка. Остаются только те элементы, для которых результат применения f возвращает TRUE.

Большинство функций в R векторизовано. То есть применяется поэлементно и так. Например складывать два вектора не надо в цикле поэлементно. Достаточно просто написать v1 + v2 и элементы векторов сложатся. Но существуют функции, которые принимают один аргументы. Именно для таких случаев и существуют функции высших порядков. Как всегда, проще на примере.

# созадим сразу список с результатами кластеризации по списку с количеством центроидов
kmeans_results <- Map(kmeans, list(mtcars), 2:6)

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

Знающие люди могут спросить: "Но ведь если посмотреть исходный код функций, там всё равно будут циклы? И если так, зачем вот эти сложные концепции, когда можно просто написать цикл в лоб?". Ну во-первых, написать цикл в лоб не так просто, как кажется, особенно учитывая работу с памятью в R. Наверняка на цикл её уйдёт больше, а может ещё и времени тоже. А во-вторых, писать цикл просто-напросто дольше.

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

Map(kmeans, list(mtcars), 1:6)

my_func <- function(df, x) {
  cl_list <- list()
  length(cl_list) <- x
  for (i in seq_len(x)) {
    cl_list[[i]] <- kmeans(df, i)
  }
  return(cl_list)
}

microbenchmark(
  Map(kmeans, list(mtcars), 1:6),
  my_func(mtcars, 6)
) %>% 
  as_tibble() %>% 
  mutate(time = time / 10e9) %>% 
  ggplot(aes(x = expr, y = time, fill = expr))+
  geom_boxplot()+
  coord_flip()+
  scale_fill_manual(values = c('#FF9E18', '#7D62F4'))+
  theme_bw()+
  theme(legend.position = 'bottom', axis.text.y.left = element_blank())

Теперь о Reduce. Если нужно вычислить вектор, где каждый последующий элемент вычисляется на основе расчёта предыдущего, то можно и нужно использовать Reduce. Например при расчёте факториала используются результаты на предыдущих итерациях: факториал 5 равен 5, умноженному на факториал 4.

Reduce(`*`, 1:5)
1 * 2 == 2
2 * 3 == 6
6 * 4 == 24
24 * 5 == 120

После самого вызова Reduce я раскрыл, как именно происходит расчёт. Заодно разберёмся, что за функция используется в первом аргументе.

В Reduce необходимо передавать функцию от двух аргументов: первый является результатом расчёта Reduce на предыдущем шаге, а второй - текущим элементом из исходного вектора. И к ним применяется функция f. В данном случае функция - бинарный оператор перемножения. Все операторы в R по сути своей функции, потому мы спокойно можем писать их вот как ниже или использовать в функциях высшего порядка (только окружить бэктиками надо)

`*`(24, 5)

Ну а под вызовом Reduce я расписал, что происходит на каждом шаге. Сначала перемножаются первые два элемента (получается 2). Этот результат затем перемножается с третьим элементом (получается 6). И так далее.

Если в Reduce передать в аргумент accumulate значение TRUE, то Reduce вернёт все промежуточные результаты. А если передать в аргумент init какое-то значение, то оно будет использоваться в качестве первого аргумента в первом расчёте.

Filter(\(x) x %% 2 == 0, x = as.numeric(1:20)) |>
  Reduce(`*`, x = _, accumulate = TRUE)

Здесь заодно есть и оператор конвейера (|>) и лямбда (\(x)). Об этом и поговорим в следующем разделе.

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

# вот так гораздо лучше
x <- 1:20
x[x %% 2 == 0]

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

Пример выше преобразует изначальный вектор 1:20 в произведение всех чётных его членов с сохранением промежуточных элементов. Подведу к конвейерам издалека на этом примере. Начнём с того, что наделаем кучу переменных.

starting_vector <- 1:10
numeric_vector <- as.numeric(x = starting_vector)
filtered_vector <- Filter(\(x) x %% 2 == 0, x = numeric_vector)
reduced_vector <- Reduce(`*`, x = filtered_vector, accumulate = TRUE)

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

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

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

# здесь в фильтр сразу передаём вектор с изменённым типом, просто пример
Filter(\(x) x %% 2 == 0, as.numeric(1:20))

# а это финал, тут в аргумент x передаём предыдущую строчку
reduced_vector <- Reduce(`*`, x = Filter(\(x) x %% 2 == 0, as.numeric(1:20)), accumulate = TRUE)

Итак можно делать со сколь угодно глубокой вложенностью. К сожалению, так сильно страдает читаемость кода, потому что в основном люди читают сверху вниз и слева направо. И получается, что этот вызов будет прочитан с конца: сначала Reduce, а уже потом Filter. Для композиции из большого количества вызовов это превратится в жуткое нечитаемое месиво. Зато здесь создаётся только одна переменная.

Чтобы наш код был также понятен, как в первом примере, но при этом не имел кучи промежуточных переменных, существует оператор конвейера. До четвёртой версии R он был только в дополнительных пакетах (пусть и очень популярных; в этой же статье я использую %>% из пакета magrittr), но сейчас есть в стандартном наборе инструментов: |>.

f(g(h(x)))
# тоже самое, что и
x |> h() |> g() |> f()

# для передачи предыдщуего результата в конкретный аргумент 
# следующей функции используется placeholder _
# без такого явного указания значение из вызова слева передаётся
# в первый аргумент
TRUE |>
  sum(c(NA, 1:10), na.rm = _)

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

function(x) x + 1
# или
\(x) x + 1

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

# традиционный: присваиваем в переменную
succ <- \(x) x + 1
succ(1) == 2

# извращённый: вызываем на месте
(\(x) x + 1)(1)
(\(x) x + 1)(1) == 2

# стандартный: в аргументе функций высшего порядка
Map(\(x) x + 1, 1:10)

Что нужно знать про анонимные функции:

1. В отличие от того же Python, лямбды в R могут состоять из более чем одной строчки, если тело функции обернуть в фигурные скобки.

2. В тело функции можно запихать всё, что угодно. Можно плюнуть на функциональный подход и налепить там чтения с диска, запись в файл, логирование и прочие побочные эффекты, что противоречит подходу "чистых функций"

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

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

Функции возвращают функции

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

Map(\(x) \(df) kmeans(df, x), 1:6) %>% 
  Map(\(f) f(mtcars), .)

Здесь первая лямбда для каждого элемента вектора 1:10 возвращает функцию. Возвращаемая функция принимает в качестве аргумента датафрейм и применяет к нему метод k-средних с количеством центроидов, равных соответствующему значению элемента вектора 1:10. Ну а далее, чтобы не быть голословным, мы этот список функций отправим по конвейеру (уже из magrittr, он чуть более функциональный в общем плане) в следующее отображение, где применим эту функцию на датафрейм mtcars.

Функции, возвращающие функции, удобны для разработки. Написав вот так:

# Да, это классический вариант с add
add <- function(x, y) function(y) x + y

# > add(1)
# function(y) x + y
# <environment: 0x1544b09e8>

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

add(1)(2) == 3

Такая запись может быть даже проще читается, чем два подряд Map:

(\(df, n) \(n) kmeans(df, n))(mtcars) |>
  Map(f = _, 1:6)

Здесь мы объявляем лямбдой функцию от двух переменных df и n, передаём в первый аргумент значение mtcars и получаем функцию от одного аргумента. Её отправляем по конвейеру в Map, где получаем список результатов kmeans по на набору центроидов.

Сокращение количества аргументов путём последовательного возвращения функций от одного аргумента называется каррированием или каррингом по имени математика Хаскеля Карри.

Синтаксис с лямбдами может быть не очень понятен, особенно начинающим (хотя чем раньше начнёшь, тем быстрее научишься). Для этого существуют вспомогательные функции, например из пакета purrr, который является воплощением ФП в R (частичным).

library(purrr)

partial(kmeans, x = mtcars) %>% 
  map(1:6, .)

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

partial(kmeans, x = mtcars, centers = 5)()

Последняя на сегодня функция высшего порядка - compose из purrr. По сути это замена конвейера. Но если у вас есть стандартный набор шагов, используемый в разных частях кода, стоит подумать над заворачиваением его в compose.

sum_of_addition <- compose(`+`, sum)
sum_of_addition(1:10, 10:1)

Функция выше складывает два вектора поэлементно а затем результат суммирует.

Рекурсия

Говоря о ФП, невозможно обойти стороной рекурсию. Это довольно распространённый приём в преимущественно функциональных языках. Особенно в чистых, где вообще нет циклов и рекурсия является одним из немногих способов итерироваться (не считая функций высшего порядка). Концепцию рекурсии на курсе по Scala на курсере её создатель объясняет на втором уроке уже буквально. Я же этим блоком хочу сразу показать, что нельзя так огульно бросаться в ФП в R.

Итак, рекурсия - это обращение функции к самой себе. Это мощный и лаконичный приём, для понимания которого может понадобится время. Но как и всё мощное, надо к его использованию подходить с умом. Я приведу классические примеры с факториалом и вычислением n-ого элемента последовательности Фибоначчи.

straight_recursion_factorial <- function(n) {
  if (n <= 1) return(1)
  return(n * straight_recursion_factorial(n - 1))
}

# > straight_recursion_factorial(10)
# [1] 3628800

Здесь решение буквально в лоб. Факториал n равен факториалу (n-1) умноженному на n. Потому мы явно вызываем объявляемую функцию в её же теле. Давайте разберём это построчно

straight_recursion_factorial(10) == 10 * straight_recursion_factorial(9)
straight_recursion_factorial(9) == 9 * straight_recursion_factorial(8)
straight_recursion_factorial(8) == 8 * straight_recursion_factorial(7)
straight_recursion_factorial(7) == 7 * straight_recursion_factorial(6)
straight_recursion_factorial(6) == 6 * straight_recursion_factorial(5)
straight_recursion_factorial(5) == 5 * straight_recursion_factorial(4)
straight_recursion_factorial(4) == 4 * straight_recursion_factorial(3)
straight_recursion_factorial(3) == 3 * straight_recursion_factorial(2)
straight_recursion_factorial(2) == 2 * straight_recursion_factorial(1)
straight_recursion_factorial(1) == 1

В последней строчке срабатывает условие if (n <= 1) return(1), потому значение нашей функции равно 1. Это значение подставляется в формулу вычисления факториала от 2, его результат отправляется в формулу для 3 и так далее до 10. Условие для вычисления результата функции от единицы (и меньше) называется выходом из рекурсии. Без него она была бы бесконечной и никогда не разрешилась бы.

Тоже самое, но с подстановкой значений (β-редукция для следующего чтения)

straight_recursion_factorial(10) == 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
straight_recursion_factorial(9) == 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
straight_recursion_factorial(8) == 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
straight_recursion_factorial(7) == 7 * 6 * 5 * 4 * 3 * 2 * 1
straight_recursion_factorial(6) == 6 * 5 * 4 * 3 * 2 * 1
straight_recursion_factorial(5) == 5 * 4 * 3 * 2 * 1
straight_recursion_factorial(4) == 4 * 3 * 2 * 1
straight_recursion_factorial(3) == 3 * 2 * 1
straight_recursion_factorial(2) == 2 * 1
straight_recursion_factorial(1) == 1

Здесь сразу видно слабое место такой рекурсии: с увеличением n растёт и количество необходимых ресурсов для вычисления, потому что все промежуточные состояния до выхода из рекурсии заносятся в стек вызовов. И он вполне может переполниться

> straight_recursion_factorial(10000)
Error: C stack usage  7954120 is too close to the limit

Для оптимизации рекурсии есть вариант написать "хвостовую рекурсию". Его главное отличие - возвращается последний вызов рекурсивной функции, а не первый. Что может заметно ускорить выполнение и затребовать меньше памяти. А в функциональных языках такая рекурсия компилятором или интерпретатором преобразуется в итерацию, что избавляет от проблемы переполненного стека вызовов. К сожалению, R так не умеет, хотя это не означает, что не надо пытаться оптимизирвоать свою рекурсивную функцию.

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

tail_recursion_factorial <- function(n, total = 1) {
  if (n <= 1) return(total)
  tail_recursion_factorial(n - 1, total = n * total)
}

Попробуем вызвать эту функцию и применить редукцию.

tail_recursion_factorial(n = 5, total = 1) == 
	tail_recursion_factorial(n = 4, total = 5 * 1)
tail_recursion_factorial(n = 4, total = 5 * 1) == 
	tail_recursion_factorial(n = 3, total = 4 * 5 * 1)
tail_recursion_factorial(n = 3, total = 4 * 5 * 1) == 
	tail_recursion_factorial(n = 2, total = 3 * 4 * 5 * 1)
	tail_recursion_factorial(n = 2, total = 3 * 4 * 5 * 1) == tail_recursion_factorial(n = 1, total = 2 * 3 * 4 * 5 * 1)
tail_recursion_factorial(n = 1, total = 2 * 3 * 4 * 5 * 1) == 
	2 * 3 * 4 * 5 * 1

Здесь мы видим, что при каждом вызове значение total умножалось на соответствующее n и к последнему вызову, когда происходит выход из рекурсии, проходить обратно по всему стеку для вычисления значения не надо, total уже весь посчитан, остаётся его вернуть. Тем не менее интерпретатор должен умень с этим работать и не забивать стек. В R это не так и это можно увидеть на бенчмарках двух факториалов (прямого и хвостового)

Здесь хвостовая рекурсия по времени выполнения даже хуже обычной. Но есть и обратные примеры. Напишем функцию вычисления n-ого элемента последовательности Фибоначчи. Считаем что первый и второй элементы последовательности равны одному.

straight_recursion_fibonacci <- function(n) {
  if (n <= 2) return(1)
  return(
    straight_recursion_fibonacci(n - 1) + straight_recursion_fibonacci(n - 2)
  )
}

tail_recursion_fibonacci <- function(n, prev = 1, prev_prev = 1) {
  if(n <= 2) return(prev)
  tail_recursion_fibonacci(n - 1, prev = prev + prev_prev, prev_prev = prev)
}

А вот здесь разница огромная. Скорость вычисления в хвостовом варианте выше примерно в 3 раза. И это даже без оптимизации интерпретатором.

Рекурсия - сложная концепция, но позволяет писать простой и понятный код. Описать рекурсию можно меметичной фразой "сводим задачу к предыдущей". Хотя вариант с хвостовой рекурсией последовательнсоти Фибоначчи всё равно не самый очевидный.

Однако на практике почти всегда рекурсию можно заменить функциями высшего порядка. Я могу привести только один реальный пример, когда можно использовать рекурсию вместо цикла и невозможно использовать map или reduce. Я говорю о расчёте размера вклада после определённого периода с извлечением фиксированной суммы каждый месяц. Или с депозитом фиксированной суммы каждый месяц.

# рекурсивный вызов
recursive_dep <- function(n, deposit, percent, withdrawal) {
  if(n == 0) return(deposit)
  dep(n - 1, deposit = deposit * (1 + percent / 12) - withdrawal, percent, withdrawal)
}

# рекурсивный вызов
loop_dep <- function(n, deposit, percent, withdrawal) {
  for (i in seq_len(n)) {
    deposit <- deposit * (1 + percent / 12) - withdrawal
  }
  deposit
}

Кстати, рекурсия сходу получается хвостовой (у нас накапливается deposit).

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

Выводы

R не чистый функциональный язык. Он таковым и не задумывался. Однако это язык высокого уровня абстракции для профессионалов по работе с данными и статистиков. У таких специалистов иногда бывают сложности с пониманием устройства памяти и стандартных императивных алгоритмов. И именно для этого в R есть много элементов ФП. Нам буквально говорят: "Используйте декларативный стиль, пишите что нужно сделать, а не как. А интерпретатор позаботится о деталях."

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

В завершение хочу пригласить вас на бесплатный вебинар, который предназначен для всех, кто интересуется использованием R в своей работе с данными. В ходе вебинара вы познакомитесь с тремя популярными средствами разработки и анализа данных, которые помогут стать более продуктивным и эффективным при работе с R: Rstudio, Jupyter, VSCode.

• Зарегистрироваться на бесплатный вебинар