Элементы функционального программирования в R

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

Всем привет. Меня зовут Дмитрий Володин, я 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.

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