While having a conversation about functional programming with a fellow at work and how he has been using Scala to create an expression evaluator I realized that I have been doing some interesting work using Scala in the last months. However, I have not coded any basic algorithms from school time.
I decided to implement a sorting algorithm, let say quick sort, but I wanted to remove any trace of imperative programming from it.
In about two mins I ended up with this:
def quickSort(list: List[Int]): List[Int] = {list match {case Nil => Nilcase a :: Nil => List(a)case a :: tail => quickSort(tail.filter(x=> x <= a)) ::: List(a) ::: quickSort(tail.filter(x => x > a))}}
This is an interesting quick sort implementation that always get the pivote as the head of the list, but it is perfect in this particular case where we only have access to this element in a very natural way.
Then I went to the internet and compared my solution to the ones online.
This is the one that came out:
def sort(xs: Array[Int]) {def swap(i: Int, j: Int) {val t = xs(i); xs(i) = xs(j); xs(j) = t}def sort1(l: Int, r: Int) {val pivot = xs((l + r) / 2)var i = l; var j = rwhile (i <= j) {while (xs(i) < pivot) i += 1while (xs(j) > pivot) j -= 1if (i <= j) {swap(i, j)i += 1j -= 1}}if (l < j) sort1(l, j)if (j < r) sort1(i, r)}sort1(0, xs.length - 1)}
Well, it is the classical quick sort we can see in any programming class, but the imperative of the solution makes it ugly to write and read if we focus on Scala and its functional aspects.
On a deeper search, another solution showed up, this time, closer to what I was looking for.
def sort(xs: Array[Int]): Array[Int] = {if (xs.length <= 1) xselse {val pivot = xs(xs.length / 2)Array.concat(sort(xs filter (pivot >)),xs filter (pivot ==),sort(xs filter (pivot <)))}}
This one is quite closer to mine. However, it lacks of pattern matching, still uses a calculated pivote, and has if else unnecessary constructions.
Now, I can get something back from what I’ve found, I might modify my last case to case a :: tail => q(tail.filter(a >)) ::: List(a) ::: q(tail.filter(a <=)). But it seems difficult to read and understand if you are not related with the language, so I kept my solution as in my first implementation.
Endings
At the end, no everyone cares about implementation details, the only thing you see is a method (or function) signature you will call like def quickSort(list: List[Int]): List[Int]. Details of the implementation are left completely behind the wall that signature creates. This kind of approach is OK if you are the API user or consumer, but if you are the one who writes this API then it is a different story. On the other hand, how those details are written is important when the product has been implemented using different tools and technology stacks. Writing clean code, code that is easy to read and modify, is as simplest as we (programmers) decide to. I believe that functional programming helps a lot in this matter because we express ideas in code very close to the way we think about them.
I’ve heard folks talking against functional programming and the shift of mind it requires. It might scare sometimes, as any other changes in life, but don’t close yourself to the change, embrace new technologies and approaches to problems without fear, be someone who is willing to learn and you will be just fine.
Read next: