Thinking Functionally: Transforming Data (Part 2)

By now, I'm assuming that you've read Part 1. If you haven't, that's ok. Although this post follows thematically from Part 1, it can stand alone. Enough talk, let's get to it.

In Part 1 I talked a lot about this programming problem that I was asked to solve during a technical interview. Here's a rough reconstruction of that problem:

Use the BitTorrent encoding (Bencode) protocol to serialize the following data structures: String, Integer, List, Dictionary.

That's not the exact wording, but it's roughly equivalent. I suggest that you quickly review the Bencode protocol if you aren't familiar with it; just so that we'll be on the same page. I'll give a couple of examples from the Bencode wiki:

1: "Spam" -> 4:spam
2: 3 -> i3e
3: ["spam", "eggs"] -> l4:spam:4:eggse
4: {"cow" => "moo", "spam" => "eggs"} -> d3:cow3:moo4:spam4:eggse
5: {"spam" => ["a", "b"]} -> d4:spaml1:a1:bee
When this problem was presented to me, I approached it from the perspective of OO imperative programming. Let me tell you: that got really messy, really fast. 

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. 

Thinking Functionally: The Paradigm Shift of Functional Programming

I've been reading a lot about functional programming over the last year or so. I started with Scala and more recently picked up Clojure. Of everything that I've read about functional programming, it seems that the focus is on immutable data structures, the different types of functions, and the different ways that functions can be used together. Generally speaking, there is mention of the difference between imperative and functional programming, but I haven't yet read something that has truly expressed how much of a shift in thought process it is to go from thinking imperatively to thinking functionally when programming. Maybe it's just me. Maybe I just have an imperative brain, or maybe 18 years of focused imperative programming has enframed my view of what it means to program.

When reading about Lisp, you'll often hear about the Archimedean moment when you finally understand that data is code and code is data. I really haven't heard a similar sentiment about finally understanding the shift from thinking imperatively to thinking functionally. Maybe it just comes more naturally to everyone else? Maybe people don't notice that the shift happens? Or maybe people don't think it's important?

For me, it felt unnatural, drastic, and one of the more impactful revelations in my programming career. When first learning about functional programming, I just devoured everything I could relating to it. Everything I read seemed to make perfect sense. It had an inherit beauty to it; composing functions felt like composing music. You're using these finite building blocks to create something akin to a perfect whole. All of a sudden it seemed only fitting that Haskell would have monads

There's a heavy focus on list processing and recursion; you favour list traversals over iteration. You don't change data anymore, you transform it into new data. These are some of the highlights of functional programming. The problem is that it's possible to do all of that in a very imperative way. In the sense that you can essentially transliterate an imperative iterative solution into a functional recursive solution. You can write functional code that misses or ignores the shift in thought required for thinking functionally. Let's look at an example.