Functional programming by example

Functional Programming is becoming a really big concept; languages like Ruby and Python have gained quite a bit of popularity and introduce some functional concepts. Other languages like Erlang, Haskell and Lisp while having a decent developer base still remain as the "It's just really hard to write in" bucket of languages. Java has been such a powerful force in the software community in the past decade; as such, the JVM has become such a great, powerful, portable way of distributing software. On the JVM there are even more languages that have been introduced which contain functional concepts. Languages like JRuby, Jython, Groovy and Scala have opened the door of functional programming to many more people. Let's start by looking at a list of concepts which make up a functional language.

• First-class and higher-order functions
• Pure functions
• Recursion
• Strict versus non-strict evaluation
• Statements
• Pattern Matching
• Immutable Variables

We'll look at some of these concepts and how we can use them to our advantage in real world software development. As we look at these concepts, we'll be looking at code examples as well. The list above is not an exhaustive list; and actually the last 4 are concepts that I wholeheartedly believe are key parts of functional programming. Some of these concepts can actually be achieved through imperative languages; so we'll talk about some of them. Without further ado, let's get started!

First-class and higher-order functions

This sounds like it's two different concepts; but really they are intertwined. First-Class functions are when functions are actually objects themselves. This means that you can send them to other functions or return them from functions which incidentally is what higher-order functions are. You can see these with Closures in Groovy such as below.

def incBy1 = { x -> x + 1 }

So now we have incBy1, and this is a function. The cool thing here is that we can now send this to another function to execute. But why would we do this? Well, let's assume that we have a function. It's job is to perform some operation to an integer and print out the value. Not very useful right? Don't worry it'll become more understandable in a minute. So let's see this function.

def printResultingNumberOperation(val, fn) {
        println(fn(val))
}

Now we just need to put it all together and see it running.

printResultingNumberOperation(1, incBy1)

Which results in 2 which really isn't that awesome. But in essence this is a perfect example of first class functions. Notice that the function incBy1 is it's own variable, so technically we could just execute it; and by it I mean execute the variable.

println incBy1(1)

Which has a resulting output of 2, this is probably less awesome than our previous example. Oh noes! But never fear, let's take it up a notch. printResultingNumberOperation is actually a higher-order function; why, because it takes a function as a parameter. Remember we said that higher-order functions are those that can take or return a function. Remember incBy1? Let's do some abstraction there; what if we just wanted an incBy2 or incBy3? Oh noes, we're going to be doing copy and paste! Do not do this, copy and paste is evil. Why is it evil? Because if you have a bug in incBy1; inherently you have a bug in incBy2 and incBy3! Well you'll just remember to update them right? Wrong, that never happens; I promise you, incBy2 and incBy3 will deviate from the updates to incBy1. And sadness will ensue. So let's abstract incBy and take a number. Check this out.

def incBy(num) {
        { x -> x + num }
}

Many of you might be asking "what are you doing?" Well, let's break this down. We are defining a function incBy that takes a single argument "num." And what does it return? Well, it returns a function (making incBy a higher-order function) and that function takes a parameter "x." It will then add "x" to "num" and return the result. It's important to understand that the "num" variable will be "closed over" and result in a "closure." Essentially, the returned function keeps "num" in scope even after the function incBy has returned. If that makes very little sense; let's see how to use this and that should make a bit more sense.

println incBy(2)

But wait, this prints out some garbage temp$_incBy_closure1@5815338! Right, remember that I said incBy will return a function; you're just seeing the toString. So what can I do with that? Well you can execute that function; remember above, it's a function that takes a single argument. So let's see what happens when we call it with 2 (hint, it should return 4).

println incBy(2)(2)

And what do we get, 4. Surprise; our function incBy that we called with 2 ended up with a function that did x + 2; and since we executed it with 2 we got 2 + 2 ending up with 4 as our return. So how is this useful? Well do you remember printResultingNumberOperation which takes a function which takes a number and increments it by some amount? Well how about we use it there!

printResultingNumberOperation(2, incBy(2))

And what do we get, 4; that is just amazing and life altering! I can write code which is reusable since I can abstract large chunks of my functions. This is one of the main things that a functional language must implement; if it does not have this, it is not a functional language.

Pure functions

Pure functions are functions that have no side effects. They are functions that purely execute on their parameters themselves. This allows the system to do more optimizations by either inlining code or even caching the results (since if what is put in is always the same coming out). To understand what pure functions are; we must first understand what side effects are. Let's look at some examples of side effects.

• Output
• Class Mutators
• Parameter Mutators (really bad!)

Output

This is pretty straight forward; if you have a method, such as a logger or a database write; it's always non-pure. Why? Because the side effect of writing data to the console or to the database is something that changes every time it's called. Performing a log or database write is a side effect to calling the method.

Class Mutators

This is actually tied closely into immutable variables so I'm not going to get into Immutables until later. But the idea is still there; if you have a .setX(x) method which does exactly that "this.x = x" then this is a method with a side effect. The side effect is that we are mutating the current object. What is another option to make the function pure? Well let's say ".setX(x)" will create a new object and set the X during creation. Again, this ties into immutable variables so I'm not going to get too far into this.

Parameter Mutators (really bad!)

This one is really bad and also ties into immutable variables. Frankly this is one of those concepts that I choke on when I see someone violate. If you pass in a variable; and you try to change that parameter, you are doing it all wrong! Let us look at an example of this atrocity again in Groovy.

class Me {
        String fname

        def setFname(str) {
                this.fname = str
        }
}

new Me().setFname("Test")

So why is this so bad? Well this is actually a simple example which reflects a larger problem. What if I didn't actually want to change Me; why am I changing an input variable itself? Imagine if I had the following example.

class Me {
        String fname
}
def checkName(m, f) {
        if(m.fname != f) {
                m.fname = f
        }
}
def m = new Me()
checkName(m, "Test")
println(m.fname)

Well why is this bad? Because checkName is not clear in what it's doing. It's actually changing the value of my object that I'm sending in. This inherently means that I cannot trust my object that I send in. What should we have done instead?

class Me {
        String fname
}
def compareName(m, f) {
        if(m.fname != f) {
                new Me(fname: f)
        } else {
                m
        }
}
def m = compareName(new Me(), "Test")
println(m.fname)

So why is this better? Because I know that the Me I'm sending in cannot change. This means that either I can send a brand new Me or I can send another Me that has already been initialized and I'm assured that I have the original. Again, this goes to immutable variables; but it's important to understand that we want pure functions or functions that have no side effects.

Recursion

This is one of my favorite topics; not just because it makes peoples brains explode, but because most software developers are so scared of it they refuse to use it. Let's talk about the simple definition. A function that calls into itself to perform loops. So why does everyone find it difficult? Because you have to be correct with the end cases. The best thing to do is to define your end cases as soon as your begin writing your recursive function. But this isn't all; everyone has had to write a recursive function which recurses too deeply. Let's look at one example of recursion in Scala.

def fibonacci(i : Int) : Int = {
  if(i <= 0) { 
    0 
  } else { 
    i + fibonacci(i-1) 
  }
}

Notice that we have defined our end case (i <= 0) and we've performed general recursion. If I call this on 10, I get back 55; all seems non problematic until we try some large number. Let's say we want to find the Fibonacci number at the 10,000th spot. What happens? java.lang.StackOverflowError oh noes, I can't do that! So how do we get around this? Well; we use a technique called tail-recursion. It essentially keeps the recursive definition in code; but converts it to iteration at compile time. Now why do you do this? Well because recursion is one of the best ways to implement an algorithm (at least in my opinion) as it allows us to do much better and much more concise code within the algorithm. So what is tail recursion? Well, simply put; the call to the function (from within the function) should not require any further operation. Let's look at an example (again in Scala).

def fibonacci(i : Int, acc : Int = 0) : Int = {
  if(i <= 0) { 
    acc 
  } else { 
    fibonacci(i - 1, i + acc) 
  }
}

What happens if we call this with 10? We get 55, yay it still works. So what happens if we try 10,000? We get a ridiculous number of 5,0005,000; it didn't crash! So if we notice; the call to "fibonacci" has nothing that it relies on once it executes. Since the compiler understands this, it will convert this into an iterative loop. This allows us to write the code and utilize immutability, instead of in a for loop where you would have to have a counter that would need to mutate over time. Instead we pass the accumulation (state) back into the call of the function. Most functional languages will support this tail-call, languages like Lisp/Scheme, Scala, Erlang, and even C support this type of call. Other languages such as Groovy, it is not directly supported but instead is accomplished by using Trampolining. I won't get into it, but essentially you have a function that will call the function each time and wait for a specific end case "trampolining" between the actual function and the function maintaining it's state.

Strict versus non-strict evaluation

Strict evaluation is also called eager evaluation; non-strict is also called lazy evaluation. When we think about defining languages; we normally think about defining a variable.

def x = 10

This means that x is eagerly defined. So if we did something like below; we would expect x to be defined immediately.

def x = 10 * 10

So now, x is defined as 100; but what if we didn't want to have it evaluated immediately? What if that initialization was extremely costly? Well, we could either change it into a method call so that it would only be defined when we need it. But if we have to call it multiple times; we have to calculate it multiple times. Well certain languages like Groovy, as shown below, and Scala, as shown below that, allow you to define a variable as Lazy. This means that the variable is not actually defined until you use it.

class Me {
        @Lazy def o = [x()]

        static def x() {
                println("X Called")
                1
        }

}
println("Create")
def me = new Me()
println("Done Creating")
me.o.size()
println("Complete")

What is our output?

Create
Done Creating
X Called
Complete

Notice how "X Called" doesn't actually happen until we've actually called anything about o. Otherwise we do not execute the evaluation of o. Scala does the same kind of thing as shown below.

def x() = { 
  println("X called")
  1 
}
println("Create")
lazy val v = List(x())
println("Done Creating")
v
println("Complete")

Which gives us the exact same output.

Create
Done Creating
X Called
Complete

Again, this type of functionality is really useful for waiting before making large computations or executions that will define a variable until it's actually necessary.

Statements

Statements are very key to functional programming; at first glance, they seem like a useless predicate of a language; but when getting into immutable variables it becomes a very important part of the language itself. Statements are exactly that; every statement that occurs has (or should have) a return of some type. So take, for example, an if statement. Within functional programming an if statement should always return a type. Let's look at an example of a statement in Scala really quickly.

println(if(true) { 10 } else { 20 })
println(if(false) { 10 } else { 20 })

This gives us the output.

10
20

As we can see, the if statement itself actually has a return value. This is much like a ternary statement; you know the one that looks like

(true)?10:20

We also know that the last statement in a block is the return value of that block. check out this example of a block in Scala.

{
  val v = 10
  v + 20
}

This then returns 30 since v is 10, and 10 + 20 is ta-da 30 and this was the return of the last statement in the block. The reason why statements are so important is because we can do things like using function returns or, as we'll see, the return of an if statement or block to build an object. While this sounds crazy; it actually becomes simpler to understand the code over time. Let's see an example in Scala below.

class Test(str : String, length : Int) {}

So let's say that we want a method that generates a Test object; and if a null is passed in it should send back a Test with a blank string and a length of zero. How would we do this normally in an imperative manner?

def NewTest(str : String) = {
  val _str = if(str == null) {
    ""
  } else {
    str
  }
  new Test(_str, _str.length)
}

This is a good example of a statement, but let's try to remove the unnecessary variable.

def NewTest(str : String) = {
  if(str == null) {
    new Test("", 0)
  } else {
    new Test(str, str.length)
  }
}

Now this is really nasty; now we have to maintain two different branches where we create a new Test. So let's make the composition of Test be statements.

def NewTest(str : String) = {
  new Test(
    if(str == null) {
      ""
    } else {
      str
    }, 
    if(str == null) {
      0
    } else {
      str.length
    }
  )
}

So notice that the creation of Test is only defined once; it is composed of statements to build it's components. If we were to extend the if statement and add another branch; it would probably be best to rip those out into their own functions. Let's say, for example, that we just wanted to do something if it was null; maybe we can do a higher order function here?

def NewTest(str : String) = {
  def handleStr[T](op : String => T) : T = {
    op( if(str == null) { "" } else { str })
  }
  new Test(handleStr(x=>x), handleStr(x=>x.length))
}

This works out really well because we can just modify handleStr to do any extra checking in the future. And notice that we never use a variable and instead we are able to let handleStr deal with the edge cases for us.

Pattern Matching

Pattern matching is one of those topics that either people understand or they just miss the boat on what it is designed to do. There are plenty of uses for pattern matching and we'll look at a few of them in this section. For this section we'll be looking at examples in Scala.

Basic Functionality

We're going to start with something that is extremely reminiscent of a switch statement. We'll start with a boolean and look at a true, false, and everything else case.

true match {
  case true => "We're True"
  case false => "We're False"
  case _ => "Something that was not true or false"
}

From here, we will end up with the string "We're True". Now this seems odd, but if we assume that we just care if the match was true, otherwise we assume it's false we can do this instead.

true match {
  case true => "We're True"
  case _ => "Was false or something else"
}

Now what about a numerical value?

0 match {
  case 0 => true
  case _ => false
}

We now have a way to do simple matches and help us determine if our value was 0 or something else. Now this might now seem very interesting; but let's see what happens if we have a String and we want to make sure we have a valid string (non-null).

"string" match {
  case null => ""
  case str : String => str
}

Now why is this important? Because, remember we want to use as few variables as possible, you can do a match for a function return and get the string without storing it.

stringOperation("string") match {
  case null => ""
  case str : String => str
}

As we see, if stringOperation returns null we will end up with an actual valid blank string which is operable. If we get a string, then we'll just return that. So now we get the very basics of pattern matching.

Extracting Attributes

One of the general uses for pattern matching is to extract certain attributes from classes. Pattern matching is really useful when matching against lists. We'll look at list examples for now; and to start out we're going to see a basic list and we'll take the head element off of the list.

List(1, 2, 3) match {
  case List() => -1
  case x :: xs => x
}

So here we can see that we're looking for an empty list; and if we get an empty list we will return a -1. If it's not an empty list; we will extract the first element from the list (the head element) and return it. This usage of "::" is an unapply which allows us to extract the attribute. What is interesting here is that the :: will extract the head element in an x variable and the rest of the list into the xs variable which become available to the right of the => which is the body of the case statement. Now what is really cool is that we can actually extract more than just once!

List(1, 2, 3) match {
  case List() => -1
  case x ::  y :: xs => y
}

Now we're going to expect to get 2 since we extracted 1 into x, 2 into y, and List(3) into xs. Now if we look at this; there is clearly a missing case, x :: xs (which could also be x :: List(). So on compilation we end up with a warning warning: match is not exhaustive! which will let us know that we should extend our matches so that we don't fall off the end. Now for the mind killing part; you can actually use literals to extract certain parts of match.

List(1, 2, 3) match {
  case List() => -1
  case 1 ::  x :: 3 :: xs => x
}

And from this output we get 2; notice how we extracted the 2nd element by using the variable x and indicating where we wanted to rip it out from. This is some of the more general usages of pattern matching; next we'll look at case classes and how they are used to pass messages.

Case Classes

One of the major selling points of pattern matching is the ability to extract objects themselves. In Scala these are case classes which we'll look into. The basic concept is that a case class can be used to extract attributes from an object. Let's look at a very simple example.

case class MyObj(str : String, len : Int)
new MyObj("Foo", "Foo".length) match {
  case MyObj(str, len) => println(str + "@" + len)
}

As we can see, we match on the fact that we have an object and we are able to extract all of the attributes from the object itself. So the big question is; why do we care? We can access the attributes from the object anyway. Well here is the thing; we can use inheritance to do an extraction based on the child class.

trait MyTrait
case class MyObj1(str : String, len : Int) extends MyTrait
case class MyObj2(num : Long) extends MyTrait
def exec(in : MyTrait) : Long = in match {
  case MyObj1(_, len) => len.toLong
  case MyObj2(n) => n
}

So now what happens if we call it; more specifically, what if we call it with MyObj1 and how does it differ from MyObj2? Let's look at MyObj1 first.

exec(new MyObj1("Foo", "Foo".length))

So what do we get? Well we're going to get 3 as a return. Why? Because the match succeeded on the case MyObj1(_, len)! So what happens if we call this again with MyObj2?

exec(new MyObj2(22))

This gives us 22; which we kind of expected by now. This means that we can extract attributes of an object as we enter a function; or choose which function to execute based on the type of the object passed in; again, all without having to store any state.

Immutable Variables

This is a concept that is not new to programming; it is also not specific to functional programming. Think about this statement from C.

const char *str = "MyString";

What does this mean? Well, it means that the variable str cannot change after being set. Well why does this matter? Personally I think that this goes to the very heart of what functional programming is. When we think about functional programming; we think of returns from functions being sent directly as a parameter to another function. If we think about functional programming like this; then we can assume that a return from a function would not be changed before it was passed into another function. If this is true; then we can, for the most part, not need any variables whatsoever.
But of course, there are cases when a variable might be returned and we will need to pass individual components of the return to other functions. In these instances, we will need to store the variable such that we aren't doing the calculation that resulted in the return multiple times. In doing so, we should not make it possible to modify the variable in it's transitory state. Think about it; if we did multiple threads, and each of those threads were touching a variable that IS mutable; then it's possible that one thread could be modifying the variable at the same time another thread is trying to read it.
So now, let's think about this example; if I know that my object A cannot be modified (all of the components of the object are immutable). Then I also know that I can pass it to any method/function and know for a fact that I cannot change. This means that I can technically make multiple calls (if possible) against that variable concurrently.

Summary

As a quick summary, functional programming is all about purity in programming. Having pure functions as well as data that cannot mutate; only create new instances with mutated data. This type of programming ensures that bugs do not come from concurrent modifications; or modifications of variables where they shouldn't have modified. It also means that functions can be cached much easier especially with things like pure functions. Overall, using functional programming allows developers to be more expressive and thus be more intuitive to others picking up products from other programmers.
I hope that people find this interesting and help people to better understand what exactly functional programming means and how to start working programming in it. Remember, just because a language isn't setup to be functional (languages like Java or C) doesn't mean that you can't accomplish the same concepts. Although it's going to be much more painful and difficult to implement than actual functional languages (implementing higher order functions with interfaces and anonymous classes; an example is the Comparator interface and usage of it) it still has the same effect of good function re-use!