Почему циклы должны умереть

Всем привет,

Прочитав недавнее обсуждение по поводу 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)