Всем привет,

Прочитав недавнее обсуждение по поводу PHP, обнаружилось, что много людей боятся рекурсии как огня. Таковой миф нужно разоблачить!

Сегодня мы обоснуем, почему циклы это плохо, и почему их надо замочеть. В процессе мы будем пейсать на православном языке Хаскель, который очень непонятен. Вас предупредили!



Итак, что же такое цикл «for»?
  • это «оператор» (а точнее, инструкция, statement), которая позволяет изменить поток управления программы
  • это синтаксическая абстракция
  • это замаскированный goto, которые суть зло (Дейкстра доказал уже в своем труде «Goto considered harmful», ЕМНИП)
  • это еще один способ «повторить себя»


А что тут плохого, спросит фтыкатель? Перечислим те штуки, которые с циклом делать нельзя:
  • передавать в функции в качестве аргументов и возвращать из других функций
  • строить с помощью них другие циклы


Цикл не помогает вводить новые понятия в программу, потому что цикл сам по себе никакого смысла не имеет (ну напишешь ты for (int i = 0; i < 10; i++); и чего?), а только помогает немного сберечь пальцы (ведь он разворачивается в инструкции, вовлекающие goto).

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

Какова же альтернатива? Ну конечно же божественная рекурсия! Она, во-первых, проще, а во-вторых, помогает вводить те самые понятия.

Начнем с простого. У нас есть список (пусть даже массив), и мы хотим посчитать сумму его элементов.

Посмотрим на обычное решение этой проблемы ©:

int sum(int *a, size_t length) {
    int x = 0;
    size_t i = 0;
    for (; i < length; i++) {
        x += a[i];
    }
    return x;
}


А теперь — примерно оно же, но в Хаскеле:

-- надо заметить, что эта функция уже определена в "стандартной библиотеке"
sum = foldr (+) 0


Функция foldr определяется как рекурсивный процесс:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)


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

Например, мы внезапно решили сложить только четные числа нашего списка.

C, обычное решение — копипастим старую функцию, добавляем условие:

int sumEven(int *a, size_t length) {
    int x = 0;
    size_t i = 0;
    for (; i < length; i++) {
        if (a[i] % 2 == 0)
            x += a[i];
    }
    return x;
}


А теперь на Хаскеле:

-- эта функция уже определена в "стандартной библиотеке",
-- но повторение это мать учения :)
even x = x `mod` 2 == 0
sumEven = sum . filter even


Никакой копипасты, мы просто отбрасываем все элементы списка, которые не удовлетворяют предикату even, и применяем к этому списку функцию sum.

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

А циклы таки не нужны. :)

Примечания



  • Большое количество взаимно-рекурсивных функций конечно же, сложно понять. Поэтому тут надо быть осторожным, и все делать в меру. Вообще-то, в функциональных языках обычно присутствуют средства абстракции, достаточно мощные для того, чтобы убрать (или, точнее, снизить) сложность для восприятия.
  • В некоторых особо распространенных языках программирования этот подход неприменим, но это недостатки этих языков, а не подхода. :)
  • Не следует боятся того, что функция foldr съесть весь стек, потому что ее можно переписать в итеративный процесс, определенный рекурсивно.
  • Более подробно (с объяснениями, как же оно работает), можно почитать в блоге Adam Turoff


UPD: правка (JS -> C), замечания (спасибо tass и voicer)