Рекурсия, оптимизация хвостового вызова и каррирование

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

(Правка: изначально я начал писать этот пост с намерением составить исчерпывающий список известных мне «методов функционального программирования». С тех пор я занимался реальным™функциональным программированием. , и для меня становится все более очевидным, что функциональное программирование — это плотная парадигма, а его «методы» — просто побочные продукты основных ценностей, которые оно продвигает. Тем не менее, это, вероятно, хорошее вводное чтение для новичка, знакомого с процедурным программированием. )

Есть много методов, заимствованных из функционального программирования, которые действительно могли бы добавить к обычному репертуару трюков программиста. Эти методы не достигают широкой аудитории, потому что их часто можно найти в академической литературе или среди сообществ менее распространенных языков, таких как Lisp, Haskell и т. д. Здесь я объясню некоторые из них, используя два популярных языка: Python и JavaScript. Мы не будем обсуждать многие технические аспекты, но посмотрим, как они пригодятся.

При написании этой статьи мне стало ясно, что должен быть отдельный раздел Почему функциональное программирование? статья. Я не буду этого писать. Если вам интересно, Google — ваш друг. Я бы порекомендовал статью Out of the Tarpit — одну из классических.

Несколько замечаний, прежде чем мы начнем

Мы собираемся обсудить «парадигмы программирования», которые не являются «кодом», то есть они не являются конкретными реализациями концепции на конкретном языке программирования. Эти методы не зависят от какого-либо языка программирования. Однако это означает, что некоторые методы нельзя использовать в некоторых языках из-за особенностей реализации этого языка.

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

Рекурсия против итерации

Вы, наверное, думаете: «Эй, это не концепция функционального программирования. Это базовые вещи».

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

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

Вы, наверное, думаете: «Но ведь это невозможно! Как можно избежать объявления глобальных переменных?»

Ну, кажется, есть масса способов сделать это. Например, рекурсия.

Если вы не можете объявить переменную, то как реализовать цикл? Использование счетчика циклов включает в себя состояние — так как же обойти это? Рекурсия, конечно.

Возьмем пример на Javascript [поскольку в Python это не так очевидно]:

var n = 10;
var ans = 1;
for (i = 1; i <= n; i++) {
    ans = i * ans;
}
console.log(ans);

Теперь это простой фрагмент кода, который находит значение n! (n-факториал, т. е. 3! = 3 x 2 x 1). Как бы вы сделали это рекурсивно, не объявляя переменную-счетчик i?

function factorial(n) {
    if (n != 0) {
        return n * factorial(n-1);
    }
    
    else {
        return 1;
    }
}
factorial(10);

Ясно, что мы достигли того же результата без объявления переменных. А теперь слово предостережения — подождите, мы рассмотрим это в следующем разделе.

Оптимизация хвостового вызова

Я намеренно выбрал приведенный выше пример с факториалом, чтобы продемонстрировать оптимизацию хвостового вызова. Когда вы используете рекурсивное решение для нахождения факториала действительно большого числа n, вы можете обнаружить, что вашей системе не хватает памяти. Это совершенно очевидно из функции, потому что фактическое умножение откладывается до тех пор, пока все значения не будут получены предложением возврата. Например, для 10!: 10*factorial(9) расширяется до 10*9*factorial(8) и так далее — все числа до 1 должны быть получены, прежде чем это можно будет умножить.

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

Вот версия приведенного выше рекурсивного решения, оптимизированная для хвостового вызова [обратите внимание, что язык должен поддерживать это — JS ES2015+ поддерживает, а Python — нет]:

function factorial (n) {
    function fact(num, acc) {
        if (n < 2) {
            return acc;
        } 
        else {
            return fact(n-1, n * acc);
        }
    }

    return fact(n, 1);
}

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

карри

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

Каррирование в простейшей форме — это просто замена функции f(a,b,c), которая принимает 3 переменные (a, b и c), на функцию g(a)(b)(c). Чего-чего? Вот пример на Python:

> def f(a,b,c):
      return a + b + c
> f(1,2,3)
6

можно заменить на:

> def g(a):
      def g1(b):
          def g2(c):
              return a + b + c
          return g2
      return g1
> g(1)(2)(3)
6

Не понятно, как это произошло? Возможно, это поможет:

> g(1)
<function g1 at 0x1007f7230>
> g(1)(2)
<function g2 at 0x1007f7410>
> g(1)(2)(3)
6

Из приведенного выше фрагмента кода должно быть ясно одно: вызов g(1) генерирует функцию, как и g(1)(2), которая дает окончательную функцию g2 в цепочке. Когда эта функция вызывается, мы получаем результат 6.

Так чем же это полезно, спросите вы?

Каррирование позволяет вам «настраивать» функции, оборачивая их в еще более общие функции — т. е. получать специализированные функции из более общих функций.

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

Возьмем пример:

> def g(function1):
      def g1(list):
          def g2(key):
              return a(b[c])
          return g2
      return g1
> g(round)(listofnumbers)(3)

Вы только посмотрите, как это можно использовать повторно: вы применяете функцию round к элементам в списке с именем listofnumbersс ключом 3. Вы можете изменить все это — вы можете изменить функцию, список и ключ. Это означает, что вам не нужно кодировать его снова, если вы хотите использовать другую функцию или другой список. Если вы используете это с функцией карты, возможности безграничны!