Functional Programming Techniques with Ruby: Part III

This entry is part 3 of 3 in the series Functional Programming Techniques with Ruby

Functional Programming Techniques with Ruby

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; ...; end
  • n.times do; ...; end
  • i.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)
end

If 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
        = 720

Think 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
end

This 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 # => Enumerator

Enumerators, 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 exception

You 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
end

This 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_a

Implementing 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
end

This 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_a

This 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!

Functional Programming Techniques with Ruby

<< Functional Programming Techniques With Ruby: Part II

Free book: Jump Start HTML5 Basics

Grab a free copy of one our latest ebooks! Packed with hints and tips on HTML5's most powerful new features.

  • Jabari Zakiya

    [22] pry(main)> require ‘benchmark’
    => true
    [23] pry(main)> require ‘benchmark/ips’
    => true

    [24] pry(main)> def fact1(n); return 1 if (0..1).include?(n); n*fact1(n-1) end
    => #
    [25] pry(main)> def fact2(n); (1..n).inject(:*) || 1 end
    => #
    [26] pry(main)> def fact3(n); return 1 if n #

    [27] pry(main)> fact1 0
    => 1
    [28] pry(main)> fact2 0
    => 1
    [29] pry(main)> fact3 0
    => 1
    [30] pry(main)> fact1 1
    => 1
    [31] pry(main)> fact2 1
    => 1
    [32] pry(main)> fact3 1
    => 1
    [33] pry(main)> fact1 2
    => 2
    [34] pry(main)> fact2 2
    => 2
    [35] pry(main)> fact3 2
    => 2
    [36] pry(main)> fact1 10
    => 3628800
    [37] pry(main)> fact2 10
    => 3628800
    [38] pry(main)> fact3 10
    => 3628800

    [39] pry(main)> Benchmark.ips do |r|
    [39] pry(main)* r.report(“fact1″ ) do 50.times {|i| fact1(i) } end
    [39] pry(main)* r.report(“fact2″ ) do 50.times {|i| fact2(i) } end
    [39] pry(main)* r.report(“fact3″ ) do 50.times {|i| fact3(i) } end
    [39] pry(main)* end
    Calculating ————————————-
    fact1 56 i/100ms
    fact2 105 i/100ms
    fact3 102 i/100ms
    ————————————————-
    fact1 576.1 (±13.5%) i/s – 2856 in 5.044399s
    fact2 1088.3 (±10.8%) i/s – 5460 in 5.072942s
    fact3 1103.5 (±13.1%) i/s – 5508 in 5.073773s

    On this benchmark fact3 is (by a little bit) the fastest on Rubinus 2.0.0rc1.

    Here are the results for Ruby MRI 2.0.0rc1

    [19] pry(main)> Benchmark.ips do |r|
    [19] pry(main)* r.report(“fact1″ ) do 50.times {|i| fact1(i) } end
    [19] pry(main)* r.report(“fact2″ ) do 50.times {|i| fact2(i) } end
    [19] pry(main)* r.report(“fact3″ ) do 50.times {|i| fact3(i) } end
    [19] pry(main)* end
    Calculating ————————————-
    fact1 119 i/100ms
    fact2 165 i/100ms
    fact3 170 i/100ms
    ————————————————-
    fact1 1180.8 (±10.8%) i/s – 5950 in 5.095785s
    fact2 1623.8 (±9.3%) i/s – 8085 in 5.021475s
    fact3 1702.8 (±10.5%) i/s – 8500 in 5.046677s

    Again, fact3 is the fastest

    And now for Jruby 1.7.2

    irb(main):027:0> Benchmark.ips do |r|
    irb(main):028:1* r.report(“fact1″ ) do 50.times {|i| fact1(i) } end
    irb(main):029:1> r.report(“fact2″ ) do 50.times {|i| fact2(i) } end
    irb(main):030:1> r.report(“fact3″ ) do 50.times {|i| fact3(i) } end
    irb(main):031:1> end
    Calculating ————————————-
    fact1 170 i/100ms
    fact2 366 i/100ms
    fact3 437 i/100ms
    ————————————————-
    fact1 2518.2 (±11.7%) i/s – 12410 in 5.000000s
    fact2 3924.6 (±8.8%) i/s – 19764 in 5.074000s
    fact3 3943.1 (±8.0%) i/s – 19665 in 5.020000s

    So fact3 was fastest in each of these Ruby versions, with Jruby-1.7.2 performing this micro-benchmark by almost 4x faster than Rubinius 2.0.0rc1 and over 2x faster than MRI Ruby 2.0.0rc1. But fact2 is just a little bit slower than fact3 but I guess you would consider it more in the functional paradigm.

  • Jabari Zakiya

    Somehow the definition of fact3 was truncated. Here is the whole thing.

    def fact3(n); return 1 if n < 2; (1..n).inject(:*) end