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.

This example is straight from the problem set at (which I highly recommend taking the time to work through if you're interested in functional programming).

Write a function which takes a variable number of parameters and returns the maximum value.

Adding in the restriction that you can't use any pre-existing language level max function(s). In a run-of-the-mill imperative style, using Ruby, it might look something like this:

# imperative_max.rb

list = [1, 8, 3, 4]
max = 0

list.each do |i|
  if i > max then max = i end

puts max

This code just looks at each element, compares it to the maximum number found thus far, if the current element is larger than the max, then it becomes the new max. Repeat until you've traversed the entire list. Paste this into irb and you'll see that it prints out 8, which is the maximum number in the list. This is the sort of simple example that you'll see when you're first learning imperative programming. I can remember doing something very similar in QBasic when I was first learning programming in high school. It's not particularly good code. It runs in O(n); there are better ways to achieve the same goal. However, this code is pretty expressive and easy to grok for a beginner. Although not an optimal solution, it's an acceptable entry point. The problem is that it already starts to frame the way that the beginner programmer thinks about solving programming problems. 

Say this beginner programming later picks up on functional programming. Having learned what we know about functional programming: emphasis on recursion over iteration, list traversal, etc, it's trivial to transliterate the above solution within the same frame of the imperative thought process. Doing so, in Clojure, might result in code that looks like this:

# functionally-imperative-max.clj

((fn [& li] ((fn mx [r, m]
      (= 0 (count r)) m
      (> (first r) m) (mx (rest r) (first r))
      :else (mx (rest r) m)))
  li 0)) 1 8 3 4)

This is functional code, written within an imperative frame. It turns a bunch of numbers into a list and then recursively looks at each element, comparing to the current max, until every element in the list has been compared. After that it returns the current max. If you pop this code into your REPL you'll see that it returns 8, the same as the imperative code. This code works. Is it easy to grok? Maybe only to the more experienced Lisp programmers. Is it idiomatic functional programming? No, not really. It's not better than the imperative version; if anything, I'd say it's worse. It's missing that important shift in thought process and capitalizing on the power of a functional language. 

We don't want to think imperatively in a functional language. We want to think functionally. We want to use functions; to embrace the power that functions have in a functional language and utilize the tools for processing lists that the language offers. In Clojure a more idiomatic, non-imperative solution could be:

# functional-max.clj

((fn [& li] (last (sort li))) 1 8 3 4)

I probably don't even need to explain what this code does. Create a list, sort it, return the last element of the sorted list. That's your max. Paste that in your REPL and you'll see 8. Instead of recursion and list traversal, it uses data transformation and functional composition. Although recursion and list traversal are important aspects of functional programming, that doesn't mean they are the right tool to solve the problem. It's often just the path of least resistance to transliterate from an iterative style to a functional style using those tools. The real A-Ha moment comes when you don't just see the power of data transformation and functional composition, but actually start to think it. That's the paradigm shift. 

It's quite easy to transliterate this functional solution back into an object-oriented imperative style:

# imperatively_functional_max.rb

list = [1, 8, 3, 4]
puts list.sort.last

Instead of functional composition, you get method chaining. Method chaining being one of those techniques that comes with some pretty hefty caveats. Such a trivial example is pretty safe, but as your object graph grows, method chaining can quickly turn into a train wreck. 

The point I'm trying to make is that in order to be productive in a style of programming, you have to learn to think in that style of programming. It's something that I'm constantly reminding myself every time I switch from one language to another, or one programming style to another. Keep consuming information until you finally experience that moment where, all of a sudden, everything just comes together and is clear as day. Even if that means fumbling your way through writing a blog post about it. Eventually you'll get that Eureka.

You can discuss this post on Hacker News if you feel so inclined

4 responses
Thought provoking post. I enjoyed reading it. One obvious objection to functional-max.clj is that it can never have performance better than O(nlogn) due to the sort while finding the max is clearly O(n). The way to think functionally here isn't to find a clever way to get the maximum element at the end (or beginning) of the sequence and pick it off, but rather to think of the operation more abstractly. max is a function that takes a sequence of numbers and produces a single value using a function that does something with successive elements of the sequence. That sounds like reduce. Indeed (fn [& li] (reduce (fn [x y] (if (> x y) x y)) li)) is a pretty solid answer here and will be readable by anyone familiar with reduce. You could shorten it using the #() anonymous function syntax sugar, but I left the (fn []) style to be consistent with your post. Cheers!
thanks Brian! You raise an excellent point. I guess you exposed that my functional-max example was tailored somewhat to serving my larger point. I needed something that could illustrate functional techniques but also could be easily transliterated back into an imperative style. Your solution using reduce is definitely a better option in general terms. I think it really illustrates the power of functional languages. A solution to the same problem can be expressed in so many different ways. I opted against the function shorthand only because I thought it might keep the examples a little bit more clear for readers who aren't familiar with Clojure. I remember it being something that would trip me up when I was first learning the Clojure syntax.
(#(reduce max %&) 3 4 8) (fn [& li] (reduce max li))
Marutks, I'm sorry, but I'm not seeing the point of your comment. The restriction of the problem is that you *can't* use the pre-defined max function. However, if you are going to use max, I don't see what you've brought reduce into the mix, when (max 1 8 3 4 ) is sufficient. Sorry if I've missed something obvious. Maybe you could add some more context to your comment?