Category Archives: FP For OO Developers

This is a series of blogs to introduce FP concepts and some FP language tutorials in Scala and Clojure for developers coming from an OO background.

Haskell div mod – Cyclical Division, Modulus Visualised

Reading Time: 8 mins
When I first came to integer division and the modulus operation in Haskell, I was thrown a bit of a curve ball, but a good curve ball at that. While Haskell does have two forms of integer division, one of those is a lot different from how I was used to thinking about integer division in other languages like Java and Scala. This actually comes in very handy for algorithms that cycle through ranges of values either left to right or right to left. However, as I was more used to the way it is done in Java and Scala, it took a bit of a mind-shift when I came to Haskell and saw another way to handle integer division and modulus.

One way of doing integer division in Haskell is with the quot and rem functions. They can be put together with the function quotRem and giving a tuple of the result and the remainder and this works like many would be used to from Java or some other languages.

ghci> let x = 8 :: Integer
ghci> let y = 3 :: Integer
ghci> quotRem x y
(2,2)
ghci>
ghci> let x = (-8) :: Integer
ghci> let y = 3 :: Integer
ghci> quotRem x y
(-2,-2)
ghci> let x = (-8) :: Integer
ghci> let y = (-3) :: Integer
ghci> quotRem x y
(2,-2)

ghci> let y = -3 :: Integer
ghci> quotRem x y
(-2,2)
ghci>

I’ve put together  a visualisation and a set of rules that I use to reason about another way that Haskell provides for integer division and along with its modulus operation. First, lets take 8 div 3 and show the results of the different combinations of positive and negative numerators and denominators.
Haskell has a handy function called divMod which returns a tuple with the first element being the integer division result and the second being the remainder (the result of the mod operation).

8 div 3

ghci> let x = 8 :: Integer
ghci> let y = 3 :: Integer
ghci> divMod x y
(2,2)
ghci>

-8 div 3

ghci> let x = (-8) :: Integer
ghci> let y = 3 :: Integer
ghci> divMod x y
(-3,1)
ghci>

-8 div -3

ghci> let x = (-8) :: Integer 
ghci> let y = (-3) :: Integer
ghci> divMod x y 
(2,-2)
ghci>  

8 div -3

ghci> let x = 8 :: Integer
ghci> let y = (-3) :: Integer
ghci> divMod x y
(-3,-1)
ghci>

These can be surprising results especially when compared to, say, Scala. For example, if we take -8 mod 3 in Scala, we get -2 unlike the 1 modulus result we got in our Haskell result (-3,1)

scala> -8 % 3
res2: Int = -2

Visualising Cyclical Integer Division And Modulus

The visualisation works as follows:

  • We have a denominator block in blue which has a length equal to the denominator.
  •  We have a denominator range that we are trying to move the block into which ranges from the denominator , inclusive, to the 0 boundary, exclusive.
  •  We move the denominator block until it partially or completely enters the denominator range.
  •  We have a Divisions accumulator which gets incremented or decremented.
  • If our block moves so that it approaches the denominator range without passing through the 0 boundary, we increment our Divisions accumulator with each move.
  •  Otherwise, the denominator block passes over the 0 boundary and we decrement our Divisions accumulator with each move.
  •  The final Divisions accumulator is the division result and the difference between the top of the denominator block and the 0 boundary gives the remainder.

8 div 2

0 Boundary

1
2
3
4
5
6
7
8

Divisions 0

0 Boundary

1
2
3
4
5
6
7
8

Divisions 1

0 Boundary

1
2
3
4
5
6
7
8

Divisions 2

0 Boundary

1
2
3
4
5
6
7
8

Divisions 3

0 Boundary

1
2
3
4
5
6
7
8

Divisions 4

Our last move brings the denominator block fully into the denominator range so we have no remainder.
So, 8 div 2 is 4 remainder 0.

8 div 3

0 Boundary

1
2
3
4
5
6
7
8

Divisions 0

0 Boundary

1
2
3
4
5
6
7
8

Divisions 1

0 Boundary

1
2
3
4
5
6
7
8

Divisions 2

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is 3 and the difference between the top of the denominator block and the 0 boundary is 2.
So, 8 div 3 is 2 remainder 2.

Changing division direction -8 div 3

Our Divisions accumulator gets decremented this time because we will be crossing the 0 boundary.

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 0

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -1

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -2

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions -3

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is -3 and the difference between the top of the denominator block and the 0 boundary is 1.
So, -8 div 3 is -3 remainder 1.

Making the denominator negative, -8 div -3

We can visualise the integer division in the same way. Except, this time the denominator range that we move the denominator block into is -3, inclusive to -1, inclusive.

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 1

-8
-7
-6
-5
-4
-3
-2
-1

0 Boundary

1
2
3

Divisions 2

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is 2 and the difference between the top of the denominator block and the 0 boundary is -2.
So, -8 div -3 is 2 remainder -2.

8 div -3

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions 0

0 Boundary


-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -1

0 Boundary

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -2

0 Boundary

-3
-2
-1
1
2
3
4
5
6
7
8

Divisions -3

0 Boundary

Our last move brings the denominator partially into the denominator range. Our Divisions accumulator is -3 and the difference between the top of the denominator block and the 0 boundary is -1.
So, 8 div -3 is -3 remainder -1

Conclusion

So integer division, when treated like it is with div and mod in Haskell, is different to what many developers would be used to from Java or Scala. The modulus operation is really a way to restrict elements to a certain range as dictated by the denominator. This is why the denominator blocks in the above visualisation are always trying to get into the denominator range without moving past it. It also makes sense to me that, when the denominator block arrives in the denominator range, the remainder is the difference between its top and the 0 boundary.

There are a lot of ways to visualise and think about these cyclical division and modulus operations. I hope this blog may help others reason about the these operations and explore other ways of thinking about them.

Dip your toes in some Haskell, the water is warm here!

Reading Time: 15 mins
Reading Time with hands on trying of the examples: 30 mins approx

Haskell Warm Water

So, Haskell sounds quite daunting right? All this talk of monads and functors when all you want to do is just try out some simple problems and see what it’s like to play around with this language! Monads and functors are actually not that scary once you get into functional programming but, for today, I won’t mention them again. So, lets dip our toes in and see what it’s like.

I often hear newcomers to functional programming sighing to themselves about how difficult it is to retrain their brains to read and write code in this paradigm that is new to them. Don’t get me wrong, the sighing is understandable especially when we have spent years wrapped in our imperative, object oriented comfort blankets with for loops and mutable variables. The sighing is usually witnessed when watching an experienced OO programmer getting to grips with a new codebase written in a functional language and seeing something like this:

5 isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)

Yep, there is a bit in there especially when you may be more used to the imperative way of writing such an algorithm.

 2 
 3 public class Palindrome {
 4 
 5     public static boolean isPalindrome(String str) {
 6 
 7         int strEndIndex = str.length() - 1;
 8 
 9         for(int i = strEndIndex; i > (strEndIndex/2); i--)
10             if(str.charAt(i) != str.charAt(strEndIndex - i))
11                 return false;
12 
13         return true;
14     }
15 }

Ah, that’s better. Our old reliable Java for loop with our mutable counter. Let me take you on a small journey to give you a taster for Haskell. We’ll go from Haskell code that actually looks quite similar to that imperative Java code and gradually work towards that previous Haskell code snippet. We’ll use the good old palindrome kata to take us on that journey. The palindrome kata is a task to write a function which checks if a String is the same going from left to right as it is going right to left. Yes, I know, most languages have a library function, reverse, meaning we can simply reverse the String and compare with the original. But lets suspend our disbelief for a while so I can take you on a journey!

Quick setup to follow along

To start dipping your toes in, why not follow along with the Haskell examples in the rest of this post. Haskell quick installers for most types of OS can be found here:
After that, all you need is a text editor and your terminal.
Make a new file called DipYourToesIn.hs and add the declaration for the Haskell module where we will put our functions:

 1 module DipYourToesIn where

Now crank up your favourite command line terminal and go to the directory where you created that file.
Now, simply type: ghci and this will start up the Haskell compiler in interactive mode allowing you to enter and evaluate Haskell expressions. We will use it to simply load and compile our DipYourToesIn.hs Haskell source so that we can call our Haskell functions as we create them to see it them working.

ghci> :l DipYourToesIn.hs
[1 of 1] Compiling DipYourToesIn    ( DipYourToesIn.hs, interpreted )
Ok, modules loaded: DipYourToesIn.
ghci> isPalindromeWithRecursion "hello"
False
ghci> isPalindromeWithRecursion "racecar"
True
ghci>

The Haskell source can be loaded and compiled using :l DipYourToesIn.hs
Once it is compiled, we can now execute functions within that file by simply calling them.
In the next section, we will be creating the function, isPalindromeWithRecursion, but the above just shows how quick it is to start interacting with Haskell code as you write it. In saying that though, this shouldn’t be a substitution for tests. I would still write tests first, and use this interactive approach to experiment with the code that I am writing to make the tests pass.

Imperative Looking Haskell – looks can be deceiving!

So, lets start off with some Haskell that models the above Java solution quite closely.

 2 
 3 isPalindromeWithRecursion :: String -> Bool
 4 isPalindromeWithRecursion str =
 5   loop strEndIndex where
 6 
 7   strEndIndex = length str - 1
 8   loop i =
 9     if (i <= (div strEndIndex 2)) then True
10     else if (str !! i) /= str !! (strEndIndex - i) then False
11     else loop (i - 1)
12 

A note about function type signatures

Line 3 in the above example contains the type signature for our function right after the :: after the function name. This specifies that the function takes a String parameter and returns a Bool (a boolean). Parameters and return types are separated by the -> symbol. If there are multiple parameters, they are all separated by -> with the last type being the return type. This is because every function in Haskell is actually a one parameter function. So, when we see a multiple parameter type signature, under the hood we have a series of outer to inner functions – a concept called currying. It is not important to know all about that just yet though if you are just dipping your toes in.

In Haskell there are no mutable variables or for loops but that doesn’t stop us from writing code that looks almost like the imperative Java solution. We define an inner loop function which is called recursively acting like our for loop.

  • On line 5, the where syntax there is a way to give bindings to local values or functions – essentially creating local immutable variables.
  •  On line 8, we define the loop function which takes an immutable counter, i, meaning that the counter is “updated” by passing a new version of the counter value into the loop function every time it is called.
  •  On line 5, the loop function is called with an initial counter, i, argument being the last index of the String – just like we initialised i in the Java solution.
  • The algorithm remains the same. We check the first and last characters. If they are equal, we continue checking the next 2 inner characters and so on. If we find two that are not equal, we can return False straight away and if we get down to only one or no characters remaining, we know we have a palindrome and return True.
  • This divides the end index of the String by 2 so that we can tell we have gotten to a point of 1 or 0 characters left.
  • (div strEndIndex 2)

     

  • This gets the i’th element of a list, in this case, the i’th character in the String str.
  •  (str !! i)

     

  • This is how we compare a character going right to left with its corresponding character going left to right. /= meaning not equal to
  • (str !! i) /= str !! (strEndIndex - i)

     

As shown previously, we can load this into our GHCI and look at it in action.

ghci> :l DipYourToesIn.hs
[1 of 1] Compiling DipYourToesIn    ( DipYourToesIn.hs, interpreted )
Ok, modules loaded: DipYourToesIn.
ghci> isPalindromeWithRecursion "hello"
False
ghci> isPalindromeWithRecursion "racecar"
True
ghci>

Guard those if then elses!

Instead of building up multiple if then elses, Haskell has this lovely construct called Guards. Using, the | symbol, we can build up boolean conditional expressions with corresponding expressions, one of which will be evaluated if its corresponding boolean expression evaluates to true.

13 isPalindromeWithRecursionAndGuard :: String -> Bool
14 isPalindromeWithRecursionAndGuard str =
15   loop strEndIndex where
16 
17     strEndIndex = length str - 1
18     loop i
19       | i <= (div strEndIndex 2) = True
20       | (str !! i) /= str !! (strEndIndex - i) = False
21       | otherwise = loop (i - 1)
22  

Nothing has changed in our underlying algorithm. Also, not much has changed in the code but it is easier to read right? We still have the same set of conditions and corresponding expressions, one of which will be evaluated.

 | i <= (div strEndIndex 2)
| (str !! i) /= str !! (strEndIndex - i)

and

 | otherwise =

otherwise is the default case and its corresponding expression will be evaluated if none of the other boolean expressions have evaluated to True.

A bit about Haskell lists

A List in Haskell is a recursive data structure. A List can be empty and is simply represented as

[]

A List can also be non empty and, in this case, it is represented as a cell containing a value and a link to another List which itself can be empty or contain another cell with a value and a link to a further List. This recursive structure continues until we get an empty list. This is shown in the diagram below.

beginning-haskell-2-001

The cons function in Haskell, represented with a

:

is used to create one of these list cells by joining a value together with an existing List which may or may not be empty. Using this function, we can create the List in the above diagram as follows:

1 : 2 : 3 : []

Haskell has a nicer way though with syntactic sugar allowing us to do the same thing with this bit of code:

[1, 2, 3]

A couple of List operations to help the palindrome cause

Haskell like other functional programming languages has very nice high level operations that we can use on lists. Lets try a couple with GHCI.

First lets create a List and bind it to a name, l. This is done in GHCI using the let keyword but, in Haskell source code, the let isn’t required.

ghci> let l = [1,2,3,4,5]
ghci> l
[1,2,3,4,5]
ghci>

We’re going to need to be able to get the last element in the list so we can compare it to the first element. This is no problem though, we can simply use a function called last.

ghci> last l
5
ghci>

We will also need to get the first element in a list. We will be doing this later by refining the code with pattern matching. However, just for completeness, we do this by using a function called head.

ghci> head l
1
ghci>

Be careful though, calling head on an empty list will give an exception.

ghci> head []
*** Exception: Prelude.head: empty list
ghci>

For reasons that will become apparent soon, we will also need to use a handy function called init. This creates a new list from everything in an existing list except the last value.

ghci> init l
[1,2,3,4]
ghci>

Polishing it off with pattern matching

Pattern matching is a concept very prevalent in functional programming. It allows you specify patterns to match against a data structure, its value type and by the structure and values of its elements. This allows the data structure to be deconstructed and parts of it extracted.

Function arguments are one place where pattern matching can be used very effectively. This is done in Haskell by redefining the function multiple times to deal with the different possible argument value patterns that can be passed in when the function is called.

52 
53 isPalindrome :: String -> Bool
54 isPalindrome [] = True
55 isPalindrome (x : []) = True
56 isPalindrome (x1 : x2 : []) = x1 == x2 -- this line is not necessary, thanks Szymon 
57 isPalindrome (x1 : xs)  = x1 == last xs && isPalindrome (init xs)
58 

  • The final example above uses a mixture of pattern matching and the functions we saw earlier that we can use on lists. A String is a list of characters so we can pattern match on a list argument to the isPalindrome function.
  • Line 54 matches on the empty list. So, if an empty list is passed as an argument to the isPalindrome function, we return True straight away.
  • Line 55 pattern matches on a list with one element. We use the cons function, : , to match on a list structure which contains one cons cell with a value and a link to an empty list. The value of the cons cell can be anything and is bound to the value, x, in the pattern. So, with this pattern, we are checking if the list has only one element and, if it does, we can again return True.
  • Correction, line 56 is not necessary. Thanks for pointing this out Szymon. If a 2 element list has 2 equal values, the init on line 57 will be called on a one element List, xs, returning an empty list and on the next recursive call, line 54 will return True. Line 56 is pattern matching to check if the list argument has only 2 values. We again use the cons function to match against the list structure that we are looking for. We can also bind the first 2 values of the list to the names, x1 and x2. This allows us to check these for equality to determine if the 2 element list is a palindrome.
  • Finally, on line 57, we are back to that piece of code that is likely to make an experienced imperative programmer sigh when trying to get to grips with a functional programming codebase. When pattern matching, the first function expression with a matching pattern for the argument being passed in is the function expression that gets executed. So, if we have gotten this far, there has been no other pattern match so we know that our list argument has more then 2 values. So, now we simply use one cons function to match on a list that has a first element, x1, and a link to the rest of the list, xs. Now we can use our trusty last function to compare x1 to the last element of the list. If they are not equal, we return false as we don’t have a palindrome.
  • However, it they are equal, we need to evaluate the right hand side of the boolean &&. In this case, we literally create a new list made up of all elements of the list minus the first and last element. By calling init on xs, we are omitting the first element, x1, and getting all elements except the last. Then we recursively call isPalindrome on this newly created list so that we can continue checking further and further into the original list until we get to 2 values that are not equal or an empty or 1 element list (after all other outer elements have been “chopped off” so to speak).

Conclusion

I hope all this might encourage more developers to delve into the beautiful language of Haskell. I started dipping my toes in a while back and, pretty quickly, I took the plunge and absolutely love coding in Haskell. I feel at my most relaxed as a developer when I am writing Haskell code. Building up small composable Haskell functions with a type system that protects you but never gets in your way really does lead to a joyful coding experience for me. I will follow up this post with some more dipping of the toes in Haskell to show how we can use the type system to make our isPalindrome function handle lists of any type…well almost any type.

Haskell Flavoured Curry

curry

Reading time: 10 minutes
Currying is a very useful pattern in functional programming. It is a way of breaking up a function which takes multiple parameters in to a chain of outer to inner functions, each of which, takes one parameter. It allows arguments which are known at one point in program execution to be captured and used in a later execution of a function requiring more arguments. In some ways, it’s similar to when an Object is instantiated in OO with one or more property values which are used in later function executions involving that object.

I have found that the subject of currying can be confusing for developers who are new to functional programming. It was for me at the start anyway. I used to try and relate everything back to OO but I discovered that using a substitution model approach based on the Lambda Calculus really simplified things. I won’t go into the specifics of Lambda Calculus here but I’ll give a short example of using a substitution approach in the context of understanding currying.

So, we have a function which transforms a String by prepending a certain number, n, of characters to the start of it returning a new String.

So, in pseudocode this could look like:

prepend(n, c, s) = put n c's at the start of s

Now lets execute this function:

prepend(3, 'z', "Tom")

This would result in

"zzzTom"

This function is completely pure in that it has no observable interaction with its outside context. This is extremely useful because it means that anywhere we see this function called in a program, we can substitute the call arguments into the function’s implementation without changing the meaning of our program. Functional programmers love to say “functional programming is easier to reason about” and this isn’t just a catchphrase. It is this ability to substitute arguments for parameters in expressions, along with all the other functional programming goodness like immutability, that does actually make functional programming easier to reason about.

So, using a simple substitution model, when we call

prepend(3, 'z', "Tom")

in our program, we can replace it with its implementation expression by substituting into it the arguments 3, ‘z’ and “Tom” for the parameters n, c and s respectively.

so

prepend(3, 'z', "Tom")

becomes

put 3 'z' 's at the start of "Tom"

For a curried version of this function we can break it up into three one parameter functions: (I’m using

->

here to separate a function name with its parameter and the function’s expression body – again this is pseudocode)

prependA(n) -> prependB(c) -> prependC(s) -> put n c's at the start of s

Okay, hold a while here! I know this looks kind of weird as we have three functions, starting with the outer prependA function and returning an inner function until we reach the innermost expression. This is where, before, I would have gained initial understanding by thinking about each outer closure returning its inner closure working from the outmost function, prependA to the innermost, prependC – outer to inner functions/closures is the subject of one of my earlier blogs: Closures For OO Developers – 1.
I find that trying to think in this way can start to bend the brain a little bit as higher order functions become more complex. If we look at how this works using the substitution model, things become way easier!

Okay, so lets say we know how many characters we want to prepend to a String but we don’t know what the character is or what the String is just yet. That’s okay!
We can still call our function

prependA(n)

.
So, if n is 3, we call,

prependA(3)

and substituting we 3 for n in its implementation expression, we get

prependB(c) -> prependC(s) -> put 3 c's at the start of s

Okay now, we have a function which can take, as a parameter, the character that we are prepending. At some point, we know that the character we want to prepend is ‘z’, so we call

prependB('z')

substituting z for c in its implementation expression, we get

prependC(s) = put 3 'z' 's at the start of s

Now we have a function which can take a String, s, and prepend three ‘z’ characters to the front of it to produce a new String.

At some point, we find out that the String we want to transform is “Tom” so we call:

prependC("Tom")

Now, we substitute again and this becomes:

put 3 'z' 's at the start of "Tom"

which is back to what we had when we called the original prepend(3, ‘z’, “Tom”)

Haskell likes its Curry

In the above example, I have actually shown, in a simplified way, how the function substitution would work in the Lambda Calculus.
With Haskell being an implementation of the Lambda Calculus, all functions are curried. This doesn’t mean that all functions have to be written as one parameter functions. When a function is declared with multiple parameters, Haskell breaks this up into a series of outer to inner one parameter curried functions underneath the hood. So, our prepend function from above could be declared in Haskell in a way that doesn’t look like its curried.

prepend :: Int -> Char -> String -> String 
prepend n c s = take n (repeat c) ++ s

The expression in the implementation of the prepend function above just says:
take the character, c repeated n times and stick it onto the String s to form a new String (without mutating the original String s).
The type signature is

prepend :: Int -> Char -> String -> String 

Type signatures in Haskell show the curried nature of functions with a series of types separated by

->

with the last being the return type of the function.

The prepend function above takes three parameters, n, c, and s just like the prepend function in our earlier pseudocode. However, just like how I broke this up into a series of outer to inner one parameter functions in the pseudocode, Haskell does this automatically for us.

This allows us to do some really handy stuff!

So, say we want a function to pad a String with a number of characters to the left of the String but we know that we will always want 10 characters. We can declare this as our pad10 function below.

pad10 :: Char -> String -> String 
pad10 = prepend 10

In the above code, we have simply assigned pad10 to prepend but we are only calling the prepend function with one argument, 10. Because the pretend function is automatically curried, when we call pretend 10, we get back another function which takes a character, c which in turn, when called with a character argument, will return the innermost expression which is the expression that actually does the String prepending.

We can continue with this pattern.

So, say we always want to pad a String to the left with 10 white space characters.

pad10WhiteSpaces :: String -> String 
pad10WhiteSpaces = pad10 ' '

In the Haskell code above, we again take advantage of Haskell’s automatic currying and call pad10 with 1 argument, the

' '

character. We can follow a similar substitution to our pseudocode so:

substituting

pad10 ' '

we get

prepend 10 ' '

and substituting this, we get:

take 10 (repeat ' ') ++ s

So when we call

pad10WhiteSpaces "Tom"

this substitutes to

take 10 (repeat ' ') ++ "Tom"

when executed, will produce

"          Tom"

Haskell’s automatic currying can take a bit of getting used to but it makes for beautiful code! It really shines when you want to re-use a multi parameter function to create a function that can only take fewer or even one parameter. For example, if we had a list of Strings and we wanted to produce a list of all the these same String values but with each one padded with 10 spaces. All we need is the original prepend function and this transformation would be as simple as mapping (prepend 10 ‘ ‘) over the list of Strings:

map (prepend 10 ' ') ["I", "like", "curry", "a", "lot"]

Isn’t that handy!

Executing this results in

["          I","          like","          curry","          a","          lot"]

Closures For OO Developers – 2 – FP in an OO Language

Reading Time 5 to 10 minutes

In a previous blog post Closures For OO Developers – 1, I described how I initially thought about closures when I came to Functional Programming. I related an inner closure having access to the environment of the outer closure that created it as being conceptually similar to an inner object having access to the properties of the outer object that created it.

I thought I would back up a bit and show that a closure can really just be thought of as a one method object. There is a quote floating around something like “A Closure is a poor man’s object and visa versa”. I’m not sure of the exact origin of that quote but really the point is that closures and objects are almost the same thing. Closures, in a sense, when thought of as one method objects, bridge the gap between OO programming and functional programming.

It is possible to apply functional programming principles in an object oriented language using closures as one method objects even when the language in question isn’t a fully featured functional programming language. I’m going to take an example of a very common transformation in functional programming – map. This is a function over a data structure which also takes a mapping function as a parameter and applies this mapping function to each element in the data structure to create new data structure elements and, ultimately, a new data structure.

Closures to make OO more Functional

Lets have a look at how this may have been achieved with closures in Java pre Java 8. I will then show the same thing in Java 8 using Java 8 lambdas which are closures.

 
 
    public static <T, U> List<U> map(List<T> list, Mapping<T, U> mapping) { 
 
        List<U> result = new ArrayList<U>(); 
        for (T elem : list) { 
            result.add(mapping.apply(elem)); 
        } 
        return result; 
    } 
 
 
    private interface Mapping<T, U> { 
        U apply(T element); 
    } 
 
    public static void main (String[] args) { 
        List<String> inputList = 
                Arrays.asList("functional", "programming", "with", "closures"); 
 
        Mapping<String, Integer> stringToStringLength = 
          new Mapping<String, Integer>() { 
            public Integer apply(String element) { 
                return element.length(); 
            } 
        }; 
        List<Integer> mappedList = map(inputList, stringToStringLength); 
        System.out.println("Initial List: " + inputList); 
        System.out.println("Mapped List: " + mappedList); 
    }

In the example above, there is a map function which takes a list but it also takes another object as a parameter which will decide how each element in the list will be transformed into a new element for the resulting list. In functional programming, functions are treated as first class values and can be passed as arguments into other functions in the same as any other type of value.

In order to do this in an OO language such as Java pre Java 8, this function argument, mapping, needs to be first wrapped in a one method object. In this case the one method object will be an implementation of the one method interface, Mapping. This interface has one method, apply. The method is essentially the first class function that could be passed around in a functional programming language. An instance of this one method interface can be called a closure. In functional programming, this one method object is represented simply as a function and can also be called a closure.

The main method uses this map function to transform a list of strings into a new list representing the length of each string in the original list. An instance of the Mapping interface is created with an anonymous class. This is the one method object or closure or “function” which is passed as an argument to the map function in order to tell the map function how to transform the list of strings.

Lambdas/Closures in Java 8 – Coating on one Method Objects

Now lets refine the above example a bit to show how, essentially, Java 8 hides this under the covers (but I’m sure it provides optimisations along the way) with its lambda syntax.

 
 
    public static <T, U> List<U> map(List<T> list, Function<T, U> mapping) { 
 
        List<U> result = new ArrayList<U>(); 
        for (T elem : list) { 
            result.add(mapping.apply(elem)); 
        } 
        return result; 
    } 
 
    public static void main (String[] args) { 
        List<String> inputList = 
                Arrays.asList("functional", "programming", "with", "closures"); 
 
        List<Integer> mappedList = map(inputList, s -> s.length()); 
 
        System.out.println("Initial List: " + inputList); 
        System.out.println("Mapped List: " + mappedList); 
    }

In the above example, the Mapping interface is no longer required because Java 8 has a library of one method interfaces, called Functional Interfaces, out of the box. The map function, apart from using the Java 8 Function interface, has remained the same in its implementation. In the main method, instead of having to create and instantiate an anonymous class, we can use a Java 8 lambda which is essentially a function implementation.
s -> s.length()
This is defining a function implementation which takes a String (or anything which has a .length() method and returns an Integer) and returns the length of that String. It can really be thought of as a syntax replacement for the anonymous one method class that we had to declare in the previous example.

Refined more with Java 8 Streams

Using Java 8 streams we can take this further by simply using the map method already available on Java 8 streams. It is typical for any functional programming language to provide this map method out of the box.

 
 
    public static void main (String[] args) { 
        List<String> inputList = 
                Arrays.asList("functional", "programming", "with", "closures"); 
 
        List<Integer> mappedList = inputList.stream().map(s -> s.length()).collect(toList()); 
 
        System.out.println("Initial List: " + inputList); 
        System.out.println("Mapped List: " + mappedList); 
    }

The above example is refined to use Java 8 streams. The whole transformation can now be done in the main method using the map function from the Java 8 API. The lambda which is passed to this function remains unchanged from the one passed to the earlier implementation of map.

Haskell Beauty!!

To finish, here is the same mapping transformation implemented in the fully fledged, pure functional programming language that is Haskell.

map length ["functional", "programming", "with", "closures"]

In the Haskell above, we are simply declaring that we want to map the length function over the list of strings.

Conclusion

Thanks for reading this. I hope this post brought some value to developers looking to move into the functional programming world and also to developers already doing functional programming along with anyone with any other interest in functional programming. Feel free to comment.

Declaring Vs Impering

After years of OO programming,  I had become quite used to the imperative approach to implementing algorithms. One of the beauties of functional programming is that it challenges you to adapt to a different way of thinking and to look at other ways of approaching problem solving, implementing algorithms, and indeed to designing software modules and complete systems.

Imperative programming is all about executing a sequence of steps, each of which, can mutate program state. Declarative programming, on the other hand, is more about declaring what you want a program or component to do with one or more immutable data structures and about linking these declarations together to implement declarations at higher abstraction levels or to form a pipeline of operations on immutable data structures. That difference may seem a bit abstract so lets dive into some code to show what I mean (and maybe learn some Clojure along the way if you are not already familiar with this wonderful language).

Looping

Even something as simple as a looping construct can be enough to show the difference between the imperative and declarative approach.

  
 
    public int sum(int[] nums) { 
        int result = 0; 
        for (int i = 0; i < nums.length; i++) { 
            result += nums[i]; 
        } 
        return result; 
    } 

 

This example is a typical for loop written in Java. The algorithm to sum up an array of numbers is implemented as a sequence of steps which are repeated on the updated mutable variables – the counter variable, i, and the accumulator variable, result.

The Functional Programming approach in implementing this algorithm would be to use recursion to declare the operation to be performed on the array. The following is an example of this declarative approach in Clojure. numbers here is a Vector in Clojure similar to an array.

(defn sum [numbers] 
  (let [go (fn go [numbers result] 
             (if (seq numbers) 
               (go (rest numbers) (+ result (first numbers))) 
               result))] 
    (go numbers 0)))

In the example above, there is an inner function declared called go. This function takes, as parameters, the current immutable state of the numbers collection that it is summing up and also the current immutable result. These arguments are, at runtime, immutable values created for every call to the go function. When executed, this function will return the result if there are no more numbers to process – (seq numbers) returns a falsey value in this case – or else the go function recursively calls itself passing in the rest of the numbers to process along with a new result value calculated from adding the head of the current nums vector to the current result.

Note here that (rest numbers) creates a new immutable Vector with the same numbers except omitting the first number.

Also

(+ result (first numbers))

returns a newly calculated immutable result value.

This implementation can be simplified in Clojure using the loop construct below.

(defn sum-with-loop [numbers] 
  (loop [nums numbers 
         result 0] 
    (if (seq nums) 
      (recur (rest nums) (+ result (first nums))) 
      result)))


In this code, the inner go function is replaced with (loop
which also allows its parameters to be initialized.

(recur..here is a Clojure construct which will recursively execute loop with new arguments. The benefit of using the recur construct in Clojure is that it uses tail recursion. This means that, provided the recursive call is the very last evaluation of the function, the function’s stack frame can be reused for the recursive call meaning that stack overflow can be avoided for large data structures.

Implementing a loop is a reletively low level abstraction but, even at this abstraction level, we can see the difference between the imperative and declarative approach. The imperative for loop uses mutable variables to specify, quite explicitly, a sequence of steps to be implemented. The functional declarative approach uses recursion and more so describes, at a higher level, what we want the program to do. We are literally just saying
“Is the Vector empty? if so just give us back the aggregate but, if not..”
“Produce a new aggregate by adding the top of the list to the current aggregate”
“Now just go ahead and do all that again but with the rest of the Vector as a new Vector…oh and use the new aggregate”.

Declaring At Higher Abstraction Levels

In functional programming, pure functions are composed to create new pure functions. By a pure function, I mean a function which always returns the same output value(s) for the same input value(s) for all possible input values.
So, often in functional programming, there is no need to implement low level recursive loops. Instead functions at higher abstraction levels can be used instead and there are many common functions that are provided in all functional programming languages. The declarative approach really shines when using these higher level functions. Implementations become a lot more concise and readable compared to their corresponding imperative implementations.

Lets look at an example of this. So, say we want to transform a list of numbers into a new list by taking just the even numbers and multiplying them by n.

The following is an imperative approach written in Java – this can be done in a declarative way with Java 8’s functional programming features but the example here is to show the imperative approach that is common in OO programming.

 
 
    public List<Integer> multiplyEvenNumbersBy(List<Integer> nums, int n) { 
        List<Integer> result = new ArrayList<Integer>(); 
 
        for (Integer x : nums){ 
            if(x % 2 == 0) { 
                result.add(x * n); 
            } 
        } 
 
        return result; 
    }

Now, below we implement the same function in a declarative way in Clojure.

(defn multiply-even-numbers-by [nums n] 
  (->> nums (filter even?) (map #(* % n))))

In the declarative approach, we can use these higher abstracted functions called filter and map to declare exactly what we want to do do:

“Give me a sequence of just the even numbers with each one multiplied by n”.

#(* % n) is a shorter way to write anonymous functions in Clojure with % being an argument passed to this one arg function which multiplies its argument by n.

Again everything is immutable in the declarative approach unlike the mutable variables that are used in the imperative approach.

Laziness

The other beauty about the declarative approach using map and filter is that this declarative approach is lazy. It is using lazy sequences in Clojure which are only actually evaluated if they are needed.

(->> nums (filter even?) (map #(* % n)))

The above does not actually immediately produce a new sequence. Instead, it builds up a composition of functions, a functional pipeline, which will be executed to produce elements of this new sequence as they are needed.

For example, lets take a Vector of numbers and, from it, create a new sequence with each number multiplied by 2.
This example is executed directly in the Clojure REPL (read eval print loop console that allows immediate execution of Clojure code.)
It is common to do this in Functional Programming using a utility map function. This takes a data structure and a function to be performed on each element in the data structure in order to produce a new data structure.

(def result (map (fn [x] (println "executing") (* x 2)) [1 2 3]))
=> #'clojure-blogs.core/result

In the above Clojure code, we are declaring that the functional pipeline to map the Vector [1 2 3], into a new sequence, be bound (like ‘assigned to’ in a language with mutable variables) to the Symbol (like a variable) result. A println “executing” side effect (interaction with the function’s outside environment) has been added to the mapping function in order to prove that this function is not executing until one or more elements of the resulting sequence are actually required.
The code above is executed immediately and we can see the result simply prints the the new Symbol with the namespace clojure-blogs.core and name result. The Vector has not yet been transformed and the mapping function has not yet actually been executed. All we have done here is build up a functional pipeline on the original Vector which will be later executed on one element or more elements if their resulting elements are required.

Now, lets actually use result in order to force evaluation of the mapping function and the production of our new Vector.

result 
executing 
executing 
executing 
=> (2 4 6)

In the above code, we reference the result Symbol in the REPL. Now, result needs to be evaluated meaning that the functional pipeline that it references needs to be executed on each element to produce elements of the resulting sequence.
We are transforming every element of the Vector here but we could instead ask for one or more elements at a time meaning that the pipeline is, in turn, executed on each of these elements at a time to produce a new element. We can now clearly see that our map function has been eventually executed 3 times – 1 time for each number in the original Vector.

Conclusion

The declarative approach of Functional Programming can be a bit of a mind shift when coming from a more imperative OO background. It certainly was for me but it was a very positive mind shift. It makes for much more concise code and, in my opinion, it allows us to move up abstraction levels more easily and take on more complex problems without having to keep so much in our head at once.

I would always encourage other developers to stick with what might be a new way of thinking for them as it really can reap great rewards. I know, after years of writing imperative code, seeing more declarative code can seem a bit foreign and it can seem like it will take too long to get to grips with – especially when multiple data transformations like filters and maps are chained together. It is always a good approach to make sure that each of the smaller transformation functions and also the functions passed as parameters to them, are kept small, pure and well named. If it seems like its too much trying to understand a functional pipeline with multiple maps, filters flatMaps etc, I always think…”imagine if this had been written imperatively though and all the extra loops, branches and mutable state I would have to comprehend – all that extra stuff I would have to hold in my head” – I know.. if imperative code is well abstracted and organized, it should be easier to read but, in my opinion, writing declarative code can in itself bring us a step towards code that is easier to read, understand and maintain.

The declarative approach really shines when used in conjunction with laziness – complex functional pipelines that are only executed on an element of a data structure, if it is required for that element to be evaluated. These pipelines don’t even always need to have a tangible data structure to operate on, and can even produce their own data structures one element at a time – this is the concept of infinite sequences which I will get to in an upcoming blog post.

Thanks!

Thanks so much for taking time to read this blog. I really hope it has helped in other peoples’ functional journeys.
Feel free to leave feedback in the comments.

Closures For OO Developers – 1

This is the first in a series of posts that I’m writing about the concept of Closures in Functional Programming (FP for short) and how I related this concept to OO when I first came to FP and how my thinking on the concept has become more “Functional” over time.

When I started making the transition from OO programming to Functional Programming, the concept of a closure was one of the first functional programming concepts that I encountered. I found different explanations and definitions of what a closure actually is, some academic and formal and others more pragmatic. I have asked the question – what is a closure? –  and have been asked this question during interviews and nearly everyone I discuss the concept with has their own take on it.

If you want formal definitions and explanations on closures, the google machine will give you a ton of them.  In this series of blog posts, I want to leave formal definitions aside and show how I related the closure concept to OO programming at first, and how I refined and continue to refine my thinking.

My initial outlook – “closures are like inner classes”?

One way to think about closures when coming from OO, is to think about them in terms of inner classes “inheriting” property definitions from outer classes and, at runtime, “inner” object  instances “inheriting” properties from the outer objects that created them.

Lets take a look at some OO Java code and translate this to functional Scala and then to Clojure  code to show you what I mean. I will also explain the Scala and Clojure code along the way for anyone not familiar with these FP languages.

The Magic Jazz Band Closure

Lets model a Jazz Band that has a property for the tunes that it knows how to play called “setList”. Now, a jazz band isn’t a jazz band without musicians to play together. This is a magic jazz band though. If you want to add another Musician to it, it will simply just create one for you. This musician still needs to have a connection to the band though so it knows everything that musicians in the band should know – like what the set list is for the next gig!

This example is contrived and not the best way to model this type of thing in OO!

jazz band closure
jazz band closure
  • This diagram illustrates a “Parent – Child” or “Outer Object – Inner Object” relationship between a jazz band called “theBop5” and a musician that the jazz band magically created called “tom”.
  • Another way to describe this diagram is that it is a closure. The JazzBand “theBop5” instance “closes over” its state and has created “inner” state in creating Musician “tom”.
  • Musician “tom” has access to the state of the outer instance “theBop5” that created it so “tom” knows what tunes they are playing.
  • Musician “tom” is itself a closure too and any closures it creates will have access to its state and the jazz band closure’s state.
  • As an aside, when I talk about “state” here, in a purely functional approach, this state should be immutable but I will go into more detail on that in later blog posts.

Set the Musician Free – He Needs to Practise!

Its fine for the jazz band to hold on to a musician that it creates so that the musician can play along with the rest of the band. However, musicians need time alone to practice the set list. The jazz band closure will want to be able to set the inner musician closure free but the the musician closure will still need a link back to its “parent” jazz band closure so that it knows the set list it needs to practice!

The following diagram demonstrates how this might work when thinking in terms of inner classes and objects.

returned inner closure with link to parent closure
returned inner closure with link to parent closure

OO Approach – Outer Objects Returning Inner Objects


public class JazzBandTest {

    @Test
    public void bandCreatesMusicianWithAccessToBandSetList() {
        List setList = Arrays.asList("Donna Lee",  "Dig");
        JazzBand theBop5 = new JazzBand(setList);
        JazzBand.Musician tom = theBop5.createMusician();
        assertTrue(setList == tom.getBandSetList());
    }
}

public class JazzBand {

    private List setList;

    public JazzBand(List setList) {
        this.setList = setList;
    }

    public Musician createMusician() {
        return new Musician();
    }

    public class Musician {

        private Musician() {}

        public List getBandSetList() {
            return setList;
        }
    }
}

In the Java example above, there is the outer Java class, JazzBand along with it’s inner class, Musician. At runtime, in the test case above, a new JazzBand object,  theBop5, is created and it is used to create a Musician, tom. The Musician, tom, still has access to the outer object that created it after it has been returned to the test case function with the test asserting that Musician, tom, can access the setList of its outer JazzBand “parent” object and that this setList List object is indeed the same List object as the “parent” object.

FP Approach – Outer Closure Returning Inner Closures

Below is an implementation, in Scala, of the jazz band to musician relationship as an outer function( or closure) to the inner musician closure.

class JazzBandSpec extends FlatSpec with Matchers{

  "Jazz band closure " should " create a musician closure with access to band set list" in {
    val setList = List("Donna Lee", "Dig")
    val jazzBandFunctionThatCreatesMusician: List[String] => () => List[String]
      = JazzBand.jazzBandThatCreatesMusician

    val musicianFunctionThatCanGetBandSetList: () => List[String] 
      = jazzBandFunctionThatCreatesMusician(setList)
    
    musicianFunctionThatCanGetBandSetList() should be (setList)

    //Re-writing the above in a more idiomatic and simplified way
    JazzBand.jazzBandThatCreatesMusician(setList)() should be (setList)
  }
}

package object JazzBand {

  def jazzBandThatCreatesMusician(setList: List[String])
    = () => setList
  
}

In the Scala example above, the test case is deliberately written in a verbose way initially to try and demonstrate exactly what is going on in terms of the outer jazzBandThatCreatesMusician function returning an inner function, musicianFunctionThatCanGetBandSetList. This is re-written in more idiomatic Scala code at the end of the test case (although the function names are still verbose).

The key to understanding this Scala code is knowing the basics of how function/closure (also called lambda) types are defined in Scala. Without going into too much detail, functions can be treated as values in Scala and passed around like any other types of values like Strings, Ints etc. When defining a function value, you declare (or in some cases, Scala infers) the types of the input params and output value like so:

(InputTypeA,  InputTypeB…) => OutputType

e.g specifying

val musicianFunctionThatCanGetBandSetList: () => List[String]

means we are defining a value, musicianFunctionThatCanGetBandSetList to be of type, a Function which takes no parameters and returns a list of Strings.

Function runtime values or “instances” can also be created using the same type of notation except, in this case, we declare the input parameters on the left side of the lambda expression and we declare the function execution on the right side of the lambda expression.

e.g a function to add 2 Ints could be expressed as follows:

(a: Int, b: Int) => a + b

The Int types are usually not needed here as Scala can usually infer Types from the context of the expression.

So, in the Scala example, we can see now that

jazzBandThatCreatesMusician(setList: List[String])

is actually returning a function

 () => setList 

Relating Outer-Inner Objects to Outer-Inner Closures Conceptually

The original diagram modelling the jazz band and musician as an outer to inner object, in an OO approach, and an outer to inner closure in an FP approach still holds true here. The difference in the FP approach is that we are modelling our magic jazz band, which can create musicians, as the outer function taking the setList as a parameter

jazzBandThatCreatesMusician(setList: List[String])

and the inner musician who can still access the jazz band’s set list is returned from this function as an inner function which, on execution, returns the setList just like the

musician.getBandSetList

in the OO approach.

I know, the example is a bit contrived but it is deliberately so to show existing OO knowledge can be leveraged to understand the concept of Closures in FP. I am not claiming that functional programming languages necessarily implement closures like this under the hood; I am just hoping to provide an introduction to closures to developers who are more familiar with OO.

In further blog posts on this, I hope to explain further about closures in FP including things like lexical scoping and how closures can really be thought of more as execution contexts.

Also, this FP approach may seem limiting in that the outer function can only ever return an inner function which can only ever return the setList. This is because the example is modelling an OO approach using FP with closures so as to offer an introduction to closures for OO developers.

Really FP does bring with it a different way of thinking and solving problems. Instead of modelling functionality with objects that expose behaviour (like the JazzBand and Musician) which may or may not operate on encapsulated data structures; FP is all about pulling out those encapsulated data structures, making them immutable and operable on by any number of independent functions that know how to interpret the data structures. So the setList List data structure wouldn’t be encapsulated inside the JazzBand. Instead, it’s more likely that it would be a simple immutable list passed around to any number of functions each of which can operate on it and produce a new data structure as output which may or may not be a List e.g there could be a function addSong which would take the setList and produce a new list structure which would have song values matching the song values in the original setList along with an additional song.

To Finish: The Jazz Band closure implemented in Clojure!

Clojure is a personal favourite of mine for FP languages at the moment. It has great simplicity and elegance, but at the same time, it has all the power of FP.

Below is the Jazz Band to Musician outer-inner closure example implemented in Clojure.


(deftest jazz-band-closure-creates-musician-with-access-to-band-set-list
  (testing
    (is (= ["Donna Lee" "Dig"] ((jazz-band-that-creates-musician ["Donna Lee" "Dig"]))))))

(defn jazz-band-that-creates-musician [set-list] (fn [] set-list))

I know for anyone new to Clojure, it can seem clouded with parenthesis. However, after a short time programming in Clojure, it is easy to start loving the parenthesis especially when you begin to see the consistency and simplicity in the Lisp language syntax. Also, a good IDE, like the Cursive plugin for Intellij, takes full advantages of the parenthesis – for example, on moving the curser to any parenthesis, it automatically highlights this parenthesis and its corresponding starting or ending parenthesis making it easy to examine and refactor blocks of code.

The Clojure implementation is conceptually the same as the earlier Scala implementation. The key to understanding the code is to know that, in Clojure, code is data  – a parenthesis grouping is a list with the first element of the list being treated as a function and the remaining elements its parameters. This makes it very easy to identify our closures. In the test,


((jazz-band-that-creates-musician ["Donna Lee" "Dig"]))

the outer jazz-band-that-creates-musician function (our jazz band closure) gets executed in the inner parenthesis grouping


(jazz-band-that-creates-musician ["Donna Lee" "Dig"])

Like the Scala example, this returns a function representing a musician that returns the band set list when executed. This is our inner musician closure and gets executed because of the extra outer set of parenthesis in the clojure code. It’s like saying


(musician-function-that-can-get-band-set-list)

Also, to understand the function


jazz-band-that-creates-musician

a function is declared at compile time with the syntax


(defn function-name [param-1 param-2....] function-body)

a function implementation can be defined at runtime in Clojure with the syntax


(fn [param-1 param-2...] function-body)

Thanks!

Thanks for taking time to read this blog. I will be following up with more blogs to help introduce FP concepts to developers who are more familiar with OO.