Функциональное программирование на Ruby. Часть 3

В третьей части рассмотрим рекурсию и ленивые вычисления в Ruby.
Циклы в Ruby
Повторяемые операции — основной принцип эффективного кода. В руби есть несколько типов циклов:
for i in range do
...
endn.times do
...
endi.upto j do
...
end
В функциональном программировании вы говорите программе что делать, а не как делать, поэтому циклы заменяются на:
- свертку
- рекурсию
Свертка — ФВП, которая преобразует структуру данных, например список, к единственному атомарному значению при помощи заданной функции. Применение методов #reduce и #inject в Ruby можно расценивать как свертку.
Вызов себя
Рекурсие называется вызов функции из самой себя. Суть рекурсии в том, чтобы передавать в саму себя новые аргументы имитируя итерации. Рекурсивная функция как правило имеет 2 ветви: рекурсивную и терминальную:
Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов.
Терминальная ветвь выполняется, когда срабатывает условие выхода из рекурсии.
Для примера рассмотрим функцию вычисления факториала:
def fact(n)
return 1 if n <= 1
n * fact(n-1)
endВычисление 5! породит стек вызовов функции fact
fact(5) = 5 * fact(4)
= 5 * 4 * fact(3)
= 5 * 4 * 3 * fact(2)
= 5 * 4 * 3 * 2 * fact(1)
= 5 * 4 * 3 * 2 * 1
= 120Перечислительный тип в Ruby
В Ruby есть специальный класс, который представляет собой смесь операторов, циклов и рекурсии — Enumerator.
Enumerator используется в руби вместо циклов. С помощью этого класса можно управлять циклом на каждой итерации:
cats = ['spots', 'shadow', 'ginger']
enum = cats.eachenum.next
=> 'spots'enum.next
=> 'shadow'enum.next
=> 'ginger'enum.next
=> StopIteration exception
Можно создавать свои перечисляемые типы. Для этого надо подмешать модуль Enumerable в свой класс.
Модуль Enumerable содержит много полезных методов, вот самые популярные:
- any?
- all?
- find
- inject
- select
- take
- each
Перепишем функцию факториала с помощью Enumerable. Функция будет лаконичнее и понятнее:
def fact(n)
(1..n).inject(:*) || 1
endПеречисляемы типы в Ruby заменяют стандартные циклы. Но представим ситуацию, когда у нас есть класс, который генерирует бесконечный список простых чисел. Например, с помощью этого класса мы можем сгенерировать список из 10 простых чисел, содержащих цифру 7.
В таком случае нам помогут ленивые (отложенные) вычисления.
Ленивые вычисления
В функциональных языках вроде Хаскелля используются ленивые вычисления. Они позволяют создавать бесконечные списки и получать из них сколько нам нужно значений.
В языках вроде Ruby создание бесконечного списка приведет к тому, что у нас кончится память.
В Ruby есть класс Enumerator::Lazy, реализующий ленивые вычисления для коллекций.
Например, у нас есть класс Prime, генерирующий простые числа:
Prime.lazy.select { |x| x.to_s.include?('7') }.take(10).to_aНапишем тоже самое без использования отоженных вычислений:
arr = []
Prime.each do |x|
next unless x.to_s.include?('7')
arr << x
break if arr.size == 10
endКод получился более многословным. К тому же он описывает как получить результат, а функционально-ленивый что мы хотим получить.
Рассмотрим еще один пример:
(1..100).select { |x| x % 3 == 0 }.select { |x| x % 5 == 0 }Этот код находит все числа в диапазоне от 1 до 100, которые делятся на 3 и на 5, но при этом перебирает массив дважды.
При ленивых вычислениях мы пройдем по массиву только один раз:
(1..100).lazy.select { |x| x % 3 == 0 }.select { |x| x % 5 == 0 }.to_aТакой подход позволяет ускорить код, в котором несколько фильтров применяются к коллекции.
Функциональный подход в Ruby
Чтобы писать в фукнциональном стиле не обязательно писать функции-однострочники или применять экзотические возможности языка. Функциональный подход позволяет писать чистый код, который легко тестировать и поддерживать.
В части 1 мы рассмотрели неизменяемость данных. Часто в реальных проектах нам нужно управлять состоянием приложения. Мы написали генератор CSS с понятным DSL, в функциональном стиле, который легко тестировать за счет неизменяемости состояния.
В части 2 мы познакомились с ФВП и каррированием. ФВП упрощают наш код и его тестирование, а каррирование помогает организовать удобный DSL в нашем приложении.
В этой части мы рассмотрели рекурсию и ленивые вычисления. Для посторения рекурсии в Ruby можно использовать перечисляемы тип Enumerator и методы модуля Enumerable. Правильное применение отложенных вычислений может уменьшить потребление памяти и повысить скорость программ за счет уменьшения числа итераций по коллекциям.
