Thinking Functionally: Transforming Data (Part 1)

Once upon a time I interviewed with one of the big SV startups. It was my first technical interview, and feeling understandably nervous about it, I did what I could to prepare myself. I read about other people's experiences in similar interviews, did some code katas, and solved some math problems. Mentally, I was prepared. From a technical perspective, I was missing something. At the time I was very comfortable with imperative programming, but hadn't yet been turned on to functional programming. I approached problems within a very imperative frame of thought. In most cases, that's not a detriment, unfortunately for me, in this case, it was. 

I was confident that I could (eventually) solve any problem that they threw at me; the issue was that I didn't necessarily know how to solve it well. To know how to solve a problem well means being able to not only understand the expectations of problem, but also to be able to think in terms of the problem. How do you think in terms of a problem? I think it comes down to the idea that some problems lend themselves relatively better to certain kinds of solutions. 

Let's start with a trivial example: calculating the sum of a list of numbers. 

This is the kind of problem that lends itself very well to functional programming. In Clojure, a simple solution to sum a list of numbers could be:

(reduce + [1 2 3 4 5])

Traverse the list, applying the plus operator to each element. All the while Clojure keeps a running total of the result of each operation. You could say that this solution transforms a list into a single number: [1 2 3 4 5] goes in, 15 comes out.  

In an imperative style the solution is quite different, at least from a conceptual perspective. It's no more or less complex, maybe a little less succinct. A very simplistic imperative solution in Ruby -- if we ignore some of the syntactic nuances: :+, { } blocks, etc -- might look something like this:

sum = 0
[1, 2, 3, 4, 5].each do |i|
  sum += i

Define a starting point for the sum, traverse the list, building up the sum by applying the plus operation to each element. You could say that this solution builds a sum: starting with 0, then changing to 1, then 3, etc. 

Do you see the distinction I'm making here? It's kind of subtle, but I think it's very important. The functional style has an implicit notion of transforming from one type of data to another: a list becomes an integer. The imperative style has more of an explicit notion of building data from nothing to something. 

You'll find that pretty much any programmatic problem can be solved in either an imperative or a functional style. What's important is that some problems are just better suited to solutions that build data, while other problems are better suited for solutions that transform data. An important part of thinking functionally is being able to see when (as well as when-not) a solution is best suited for transforming data.

Back to my opening anecdote: this concept of transforming data was a subconscious lesson that I took away from the interview. I call it a subconscious lesson because at the time, I wasn't aware that I had learned anything. My proposed solution worked, in that it produced the expected output, yet something about it seemed... unnecessarily complex. Something about it just didn't smell right. I knew it could be improved, but I lacked the context to be able to frame the problem differently. 

This problem just plagued my mind in the weeks after the interview. Every once in awhile it would come to mind and I'd take another crack at it; never satisfied with my solution. It wasn't until I started learning about functional programming that I was able to concretize that subconscious lesson. It gave me the context to view the problem from a different angle; within a different frame of thought. I was able to think in terms better suited for the problem. You might even say that I had glimpsed the essence of the problem. 

By now I bet you're wondering: "What is this paradigm shifting, thought altering programming problem?". Let me tell you that it's not as exciting as I've made it out to be! Originally I was going to include it in this post, but I think I'll save it for Part 2; this post is already sufficiently long! Stay tuned for Part 2, it will include the actual interview problem, an in depth look into why it is well suited to a functional solution. You'll have to wait for Part 3 to see a full solution in less than 20 lines of Clojure.