Всем привет,
Прочитав недавнее обсуждение по поводу PHP, обнаружилось, что много людей боятся рекурсии как огня. Таковой миф нужно разоблачить!
Сегодня мы обоснуем, почему циклы это плохо, и почему их надо замочеть. В процессе мы будем пейсать на православном языке Хаскель, который очень непонятен. Вас предупредили!
Итак, что же такое цикл «for»?
А что тут плохого, спросит фтыкатель? Перечислим те штуки, которые с циклом делать нельзя:
Цикл не помогает вводить новые понятия в программу, потому что цикл сам по себе никакого смысла не имеет (ну напишешь ты
Цикл также смешивает по сути разные операции (фильтрация, отображение, свертка, и наверное, много чего еще), выражая их неявно, из-за чего получаем вкусный спагетти-код. Было бы круто записать указанные операции явно, чтобы получить возможность свободно комбинировать их, не повторяя себя лишний раз.
Какова же альтернатива? Ну конечно же божественная рекурсия! Она, во-первых, проще, а во-вторых, помогает вводить те самые понятия.
Начнем с простого. У нас есть список (пусть даже массив), и мы хотим посчитать сумму его элементов.
Посмотрим на обычное решение этой проблемы ©:
А теперь — примерно оно же, но в Хаскеле:
Функция foldr определяется как рекурсивный процесс:
Разница заметна невооруженным взглядом. Код на Хаскеле проще, понятней, и, как ни странно, может использоваться для того, чтобы получить новые функции, в которых будут учитываться дополнительные условия!
Например, мы внезапно решили сложить только четные числа нашего списка.
C, обычное решение — копипастим старую функцию, добавляем условие:
А теперь на Хаскеле:
Никакой копипасты, мы просто отбрасываем все элементы списка, которые не удовлетворяют предикату even, и применяем к этому списку функцию sum.
Вот примерно так, используя функции высшего порядка и рекурсию, мы радикально сокращаем количество кода. Таковые сокращения не могут не сказаться положительно на нашем психическом и «пальцевом» здоровье. %)
А циклы таки не нужны. :)
UPD: правка (JS -> C), замечания (спасибо tass и voicer)
Прочитав недавнее обсуждение по поводу 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)