Автор статьи: Дмитрий Володин
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)Что нужно знать про анонимные функции:
В отличие от того же Python, лямбды в R могут состоять из более чем одной строчки, если тело функции обернуть в фигурные скобки.
В тело функции можно запихать всё, что угодно. Можно плюнуть на функциональный подход и налепить там чтения с диска, запись в файл, логирование и прочие побочные эффекты, что противоречит подходу "чистых функций"
Но делать я так крайне не советую, лучше всё-таки функцию объявить заранее и использовать её к месту. Так вы возможно ещё и познаете прелести 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.
mordoorg
Отличная статья, при этом и не поверхностная и не дебри. Года 3 так назад, при начале освоения мною R очень помогла бы, ну а так, спасибо что много что напомнили из функций :)