First steps to functional programming with Kotlin

All the code in this post is in:

ArnauG / MasterMindSolver

Exercise to resolve Mastermind code solver

In functional programming all the elements can be understood as functions and the source code can be executed by sequential calls of functions. On the other hand we do not assign values independently. A function can be imagined as a variable of the program. It can be reused and always return a result (it has no side effects).

These are the main characteristics of functional programming:

• Uses Immutable data.
• Focus is on: “What you are doing”
• Supports Parallel Programming
• Its functions have no-side effects
• Flow Control is done using function calls & function calls with recursion
• The program have not state
• Supports both "Abstraction over Data" and "Abstraction over Behaviour".
• It’s easy to combine with imperative programming

Now stop writing and let’s get down to work. To exemplify how to transform a procedural code to functional code I am going to codify a MasterMind solver. Mastermind is a code-breaking game for two players. A code is made up 4 coloured pins and their position. I will use 6 colours (that we will represent with letters from A to F) to choose from and the same colour can be repeated multiple times:

ACDF
AABC

The game play is as follows:

The second player (the one that is guessing) sets out a series of pins in order to guess the code. The first player (that defined the secret code) then provides some feedback to the player in light of how close they are to the correct combination.

The feedback is as follows:

Number of pins that are both the right colour and position
Number of pins that are correct in colour but in the wrong position

Examples:

Secret:  AABC, Guess: ABED, Result: rightPosition: 1, wrongPosition: 1
Secret:  AABC, Guess: ABAD, Result: rightPosition: 1, wrongPosition: 2

Now I am going to show a possible solution using procedural programming:

data class Evaluation(val rightPosition: Int, val wrongPosition: Int)

private const val TOTAL_MASTER_MIND_POSITIONS = 4

fun evaluateGuess(secret: String, guess: String): Evaluation {
  var guessList = guess.toCharArray().toMutableList()
  var secretList = secret.toCharArray().toMutableList()
  var removed: Int = 0
  for (i in 0 until TOTAL_MASTER_MIND_POSITIONS) {
    if (guess[i] == secret[i]) {
      guessList.removeAt(i - removed)
      secretList.removeAt(i - removed)
      removed++
    }
  }

  var rightPosition = TOTAL_MASTER_MIND_POSITIONS - secretList.size
  var wrongPosition: Int = 0

  removed = 0
  for (i in 0 until secretList.size) {
    var currentChar = guessList[i - removed]
    if (secretList.contains(currentChar)) {
      secretList.remove(currentChar)
      guessList.remove(currentChar)
      wrongPosition++
      removed++
    }
  }
  return Evaluation(rightPosition, wrongPosition)
}

In the first part of the code “right position calculation” we check position coincidences and remove the corresponding characters from each array. Then looking at the size of the resultant array we can calculate the number of coincidences. In the second part we do a similar approach passing each time through the remaining secret array.

Now we can start with a functional approach, kotlifying (use kotlin colections api to solve the problem) a little the code. In the code below we can see a possible solution:

// secret: ABCD, guess: AFED
fun evaluateGuess(secret: String, guess: String): Evaluation {
  return secret.zip(guess)
    //[(A,A),(B,F),(C,E),(D,D)]
    .filter { it.first != it.second }
    //[(B,F),(C,E)]
    .unzip()
    //[BC,FE]
    .let {
      var rightPosition = TOTAL_MASTER_MIND_POSITIONS - it.first.size
      generateEvaluationWithNumberOfAppearances(Evaluation(rightPosition, 0), it.first, it.second)
    }
}

private fun generateEvaluationWithNumberOfAppearances(
  evaluation: Evaluation,
  secret: List<Char>,
  guess: List<Char>
): Evaluation =
  guess.firstOrNull()
    .let {
      if (it == null)
        return evaluation
      var position = secret.indexOf(it)
      var secretMutable = secret.toMutableList()//Kotlin list interface not allow mutability
      var wrongPosition = 0
      if (position >= 0) {
        secretMutable.removeAt(position)
        wrongPosition++
      }
      // Flow control using recurrency
      wrongPosition +=
        generateEvaluationWithNumberOfAppearances(evaluation, secretMutable, guess.drop(1)).wrongPosition
      Evaluation(evaluation.rightPosition, wrongPosition)
    } 

To resolve the first part of the problem we use the kotlin api extension for collections. Those are very useful and give the developers a powerful tool to manipulate them. Let’s see what’s going on.

// secret: ABCD, guess: AFED
fun evaluateGuess(secret: String, guess: String): Evaluation {
  return secret.zip(guess)
    //[(A,A),(B,F),(C,E),(D,D)]
    .filter { it.first != it.second }
    //[(B,F),(C,E)]
    .unzip()
    //[BC,FE]
    .let {
      var rightPosition = TOTAL_MASTER_MIND_POSITIONS - it.first.size
      generateEvaluationWithNumberOfAppearances(Evaluation(rightPosition, 0), it.first, it.second)
    }
}

In the second part I choose a different approach to walk through some of the main characteristics of the functional programming paradigm as mutability and Flow control using recurrency. We can see in the example below that the level of abstraction is very similar to the procedural example.

private fun generateEvaluationWithNumberOfAppearances(
  evaluation: Evaluation,
  secret: List<Char>,
  guess: List<Char>
): Evaluation =
  guess.firstOrNull()
    .let {
      if (it == null)
        return evaluation
      var position = secret.indexOf(it)
      var secretMutable = secret.toMutableList()//Kotlin list interface not allow mutability
      var wrongPosition = 0
      if (position >= 0) {
        secretMutable.removeAt(position)
        wrongPosition++
      }
      // Flow control using recurrency
      wrongPosition +=
        generateEvaluationWithNumberOfAppearances(evaluation, secretMutable, guess.drop(1)).wrongPosition
      Evaluation(evaluation.rightPosition, wrongPosition)
    }

To finish I want to show another example that combines imperative and functional programming given us a more elegant code :

// Code extracted from coursera course Java to Kotlin
fun evaluateGuess(secret: String, guess: String): Evaluation {

  val rightPositions = secret.zip(guess).count { it.first == it.second }

  val commonLetters = "ABCDEF".sumBy { ch ->

      Math.min(secret.count { it == ch }, guess.count { it == ch })
  }
  return Evaluation(rightPositions, commonLetters - rightPositions)
}

As we can see using Kotlin API we have a huge versatility that can help us to introduce functional programming with a very little effort. And learning to use this powerful programming language gave us awesome results.

Bibliography:

1.- https://www.coursera.org/learn/kotlin-for-java-developers
2.- https://es.wikipedia.org/wiki/Programación_funcional
3.- https://en.wikipedia.org/wiki/Mastermind_(board_game)