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

asqd
asqd
Aug 23, 2017 · 3 min read

В третьей части рассмотрим рекурсию и ленивые вычисления в Ruby.

Циклы в Ruby

Повторяемые операции — основной принцип эффективного кода. В руби есть несколько типов циклов:

for i in range do
...
end
n.times do
...
end
i.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.each
enum.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. Правильное применение отложенных вычислений может уменьшить потребление памяти и повысить скорость программ за счет уменьшения числа итераций по коллекциям.

)
asqd

Written by

asqd

実は私は猫です。

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade