Functional way of finding the max element in an array

 Finding the maximum element of an array is a relatively easy problem. An imperative solution would be to choose the first element as the max and then go through the rest of the array and assign the current element to the max if the current element is larger than the current max. In the end, the max variable will contain the max value of the array. 

But we are here to learn about Scala and functional programming so mutating a variable is not what we want to do. Also, we do not want to go through the array using a loop because a loop counter is also variable, in functional programming we usually implement loops or in general iterations using recursion.

So let's see how we would implement a function with the following signature for finding the max value of a given array (or List):

def maxValue(elements: List[Int]): Int = ???

For implementing recursion we can define a nested function inside our maxValue function which takes 2 parameters, one int which is the current max value, and one list which is the rest of the list. So the signature of the nested function for the recursive call is like this:

def loop(max: Int, elements: List[Int]): Int = ???

This function should have a base case that returns and some other cases to call itself.

    def loop(max: Int, elements: List[Int]): Int = {
      if (elements.isEmpty) max
      else if (elements.head > max) loop(elements.head, elements.tail)
      else loop(max, elements.tail)
    }

And the main function we only need to call this loop function with the initial list's head and tail. Meaning that initially, we consider that the first element of the list is the maximum value. We also assume the initial list is not empty, otherwise our function crashes!

So the complete function is like this:

  def maxValue(elements: List[Int]): Int = {

    def loop(max: Int, elements: List[Int]): Int = {
      if (elements.isEmpty) max
      else if (elements.head > max) loop(elements.head, elements.tail)
      else loop(max, elements.tail)
    }

    loop(elements.head, elements.tail)
  }

There are 2 things that we can improve on this function:

1. It can not take an empty list
2. It only works with a list of Int

First improvement, empty list thingy

We can fix this issue with 2 different approaches

1. Fix it in the method signature
2. Fix it in the method body

Fixing the method signature has the advantage that we keep this concern completely separate from our implementation, which means we do not add anything to our implementation, but it comes to the price of having a new type, in this case, NonEmptyList, available. We actually have this class available as it comes with the cats library. So we can simply change our method signature like this and we are good to go.

def maxValue(elements: NonEmptyList[Int]): Int = ???

Do not change the signature of the loop function, it might receive an empty list and it is crucial for the base case.

If we can't change our function's signature, then we should handle this case in the function's body. Simply we should check if the receiving list is empty at first and if it is, we should throw an Exception (I don't like this as throwing Exceptions is not a really functional way of raising a flag) or we can return a specific value, such as Int.MinValue but that's not great either. We can change the return type of our function to return Either of Throwable or Int, as follows (return type is not part of the function signature, although it is a contract change):

def maxValue(elements: List[Int]): Either[Throwable, Int] = ???

And the implementation as:

  def maxValue(elements: List[Int]): Either[Throwable, Int] = {
    def loop(max: Int, elements: List[Int]): Int = {
      if (elements.isEmpty) max
      else if (elements.head > max) loop(elements.head, elements.tail)
      else loop(max, elements.tail)
    }

    elements match {
      case Nil => Left(IllegalArgumentException("the list is empty"))
      case head :: tail => Right(loop(head, tail))
    }
  }

Cool, we did the first improvement. Let's fix the second issue, which is the fact our function is too specific. It can only take a List of Int. Finding the maximum value of a given list should be the same for any comparable list. So let's fix this by means of generic programming. 

The trait that provides comparability in Scala is Ordering trait, so we can write our method as follows as long as there is an implicit Ordering value in scope. 

  def maxValue[A](elements: NonEmptyList[A])(implicit ordering: Ordering[A]): A = {
    def loop(max: A, elements: List[A]): A = {
      if (elements.isEmpty) max
      else loop(ordering.max(max, elements.head), elements.tail)
    }

    loop(elements.head, elements.tail)
  }

And we can test it using a list of Int because an implicit Ordering value is always in scope for Int:

  def main(args: Array[String]): Unit = {
    val l = NonEmptyList(51, List(22, 3, 9))

    println(maxValue(l))
  }