В первой части этой серии мы рассмотрели основы функционального программирования и подробно ознакомились с неизменяемым кодом и кодом без побочных эффектов. Во второй части мы изучили концепции функций и карри высшего порядка, а также множество маскировок для анонимных функций в Ruby.
В этой заключительной части серии мы собираемся исследовать рекурсию и лень в Ruby и посмотреть, как вы можете применить эти основные принципы функционального программирования к своему повседневному коду.
Ruby’s много петель
Скорее всего, если вы больше, чем новичок в программировании, вы будете знакомы со старым добрым циклом. Концепция зацикливания появляется в большинстве книг по программированию на ранних этапах, и на то есть веская причина: повторение инструкций заданное число раз является фундаментальным принципом эффективного кодирования. Давным-давно, скромное и часто оскорбленное выражение goto служило этой цели, но в конечном итоге ключевые слова языка, такие как for и в while заменили большинство других форм зацикливания, гибкость торговли для краткости.
В Ruby есть много разных типов циклов, которые вы можете использовать:
-
for i in range do; ...; end -
n.times do; ...; end -
i.upto(j) do; ...; end
Есть много других (включая странные идиомы для достижения циклов while и скрытые переходы ).
В функциональном программировании, однако, подобное зацикливание неслыханно; это главным образом потому, что функциональное программирование хочет, чтобы вы указали ему, что делать, а не как это делать . В результате цикл заменяется двумя очень мощными концепциями:
- складки (в частности, левые и правые складки)
- функциональная рекурсия
Конечно же, мы уже рассмотрели сгибы в первой части этой серии , поэтому давайте рассмотрим функциональную рекурсию более подробно.
Называть себя
Функциональная рекурсия — это имя, данное процессу написания функции, которая вызывает себя. Это обычный способ в функциональном программировании заменить потребность в стандартных императивных циклах стиля. Он работает с помощью функции, передающей новые аргументы себе для имитации итерации и возвращающей, когда эти аргументы достигают некоторого порогового значения.
Пример приведен в порядок, давайте пропустим традиционную жертву примеров рекурсии, чисел Фибоначчи, и вместо этого напишем функцию для вычисления факториалов :
def fact(n) return 1 if (0..1).include?(n) n * fact(n - 1) end
Если считать 6! или 6 факториал, ответ будет 6 * 5 * 4 * 3 * 2 * 1 или 720 ; вышеприведенная функция получит тот же ответ, выполнив:
fact(6) = 6 * fact(5) = 6 * 5 * fact(4) = 6 * 5 * 4 * fact(3) = 6 * 5 * 4 * 3 * fact(2) = 6 * 5 * 4 * 3 * 2 * fact(1) = 6 * 5 * 4 * 3 * 2 * 1 = 720
Подумайте, насколько лаконичен этот код, особенно по сравнению с традиционным циклом. Вариант цикла в конечном итоге выглядел бы примерно так:
def fact(n) factorial = 1 begin factorial *= n-- end while n > 1 factorial end
Этот пример использования циклов несет очевидный багаж обновления состояния цикла, но также страдает с точки зрения краткости и читабельности.
К сожалению, предостережение во всем этом заключается в том, что в Ruby по умолчанию отсутствует поддержка оптимизации хвостовых вызовов . Это означает, что функциональная рекурсия, которую мы использовали для реализации нашего факториального метода, в конечном итоге разрушит стек. Вы можете перекомпилировать Ruby 1.9.x так, чтобы была выполнена оптимизация хвостового вызова , хотя вы должны быть осторожны, чтобы проверить, включена ли эта функция, и выдать подходящую ошибку времени выполнения, если ваш код запускается на альтернативной установке Ruby и зависит от хвоста оптимизация вызова на работу.
Перечислители: генераторы Руби
Что если бы у вас была возможность рекурсии, не беспокоясь об оптимизации хвостовой рекурсии и компиляции пользовательских версий Ruby?
Во многих языках существует концепция генераторов, которая может быть описана как сочетание между итераторами или циклами и функциональной рекурсией. В Ruby генераторы называются «счетчиками».
Руби на самом деле пытается заставить вас использовать перечислители для большинства форм циклов, за исключением того, что я использовал выше ( begin; ...; end while ... ). Все это время, когда вы были заняты использованием #each , вы фактически использовали перечислитель. Доказательство:
puts = [1, 2, 3].each.class # => Enumerator
Перечислители или генераторы основаны на идее, что циклы можно сделать еще более мощными, если функция выполняется для каждой итерации цикла, а пошаговое выполнение цикла можно контролировать с помощью кода.
В Ruby вы можете выполнять внешние итерации и самостоятельно управлять циклом в любом экземпляре класса Enumerator :
x = [1, 2, 3] enum = x.each puts enum.class # => Enumerator puts enum.next # => 1 puts enum.next # => 2 puts enum.next # => 3 puts enum.next # => StopIteration exception
Вы также можете написать собственные счетчики. Это очень мощный инструмент, позволяющий превратить любой старый класс в класс, который можно перебирать. Это делается путем включения модуля Enumerable в класс и определения each метода, который возвращает один раз для каждого итерируемого значения.
Модуль Enumerable определяет невероятное количество методов, которые вы, вероятно, используете каждый день; Вот некоторые из наиболее популярных:
-
#any? -
#all? -
#find -
#inject -
#select -
#take
Эти методы и все остальные элементы, определенные как часть модуля Enumerable , определяются в терминах метода #each который вы определяете в классе, включая этот модуль. Одно это должно продемонстрировать значительную силу счетчиков.
Вот наша предыдущая императивная циклическая функция в стиле цикла, переписанная с использованием Enumerable функций:
def fact(n) (1..n).inject(:*) || 1 end
Это потрясающе. Это, возможно, более читабельно, чем наша оригинальная функциональная рекурсивная версия, и намного короче. Это также хорошо согласуется с функциональным стилем: нет переменных для сохранения состояния, и код говорит Ruby, что делать , а не как это делать .
Перечислители являются решением большинства проблем циклирования в Ruby, но есть одно ограничение, которое они налагают. Допустим, у нас был класс, который мог бесконечно генерировать список простых чисел. Для одного приложения мы хотели найти первые 20 простых чисел где-то с цифрой «3», а для другого приложения мы хотели найти первые 10 простых чисел, где сумма цифр была также простым числом. Написание их со стандартными Enumerable функциями было бы совсем нехорошо, если не невозможно. Введите ленивые счетчики.
Ленивые Счетчики
В функциональных языках, таких как Haskell, отложенная оценка — это функция, используемая для принудительной оценки значений только при необходимости. В Haskell совершенно справедливо иметь бесконечные списки, лежащие в коде, используя только столько списков, сколько необходимо в любой момент времени. На языках строгой оценки, таких как Ruby, это невозможно. Ruby попытается вычислить весь бесконечный список, в конечном итоге запустив память.
Новым в грядущем Ruby 2.0 является совершенно новый класс Enumerator::Lazy который позволяет ленивым вычислениям перечислителей. Это означает, что бесконечные списки данных теперь также легко возможны в Ruby.
Давайте вернемся к нашему главному примеру на минуту. Предполагая, что у нас есть класс Prime который является перечислителем, который будет генерировать бесконечный поток простых чисел, вот решение для обеих наших предыдущих задач:
Prime.lazy.select { |x| x.to_s.include?('3') }.take(20).to_a Prime.lazy.select { |x| 100.to_s.chars.map(&:to_i).inject(:+) }.take(20).to_a
Реализация такого краткого и удобочитаемого кода без использования ленивого перечислителя была бы непростой задачей. Это альтернатива первому примеру ленивого перечислителя:
a = [] Prime.each do |x| next unless x.to_s.include?('3') a << x break if a.size == 20 end
Это в значительной степени противоположно функциональному программированию: переменная, используемая для состояния, и управление циклами повсеместно. Этот код больше рассказывает Ruby, как делать то, что мы хотим ; Сравните это с нашим ленивым примером, который говорит Руби, что мы хотим . Это основная сущность функционального программирования.
Есть еще одно огромное преимущество ленивой оценки. Посмотрите на этот код:
(1..100).select { |x| x % 3 == 0 }.select { |x| x % 4 == 0 }
Этот код пытается найти все числа от 1 до 100, которые делятся на 3 и 4, но в процессе повторяет набор чисел дважды ! Ленивая оценка объединяет все действия перечислителя в одну итерацию:
(1..100).lazy.select { |x| x % 3 == 0 }.select { |x| x % 4 == 0 }.to_a
Это может значительно ускорить код, когда к коллекции применяется несколько фильтров. Такое свертывание перечислимой цепочки работает для любого из множества методов, определенных в классе Enumerable , включая, но не ограничиваясь, #select , #map и #take .
В настоящее время Enumerator::Lazy работает очень медленно, поскольку затраты на создание и вызов свернутого блока очень дороги ; есть исправление, чтобы исправить это, поэтому весьма вероятно, что финальная версия Ruby 2.0 будет иметь более быструю версию ленивого перечислителя по сравнению с текущей реализацией в магистральном Ruby.
Применение этих уроков к реальному миру
Написание Ruby в функциональном стиле не сводится к написанию симпатичных строк, которые не используют переменные. Разумеется, речь идет не об использовании скрытых возможностей Ruby, чтобы просто сохранить функциональность. Речь идет о написании чистого, поддерживаемого кода.
Первая часть этой серии посвящена неизменности. Код реального мира должен будет управлять состоянием в определенное время. Тем не менее, мы рассмотрели реальный пример создания генератора CSS, который имеет хороший DSL, является цепным и полностью функциональным; это шаблон, который вы можете применить ко многим проблемам, в результате чего получается чистый и легко тестируемый код. Фактически, вы, вероятно, найдете такие шаблоны уже в дикой природе, потому что они так необходимы для создания беглых DSL.
Во второй части этой серии были рассмотрены функции высшего порядка и карри. Это два принципа, которые можно использовать в вашем коде начиная с сегодняшнего дня. Вы можете использовать функции более высокого порядка, чтобы упростить как код, так и тесты, а каррирование можно использовать для предоставления более полезных DSL в вашем приложении или библиотеке без багажа кода, который обычно поставляется вместе с ним.
Эта последняя статья, третья часть, посвящена рекурсии и лени. Вы можете использовать рекурсию сегодня в форме Enumerator и Enumerable , и, безусловно, вы найдете множество классов в дикой природе, использующих более поздний миксин. Laziness — это новая функция, которая дебютирует в Ruby 2.0, но вы, возможно, захотите сразу начать думать об использовании, потому что она очень полезна.
Тем не менее, главное в этой серии было не столько о строгих примерах кода, сколько о том, как лучше узнать принципы, лежащие в основе вашего повседневного кода. Конечно, более производительный и более эффективный программист — это тот, кто понимает инструменты в его распоряжении. Этот программист использует только инструменты, необходимые в то время, когда они действительно необходимы. Функциональное программирование — это упражнение в минимальном кодировании, достижении максимально эффективного, но в то же время лаконичного кода и повышении читабельности, позволяя языку работать на вас. То, что Ruby предоставляет так много способов сделать это, очень интересно. Как сообщество, мы должны использовать эти замечательные инструменты как можно лучше.
Удачи, функциональные рубисты!