In part one of this series, we looked looked at the basics of functional programming and visited, in detail, immutability and side-effect free code. In part two, we explored the concepts of higher-order functions and currying, as well as the myriad of disguises for anonymous functions in Ruby.
In this final part of the series, we’re going to investigate recursion and laziness in Ruby, and see just how you can apply these staples of functional programming to your everyday code.
Ruby’s Many Loops
Chances are, if you’re more than a beginner at programming, you’ll be familiar with the good old fashioned loop. The concept of looping appears early in most programming books, and with good reason: repeating instructions a given number of times is a fundamental principle of efficient coding. Once upon a time, the humble and oft-abused goto statement served this purpose, but eventually language keywords like for and while replaced most other forms of looping, trading flexibility for conciseness.
Ruby has a many different types of loops that you can dabble with:
for i in range do; ...; endn.times do; ...; endi.upto(j) do; ...; end
There are many others (including strange idioms to achieve while loops, and hidden goto’s).
In functional programming however, looping like this is unheard of; this is mainly because functional programming wants you to tell it what to do instead of how to do it. As a result of this, looping is replaced by two very powerful concepts:
- folds (specifically, left folds and right folds)
- functional recursion
Now of course, we already covered folds way back in part one of this series, so let’s look at functional recursion in more detail.
Calling Yourself
Functional recursion is the name given to the process of writing a function that calls itself. This is a common way in functional programming to replace the need for standard imperative style loops. It works by a function passing new arguments to itself to simulate an iteration, and returning when these arguments reach some threshold value.
An example being in order, let’s skip the traditional victim of recursion examples, Fibonacci numbers, and instead write a function to calculate factorials:
def fact(n)
return 1 if (0..1).include?(n)
n * fact(n - 1)
endIf one was to calculate 6!, or 6 factorial, the answer would be 6 * 5 * 4 * 3 * 2 * 1, or 720; the function above will arrive at the same answer by executing:
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
= 720Think about how concise this code is, especially in comparison to a traditional loop. The loop variant would have ended up looking something like this:
def fact(n)
factorial = 1
begin
factorial *= n--
end while n > 1
factorial
endThis example using looping carries the obvious baggage of keeping the loop state updated, but also suffers in terms of conciseness and readability.
Unfortunately, the caveat to all of this is that Ruby lacks support for tail call optimisation by default. This means that the functional recursion that we used to implement our factorial method will eventually blow the stack. You can recompile Ruby 1.9.x such that tail call optimisation is performed, though you should be careful to check whether the feature is enabled and throw a suitable run-time error should your code be run on an alternate installation of Ruby and depend on tail-call optimisation to work.
Enumerators: Ruby’s Generators
What if you could have the power of recursion, without worrying about tail recursion optimisation and compiling custom versions of Ruby?
In many languages, there is the concept of generators, which can be described as a mix between iterators, or loops, and functional recursion. In Ruby, generators are called “enumerators”.
Ruby actually tries to force you to use enumerators for most of the forms of looping, a notable exception being the one I used above (begin; ...; end while ...). All this time, when you were busy using #each, you were actually using an enumerator. Proof:
puts = [1, 2, 3].each.class # => EnumeratorEnumerators, or generators, are based on the idea that loops can be made even more powerful if a function is executed for each iteration of the loop, and step-by-step execution of the loop can be controlled using code.
In Ruby, you can iterate externally and manage the loop yourself on any instance of the Enumerator class:
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 exceptionYou can also write custom enumerators. These are immensely powerful, allowing you to turn any old class into a class that can be iterated over. This is done by including the Enumerable module into a class and defining an each method that yields once for each value to be iterated over.
The Enumerable module defines an incredible amount of methods you likely use everyday; some of the more popular ones include:
#any?#all?#find#inject#select#take
These methods, and indeed all the rest defined as part of the Enumerable module are defined in terms of the #each method you define on the class including this module. This alone should showcase the considerable power of enumerators.
Here is our previous imperative looping style factorial function rewritten using Enumerable functions:
def fact(n)
(1..n).inject(:*) || 1
endThis is amazing. This is arguably more readable than our original functional recursion version, and is much shorter. It also fits well with the functional style: no variables to keep state, and the code is telling Ruby what to do, not how to do it.
Enumerators are the solution for most of Ruby’s looping problems, but there is one limitation they impose. Let’s say we had a class that could generate a list of prime numbers infinitely. For one application, we wanted to find the first 20 prime numbers with the digit “3” in it somewhere, and for another application we wanted to find the first 10 prime numbers where the sum of the digits was also a prime. Writing these with standard Enumerable functions would not be very nice at all, if not impossible. Enter lazy enumerators.
Lazy Enumerators
In functional languages like Haskell, lazy evaluation is a feature used to force evaluation of values only as needed. In Haskell, it is perfectly valid to have infinite lists lying around throughout the code, using only as much of these lists as is needed at any given time. In strict evaluation languages like Ruby, this isn’t possible. Ruby will attempt to evaluate the entire infinite list, eventually running of of memory in the process.
New to the upcoming Ruby 2.0 is a brand new class called Enumerator::Lazy that allows lazy evaluation for enumerators. This means infinite lists of data are now also easily possible in Ruby.
Let’s return to our prime example for a minute. Assuming we have a class Prime that is an enumerator that will generate an infinite stream of prime numbers, here’s the solution for both of our previous problems:
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_aImplementing code this terse and readable without the use of the lazy enumerator would be a tall order. This is the alternative to the first lazy enumerator example:
a = []
Prime.each do |x|
next unless x.to_s.include?('3')
a << x
break if a.size == 20
endThis is pretty much the opposite of functional programming: a variable used for state, and loop management all over the place. This code is more about telling Ruby how to do what we want; contrast this with our lazy example, which is about telling Ruby what we want. This is a core essence of functional programming.
There is another huge advantage of lazy evaluation. Look at this code:
(1..100).select { |x| x % 3 == 0 }.select { |x| x % 4 == 0 }This code attempts to find all numbers between 1 and 100 that are divisible by both 3 and 4, but in the process iterates over the set of numbers twice! Lazy evaluation collapses all of the enumerator actions into a single iteration:
(1..100).lazy.select { |x| x % 3 == 0 }.select { |x| x % 4 == 0 }.to_aThis could dramatically speed up code where multiple filters are being applied to a collection. This collapsing of the enumerable chain works for any of the many methods defined on the Enumerable class, including but not limited to, #select, #map and #take.
At the present time, Enumerator::Lazy is very slow because the cost of creating and calling the collapsed block is very expensive; there is a patch outstanding to fix this, so very likely the final version of Ruby 2.0 will have a must faster version of the lazy enumerator compared to the current implementation in trunk Ruby.
Applying These Lessons To The Real World
Writing Ruby in a functional style is not about writing pretty one liners that don’t use variables. It certainly is not about exploiting hidden features of Ruby just to keep things functional, either. It is about writing clean, maintainable code.
Part one of this series looked at immutability. Real world code is going to need to manage state at certain times. However, we looked at a real world example of creating a CSS generator that has a nice DSL, is chainable, and is entirely functional; this is pattern you can apply to many problems, resulting in clean and easily testable code. In fact, you will likely find patterns like this already in the wild because they are so indispensable for creating fluent DSLs.
Part two of this series looked at higher-order functions, and currying. These are two principles that can be used in your code starting today. You could use higher-order functions to simplify both code and tests, and currying could be used for providing more usable DSLs in your application or library without the code baggage that normally comes with it.
This final article, part three, addressed recursion and laziness. Recursion you can use today in the form of Enumerator and Enumerable, and certainly you will find a multitude of classes in the wild making use of the later mixin. Laziness is a new feature that will make its debut in Ruby 2.0, but that you may possibly wish to start thinking ahead of uses right away because it is so useful.
However, the main point of this series was less about strict code examples and more about being more educated about the principles behind your everyday code. Certainly, a more productive and more efficient programmer is one who understands the tools at his disposal. This programmer uses only the tools needed at the time they are actually required. Functional programming is an exercise in minimal coding, achieving the most efficient yet terse code, and increasing readability by putting the language to work for you. That Ruby provides so many ways to do this is exciting. As a community we need to embrace these wonderful tools as best we can.
Good luck, functional Rubyists!
Nathan KleynHi! I currently work for Intent HQ as Director of Engineering, writing functional Scala by day and Rust by night. I write for SitePoint about Ruby, and I’m on Twitter and on GitHub. You can get in touch with me at mail/at/nathankleyn.com.
