Let’s say that you have the following Ruby class representing banking accounts:

 1 class BankAccount 
 2   # [String] Name of the account owner
 3   attr_accesssor :owner
 4 
 5   # [String] email of the account owner
 6   attr_email :ownerEmail
 7   
 8   # [Float] Account balance
 9   attr_accessor : balance 
10     
11   # ...
12 end

Now let’s say that you want to collect the emails of all of the account owners at the bank. Perhaps you want to send them email about an upcoming promotion or a change in terms of service. First, let’s write a method that grabs the list of emails of all the account owners.

1 # @param accounts [Array[BankAccount]] list of accounts
2 def getEmails(accounts)
3     arr = []
4     accounts.each { |acc| arr << acc.ownerEmail }
5     arr
6 end

Mapping over lists

This is nice, but it turns out that there’s a common way called mapping over the array. This trick allows us to eliminate the use of the intermediate array:

1 emails = accounts.map { |acc| acc.ownerEmail }
2 emails.each do |x| 
3     # ... send email
4 end

(Note: map is not a standard function. We haven’t written it yet.)

Just a quick note, using .each won’t work, it gives us back the original list:

1 emails = [1,2,3].each { |x| - x }
2  => [1, 2, 3]

In general, if I have a list of type , and a function that goes from , . That’s a mathematical way of saying: “if you give me a function that transforms s into s, I’ll give you a function that transforms lists containing s, into lists containing s, by using .”

If the mathematical notation there is confusing, think about it in terms of Ruby arrays. map is a function that takes two things:

  • A block that transforms elements of some type A into some type B. (Let’s say Fixnum to Fixnum, e.g., { |x| -x }.

  • An array containing elements that will all be transformed by that block.

Implementing map

So let’s write a function, remember, we’ll use yield to call the block:

1 def map(arr) 
2     retArr = []
3     arr.each { |x| retArr << yield(x) }
4     retArr
5 end

Now we can call map:

1 map([1,2,3]) { |x| -x }

Higher order functions

map is what we call a higher order function: it transforms functions into other functions. In other words, it takes a block, and allows that block to operate pointwise over the array. This is a concept that we’ll be formalizing later in the course, so seeing it here will (hopefully) help you connect it the more mathematical presentation later.

Note: We implemented map by ourselves, but it’s also implemented as a method of arrays. We could have done this just as easily ourselves by extending the Array class

Example, plotting mathematical functions

We can use map to generate mathematical sequences and graphs.

 1 # I extend the numeric class
 2 class Numeric
 3   def degrees
 4     self * Math::PI / 180 
 5   end
 6 end
 7 
 8 pairs = (0...360).to_a.map { |x| [x,Math.sin(x.degrees)] }
 9 
10 xs = pairs.map { |x| x[0] }
11 ys = pairs.map { |x| x[1] }
12 
13 require 'nyaplot'
14 plot = Nyaplot::Plot.new
15 sc = plot.add(:scatter, xs, ys)
16 plot.export_html

You can view the graph here.

I used the nyaplot library to generate the plot. You can read about nyaplot here.

Folding over lists

Our example above has a problem: what happens when you pass in accounts that have the same owner? An individual may have more than one account with our bank, and because of that, they’d be emailed multiple times. We don’t just want the list of email addresses: we want the list of unique email addresses.

Let’s write a function unique that takes lists and returns a new list that contains only unique elements of the original list:

1 unique([1,2,3,2])
2 # [1,2,3]
1 def unique(arr)
2     retArr = []
3     arr.each { |x| if !retArr.include?(x) then retArr << x end }
4     retArr
5 end

This technically works, but there’s another way to do it that illustrates another basic higher order list operation: fold.

Let’s say we have a list of numbers:

1 x = [1,2,3]

And let’s say I want to sum them.

One thing that I could do is write them out on a sheet of paper, and keep a tally of how many I have so far:

 1 1 <-- 1
 2 2
 3 3 
 4 
 5 then...
 6 
 7 1 
 8 2 <-- 3
 9 3 
10 
11 then...
12 
13 1 
14 2 
15 3 <-- 6
16 
17 6

To do this I repetitively:

  • Looked at the next thing in the array
  • Added it to the accumulator

This is a technique called folding the + operator over the array.

We’re going to write a function that behaves like this:

1 fold(0,[1,2,3]) { |acc,hd| acc + hd }
2 # 6

The 0 above is called the initial accumulator. It tells us what to do when we run out of stuff in the array.

Here’s the function fold:

1 def fold(base,arr) 
2   accumulator = base
3   arr.each do |element| 
4     accumulator = yield(accumulator,element)
5   end
6   accumulator
7 end

Now I’m going to call fold with a function that sums the accumulator:

1 2.0.0-p0 :025 > fold(0,[1,2,3]) { |acc,x| x + acc }
2  => 6

Now, let’s write an implementation of unique using fold:

1 def unique(arr)
2   fold([],arr) do |acc,element| 
3     if !acc.include?(element) then
4       acc << element 
5     else 
6       acc
7     end
8   end
9 end

Errata

When I originally wrote this post, I left out the else branch in the previous definition of unique. Let’s see what happens on an example array when I do this:

 1 def unique(arr)
 2   fold([],arr) do |acc,element| 
 3     if !acc.include?(element) then
 4       acc << element 
 5     end
 6   end
 7 end
 8 
 9 unique([1,1])
10 
11 ## Unique calls fold...
12 
13 def fold([],[1,1]) # <-- substituted arguments here.
14   accumulator = base
15   arr.each do |element| 
16     accumulator = yield(accumulator,element)
17   end
18   accumulator
19 end
20 
21 # First thing: line 2 of fold
22 accumulator = []
23 
24 # Then
25 [1,1,1].each |element|
26   accumulator = yield([],1)
27   
28   # Which calls the block passed in
29   if ![].include?(1) then
30     accumulator << element 
31   end
32   
33   # And that's true, so we say acc << element
34   
35   # Now we call each for the *second* time:
36   if ![1].include?(1) then
37     accumulator << element 
38   end
39   
40   # And that's false, so the block **returns nil!**
41   
42   # Looking at what fold does, it updates accumulator = nil
43 
44   # Now the block goes through this a **third** time, and tries to
45   # call nil.include? And we **get an exception!**

Potential homework

Another operation we can perform on arrays is filter out elements from them. The function filter that accepts a predicate as a block and filters arrays is something you should try to figure out on your own!