Implementing a functional list

With everything that we've learned in the first two chapters, we can implement a pure functional list:

sealed class FunList<out T> {
   object Nil : FunList<Nothing>()

   data class Cons<out T>(val head: T, val tail: FunList<T>) : FunList<T>()
}

The FunList class is a sealed class; just two possible subclasses exist—Nil, an empty list (in other books you can see this defined as Null or Empty) and Cons (a construct, name inherited from Lisp, that holds two values).

The T type is marked out; this is for variance, which we'll cover variance in future chapters.

Nil is an object (we don't need different instances of Nil) extending FunList<Nothing> (remember that Nothing is the bottom of Kotlin's type hierarchy).

The Cons value contains two values—head, a single T, and tail, a FunList<T>; therefore, it can be a Nil value or another Cons.

Let's create a list instance as follows:

import com.packtpub.functionalkotlin.chapter02.FunList.Cons
import com.packtpub.functionalkotlin.chapter02.FunList.Nil

fun main(args: Array<String>) {
    val numbers = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
}

It's functional, but not very readable. We can create a better initialization function:

import com.packtpub.functionalkotlin.chapter02.FunList.Cons
import com.packtpub.functionalkotlin.chapter02.FunList.Nil

fun intListOf(vararg numbers: Int): FunList<Int> {
   return if (numbers.isEmpty()) {
      Nil
   } else {
      Cons(numbers.first(), intListOf(*numbers.drop(1).toTypedArray().toIntArray()))
   }
}

There are quite a few new things here. The argument numbers are marked as vararg, which means that we can invoke this function with as many parameters as we want. For all intents and purposes, numbers is an IntArray value (a specialized type of array). If numbers is empty, we can return Nil. If not, we can extract the first element as our head value and recursively invoke intLisfOf for the tail value. To extract the tail value, we use the drop method and convert its result to an IntArray value. But we can't directly pass any array as vararg; therefore, we must use the spread (*) operator to pass each member of an array individually. 

Now, we can create our FunList<Int> value:

fun main(args: Array<String>) {
    val numbers = intListOf(1, 2, 3, 4)    
}

Let's implement forEach  as follows:

sealed class FunList<out T> {
   object Nil : FunList<Nothing>()

   data class Cons<out T>(val head: T, val tail: FunList<T>) : FunList<T>()

   fun forEach(f: (T) -> Unit) {
      tailrec fun go(list: FunList<T>, f: (T) -> Unit) {
         when (list) {
            is Cons -> {
               f(list.head)
               go(list.tail, f)
            }
            is Nil -> Unit//Do nothing
         }
      }

      go(this, f)
   }

}

The forEach implementation is similar to our examples of Factorial and Fibonacci functions in the recursion section, including tailrec.

FunList is, technically, an Algebraic Data Type (ADT). FunList can be either a Nil or Cons and nothing else. Kotlin's compiler can use this information to check that both values are evaluated when a FunList type is used as the argument in a when control structure:

fun main(args: Array<String>) {
    val numbers = intListOf(1, 2, 3, 4)
    
    numbers.forEach { i -> println("i = $i") }
}

Implementing fold will be similar to the following code:

sealed class FunList<out T> {
   
  /*Previous code here*/

   fun <R> fold(init: R, f: (R, T) -> R): R {
      tailrec fun go(list: FunList<T>, init: R, f: (R, T) -> R): R = when (list) {
         is Cons -> go(list.tail, f(init, list.head), f)
         is Nil -> init
      }

      return go(this, init, f)
   }
}

Did you notice that these functions are very easy to implement? Let's have a look at the following code:

fun main(args: Array<String>) {
    val numbers = intListOf(1, 2, 3, 4)
    
    val sum = numbers.fold(0) { acc, i -> acc + i}
}

What about a little contest between Kotlin's list and our functional list?

fun main(args: Array<String>) {
    val funList = intListOf(1, 2, 3, 4)
    val list = listOf(1, 2, 3, 4)

    println("fold on funList : ${executionTime { funList.fold(0) { acc, i -> acc + i } }}")
    println("fold on list : ${executionTime { list.fold(0) { acc, i -> acc + i } }}")
}

The output will look something like the following screenshot:

Ouch! Our implementation is 10 times slower. No worries, Kotlin's implementation is a heavily optimized imperative solution and ours is just to learn and have fun (pun intended).

What about map? To implement map in a functional way we need to implement other functions first. Let's start with reverse.

reverse is a function that returns a list in reverse order:

sealed class FunList<out T> {

    /*previous code*/

    fun reverse(): FunList<T> = fold(Nil as FunList<T>) { acc, i -> Cons(i, acc) }
}

We can reuse fold and build a new Cons value in each iteration, using the acc value as tail. This is one of the big advantages of functional programming—reusing existing functions.

Now, we can implement foldRight:

sealed class FunList<out T> {

    /*previous code*/

  fun <R> foldRight(init: R, f: (R, T) -> R): R {
   return this.reverse().fold(init, f)
  }
}

Again, we are reusing existing functions. It is time to implement our map function. At this point, it is not surprising that we'll reuse our existing functions:

sealed class FunList<out T> {

 /*previous code*

 fun <R> map(f:(T) -> R): FunList<R> {
   return foldRight(Nil as FunList<R>){ tail, head -> Cons(f(head), tail) }
 }
}

foldRight is all that we need. As you can see, we can implement a complete list using functions and other basic concepts as building blocks. And that is all about functional programming.