All posts by Tom Prior

Persist the List

A few years ago now, I developed a bit of a thing for functional programming. I explored a few different functional programming languages including Clojure, Haskell, Scala and F#. I’ve used Scala professionally and continue to do so to some extent in my current role. I also went full on into F# for 18 months and luckily found a job where I could use it professionally. These days I am back developing software mainly with JVM languages and technologies and mainly using Kotlin both professionally and for spare time coding fun.

I prefer now to mix OO and functional programming paradigms as I believe they complement each other well and Kotlin is a wonderful language for this. It has great tooling and great language features providing all the type safety I need along with concise ways to express common OO and functional programming patterns and data transformations.

When first coming to Kotlin, one feature I soon missed from languages like Scala, F# and Clojure is fully immutable data structures in the language’s standard library. Kotlin does have read-only collection interfaces and differentiates these from mutable interfaces. For example the following creates an implementation of the List interface in Kotlin. This interface doesn’t provide any methods that would allow a client of the interface to modify the underlying list.

val readOnlyList: List<Int> = listOf(1, 2, 3, 4)

The list type declaration (List<Int>) is optional as Kotlin can infer the type but I have it in the snippet to show the interface that is returned from the call to listOf.

A mutable list can be created in Kotlin as follows:

val mutableList: MutableList<Int> = mutableListOf(4, 5, 6)

The interface is called MutableList and it provides methods to modify the underlying list implementation. When compiling Kotlin to target the JVM, the underlying list implementations that are created are standard java ArrayLists. The read-only List interface offers some protection against the underlying list implementation being mutated. However, because the underlying list implementation is still a Java mutable list, it is possible for it to be mutated from elsewhere in the code as the following snippet demonstrates:

fun main(args: Array<String>) {
val mutableList: MutableList<Int> = mutableListOf(4, 5, 6)
val listNotToBeAmended: List<Int> = mutableList
println("listNotToBeAmended before add: $listNotToBeAmended")
mutableList.add(3)
println("listNotToBeAmended after add to underlying list: $listNotToBeAmended")
}

This prints the following:

listNotToBeAmended before add: [4, 5, 6]
listNotToBeAmended after add to underlying list: [4, 5, 6, 3]

At first, this really made me miss fully immutable data structures from, say, Scala. However, good code encapsulation and defensive copies can prevent the types of errors in
the above code snippet from arising. I find Kotlin read-only interfaces are good enough most of the time and reap great rewards in terms of ease of interoperability with Java and Java libraries. So fully immutable data structures aren’t a deal breaker for me using and thoroughly enjoying using Kotlin. They are more a “would be really nice to have” feature for me now.

I first came to functional programming with fully immutable data structures when first using languages like Scala and Clojure about 4 years ago now. At the time I wondered how these data structures could be performant. Most of my development experience up until that time had been with OO, imperative languages like Java. I was imagining that in order to program with immutable data structures, one would have to be constantly making copies of an entire data structure that one wanted to “update”. I soon learned that this wasn’t necessarily the case because of what are called “persistent data structures”.

Persistent Data Structures

Persistent data structures allow multiple versions of a data structure to share parts of their underlying structure. So, for example, let’s say we have a list called myList1 that is fully immutable. Now let’s say we want to update this list by pre-pending one element to the head (first element) of the list. The list myList1 is fully immutable but that doesn’t mean that we can’t use its structure to create a new list with one extra element prepended to it called myList2. myList1 doesn’t know anything about the element that was prepended to it. Its head remains the same element that it always was. myList2 has a different head element but the rest of myList2 is exactly the same as myList1. So, in order to “update” myList1, there was no copying required. The diagram below depicts this:

One might say, “well that’s just a linked list and that’s what happens when you prepend something to a linked list”. However there is a difference. When programming with mutable, imperative data structures, the underlying data structure is encapsulated behind an ADT. ADT in this context stands for Abstract Data Type. Operations such as addFirst(myElement) are exposed as the List abstract data type’s interface. The underlying representation is hidden and, when prepending an element to the start of it, it is mutated with, in the case of a linked list implementation, the head private field being mutated to point to a node containing the new first element and that node pointing to the original first node. In the case of the underlying implementation being an array, the new first element needs to be inserted as the first element in the array or as the last filled element in the array depending on the choice of representation. There is no data sharing – instead there is only one version of the list that has become mutated.

This becomes more apparent if we consider a standard functional programming transformation such as:

fun dropWhile(list: List<Int>, f: (Int) -> Boolean)

The List in the above function is not a List from the Kotlin standard library. Instead it is a persistent list. This function uses the list that gets passed to it to construct a new version by essentially skipping all elements of the original that satisfy the predicate.Its head element is then the first element of the original that doesn’t satisfy the predicate and the rest of the elements in the original list are shared to make up the new list. Again, this can be shown better with a diagram:

Persistent list as an Algebraic Data Type

Earlier I described the List interface in Java and other imperative languages as an ADT meaning an Abstract Data Type. When considering how to go about implementing a persistent list in Kotlin, it helps to think about it as an ADT except that, in this context, ADT stands for Algebraic Data Type. In a previous blog post I gave a small intro to the concept of algebraic data types and showed how they can be used in Scala to prevent illegal states occurring in one’s code. When implementing a persistent list, instead of thinking of the List as an abstract data type with its representation encapsulated, it is easier to see it for what it is which is an algebraic data type. It has a type constructor meaning that one can construct different List types which hold different types of elements and it has only 2 data constructors. One data constructor creates an empty list – let’s just call that Empty. The other constructs a data value containing an element AND a list. This is often called Cons. One can think of the Cons constructor as a constructer which prepends an element to a list to create a new list. In this way the list algebraic data type is recursive. The diagram below depicts the constructing of 3 lists starting with an empty list and shows the recursive nature of the List algebraic data type.

Persisting the List in Kotlin

The code below shows one way to represent the List algebraic data type in Kotlin.

sealed class List<out E>
object Empty: List<Nothing>() {
override fun toString()= "[]"
}
data class Cons<E>(val head: E, val tail: List<E>): List<E>() {
override fun toString(): String = "$head :: $tail"
}
fun main() {
val myList1 = Empty
val myList2 = Cons(1, myList1)
val myList3 = Cons(2, myList2)
println("myList1: $myList1")
println("myList2: $myList2")
println("myList3: $myList3")
}

In the code above, the List algebraic data type is represented as a sealed class that can only ever have 2 implementations. Marking a class as sealed in Kotlin is a way of telling the Kotlin compiler that every subclass of the sealed class will be declared in the same file that the sealed class is declared in. In this way we can guarantee that a List can only ever be constructed to be an Empty list as declared by the object singleton subtype of List called Empty OR it can be constructed using the Cons data constructor with Cons being the other subtype of the List sealed class. The Cons data constructor creates a list by combining a head element AND an existing list. I have capitalised the words “AND” and “OR” in the previous two sentences to highlight that the List type is an algebraic data type – it is an OR type or “discriminated union” with its Cons data constructor being an “AND” type or “product type”.

In the main function in the above code we create three lists just like the ones represented in the previous diagram. Each list is represented by pre-pending (or “consing”) a head element to an existing list to create a new list. It can be seen that myList2 and myList3 share part of their structures with each other and with myList1. As myList1 is the singleton Empty list, its structure will be shared with any other brand new list that is ever created. The toString function is overridden for both the Empty implementation and the Cons implementation so that the list representation prints nicely in the console. Running the main function above produces the following output.

myList1: []
myList2: 1 :: []
myList3: 2 :: 1 :: []

Transformations

All the common functional transformations one would expect can be implemented on the persistent list represented in the above code. It’s usually best to implement what are called foldLeft and foldRight functions and then implement other transformations in terms of these. However to show these and all the common List transformations in here would result in quite a long blog post. To see these in action and to learn more about persistent data structures and their implementations in Scala and Kotlin, I highly recommend studying two fantastic books:
Functional Programming in Scala by Paul Chiusano and Rúnar Bjarnason
The Joy of Kotlin by Pierre-Yves Saumont

Both of these books are full of practical exercises for the reader to build persistent data structures for themselves. They are both well worth the time and effort needed to go through all of their exercises.

To finish off this post though, let’s look at an example of one transformation – an implementation of the dropWhile function that I talked about and depicted in an earlier diagram.

fun <E> dropWhile(list: List<E>, f: (E) -> Boolean): List<E> =
when(list) {
Empty -> Empty
is Cons -> if (f(list.head)) dropWhile(list.tail, f) else list
}
fun main() {
val myList = Cons(1, Cons(2, Cons(3, Cons(4, Empty))))
dropWhile(myList) { it < 3 }.let(::println)
dropWhile(myList) { it < 1 }.let(::println)
dropWhile(myList) { it < 10 }.let(::println)
}

The output of the above is:

3 :: 4 :: []
1 :: 2 :: 3 :: 4 :: []
[]

The recursive nature of the List persistent data structure lends itself very well to a naturally recursive implementation of dropWhile. Often implementing operations over a persistent list recursively can lead to a stack overflow for large lists. Luckily Kotlin supports tail recursion. This is where the last expression to be evaluated in the a function is the recursive call to the function itself allowing the current stack frame to be re-used. The above solution is actually tail recursive because the else part of the if does not need to be evaluated if the predicate returns true. So whenever the recursive call is made, it is the last expression to be evaluated. We still need to tell Kotlin that we intend the function to be tail recursive by adding the tailrec keyword as below:

tailrec fun <E> dropWhile(list: List<E>, f: (E) -> Boolean): List<E> =
when(list) {
Empty -> Empty
is Cons -> if (f(list.head)) dropWhile(list.tail, f) else list
}

Unfortunately it’s not always as easy as simply adding the tailrec keyword. Often the implementation needs to change in order for a non tail recursive function to become tail recursive. This usually involves using an inner function or an auxiliary function to perform what can can be thought of as a loop only without any mutation. An example using this approach is shown below:

fun <E> dropWhile(list: List<E>, f: (E) -> Boolean): List<E> {
tailrec fun loop(remaining: List<E>): List<E> =
when(remaining) {
is Empty -> remaining
is Cons -> if (f(remaining.head)) loop(remaining.tail) else remaining
}
return loop(list)
}

Conclusion

I hope this has served as an intro to persistent data structures and, in particular, the list persistent data structure. Whether they become part of the Kotlin standard library, time will tell but, either way, Kotlin is a beautiful and extremely practical and productive language that I love to use!

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 List map(List list, Mapping mapping) {
List result = new ArrayList();
for (T elem : list) {
result.add(mapping.apply(elem));
}
return result;
}
private interface Mapping {
U apply(T element);
}
public static void main (String[] args) {
List inputList =
Arrays.asList("functional", "programming", "with", "closures");
Mapping stringToStringLength =
new Mapping() {
public Integer apply(String element) {
return element.length();
}
};
List 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 List map(List list, Function mapping) {
List result = new ArrayList();
for (T elem : list) {
result.add(mapping.apply(elem));
}
return result;
}
public static void main (String[] args) {
List inputList =
Arrays.asList("functional", "programming", "with", "closures");
List 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 inputList =
Arrays.asList("functional", "programming", "with", "closures");
List 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.

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!

  • 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.

diagrams-2.002

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
}


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

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.