Igor Šarčević wrote this on October 13, 2015

Banning Iteration

In the last couple of months I have had the honor of being a mentor to several students that were taking part in our summer internship program. I had a ton of fun, learning not only about programming, but also about the art of teaching other programmers and helping them overcome their fear of complexity.

Even though they were all exceptional computer science students, a common pattern was their overdependency on the good old for loop. This was, of course, understandable. Java and C/C++ are the most popular teaching languages on our local universities. None of which, in my opinion, are good enough to prepare the students for the modern web and the level of abstraction required for working on bigger projects.

Basic iteration

One of the first things any computer science undergraduate learns is the for keyword. The magic word that can repeat common tasks and can even make our programs run forever. Here is a simple Java example that counts from one to ten:

for(int i=0; i < 10; i++) {
  System.out.println(i);
}

Another common thing is iterating over a list of values. For example, to collect the age of every user in an array, we could write:

int[] ages(User[] users) {
  int[] result = new int[users.lenght];

  for(int i=0; i < users.length; i++) {
    result[i] = users[i].getAge();
  }

  return result;
}

The issue with iterating with a for loop

Take a look at the above example that transforms the array of users into an array of numbers. It is a lot of work for such a simple task. The following list contains the mental steps needed for writing the above implementation:

1. Create an array that will hold the results
2. Set the capacity of the array to match the number of users
3. Create an iterator named i that will hold the current index of the array
4. Set up an iteration construct that will loop over every user in the array
5. Limit the iteration when the iterator i is the same as the number of users
6. Increase the iterator i after each step in the iteration
7. In every iteration lookup the user on the i-th location in the array
8. Get the age of that user
9. Save the age value in the result array on the i-th place
10. When the iteration is over, return the result to the caller

Well… this was a lot of typing. Plenty of room for making an error while writing the implementation.

Luckily, there are much better ways to achieve our goals.

Eliminating the redundant i iterator

Many students learn the for(int i=0; i < N; i++) construct by heart and replicate it everywhere, replacing the value of N with an appropriate value. But why would we do this? Automating things is one of the core principles of our craft. We should never let the computers make a fool of us!

Let’s switch from arrays to lists and use the newer for loop syntax:

List<Integer> ages(List<User> users) {
  List<Integer> result = new ArryaList<User>();

  for(User user : users) {
    result.add(user.getAge());
  }

  return result;
}

The above code looks nicer. Let’s write down the mental steps for this implementation.

1. Create an array that will hold the results
2. Set up an iteration construct that will loop over every user in the list
3. Get the age of the user in each iteration
4. Save the age value in the result list
5. When the iteration is over return the result to the caller

Much nicer and easier to understand. Here are some steps that we don’t have to worry about anymore:

1. Set the capacity of the array to match the number of users
2. Create an iterator named i that will hold the current index of the array
3. Limit the iteration when the iterator i is the same as the number of users
4. Increase the iterator i after each step in the iteration
5. In every iteration, look up the user on the i-th location in the array
6. Save the age value in the result array on the i-th place

Language switch

Unfortunately, vanilla Java can take us only this far. It is still possible to conceptually improve the above, but it takes a lot of effort and it is against the flow of the language.

Introducing Ruby! The language that can easily take us to the next level.

First, let’s rewrite the above snippet in Ruby:

def ages(users)
  result = []

  for user in users do
    result.push(user.get_age())
  end

  return result
end

A note for experienced Ruby programmers: I know you want to tear your eyes out, but please bare with me. The above monstrosity is only for demonstration purposes.

Let’s continue!

Eliminating the result set

First, let’s remove the non-typical for loop. Ruby programmers always prefer the each method over the for operator.

def ages(users)
  result = []

  users.each do |user|
    result.push(user.get_age())
  end

  return result
end

While the above snippet looks quite nice, it is still far from perfect! Notice the redundant result list that we explicitly create for every list transformation.

Introducing the map method. It is very similar to the each method with a simple but very important feature. It creates the result set instead of us, and places the result of every iteration in the appropriate spot.

def ages(users)
  return users.map do |user|
    user.get_age()
  end
end

Let’s review the mental steps in the above code snippet:

1. Set up an iteration construct that will loop over every user in the list
2. Get the age of the user in each iteration
3. When the iteration is over return the result to the caller

The following steps are no longer needed:

1. Create an array that will hold the results
2. Save the age value in the result list

Eliminating the return statements

The last step that returns the value of the calculation is usually not needed in Ruby. The language is smart enough to return the last calculated value from any method.

def ages(users)
  users.map do |user|
    user.get_age()
  end
end

This snippet reduces the number of mental steps to only two steps.

1. Set up an iteration construct that will loop over every user in the list
2. Get the age of the user in each iteration

Making the code nicer and more idiomatic

A true Ruby programmer would never write a get_age() method. Explicit actions are a relic of the past. Welcome to the age of declarative programming.

To access the age attribute of the method, we can simply write .age. Also, parentheses are optional. We will optionally remove them :)

def ages(users)
  users.map do |user|
    user.age
  end
end

The above method could be even shorter. A one-liner. In Ruby, the do ... end block is equivalent to curly braces.

def ages(users)
  users.map { |user| user.age }
end

Going even further by eliminating an explicit get

You probably thought that we could not go any further and declared it finished. However, there are still a couple of things that can be done. Notice that in the above example we explicitly read out the age value from every user.

Ruby has a shorthand operator for this.

def ages(users)
  users.map(&:age)
end

The above code snippet is equivalent to the previous one, but with one less mental step. Here is the current list of needed mental steps:

1. Collect the age of every user

The following step is no longer needed:

1. Set up an iteration construct that will loop over every user in the list

With the above code snippet, you could become good friends with any Ruby programmer. I am always happy to drink a couple of beers with programmers who can write code like this. Just saying…

The second Language switch

We are still not finished! Ruby is a great language but it has its limitations. But what could possibly be left to improve, you ask. Come and see. Introducing Haskell!

First, let’s start by rewriting the above snippet into executable Haskell code.

ages users =
  map age users

Eliminating the arguments

Haskell is quite smart when it comes to handling function arguments. It can pass the arguments to the end of a function’s body. The following is equivalent to the above:

ages = map age

It looks weird. I know! But you get used to it :)

Finally, let’s review the necessary mental steps for this implementation:

• None. The above code is practically effortless.

Conclusion

We came a long way from our original implementation in Java. Just for comparison, here are two identical implementations:

int[] ages(User[] users) {
  int[] result = new int[users.length];

  for(int i=0; i < users.length; i++) {
    result[i] = users[i].getAge();
  }

  return result;
}

ages = map age

I hope you, beloved reader, understand why I think that Java is far from ideal when it comes to teaching the next generation of engineers and overcoming the challenges that our craft presents.