Notes on Functional Programming in Scala

this post gets continuously updated

• Functional programming is a programming paradigm that is based on the idea of treating computation as the evaluation of mathematical functions. Functional languages treat functions as first-class values, which means that they can be passed as arguments to other functions, returned as values from functions, and assigned to variables.
• Pure function: A function \(f\) with the input type \(A\) and output type \(B\) is a computation that relates every value \(a\) of type \(A\) to exactly one value \(b\) of type \(B\) such that \(b\) is determined solely by the value of \(a\). Think of an injective(one-to-one) function in Mathematics. For example a function that returns the next integer.

The equivalent Scala code looks like:

def f(x: Int): Int = x+1

• Side effects: modification of the state outside of the local scope.
• Referential transparency:  A piece of code is referentially transparent if we can safely replace that piece of code with the value it computes and vice-versa, anywhere where that piece is used, without changing the meaning or result of our program.
• Higher order function does at least one of the following two:
  • Take one or more functions as an argument
  • Returns a function as it’s result
• tail recursion: A tail recursive function calls itself as its last action. Can be optimized by reusing the using the stack frame. Represents an iterative process. In Scala it can be annotated with @tailrec so that the compiler will succeed only if the function is indeed tail recursive. Refer Tail Recursion Explained - Computerphile

// function to get the nth Fibonacci number
def fib(n: Int): Int = {
  @tailrec
  def loop(n1: Int, n2: Int, i: Int): Int = {
    if (i == n) n1
    else loop(n2, n1+n2, i+1) // <- tail call
  }

  loop(0, 1, 0)
}

• monomorphic function: is a function that operates only on one datatype

• polymorphic/generic function: A generic function is a function that is declared with type parameters. When called, actual types are used instead of the type parameters.

• anonymous function: Inline functions that can be defined without a name. Also known as lambda function, or function literal.

Following code snippet is an example for polymorphic function (since it is generic over the data type A) and higher order function (since the second parameter it takes has to be a function).

def findFirst[A](as: Array[A], p: A => Boolean): Int = {
  @tailrec
  def loop(n: Int): Int = {
    if (n >= as.length) -1
    else if (p(as(n))) n
    else loop(n+1)          // <- tail call
  }

  loop(0)
}

// the 'x => x == 5' is an anonymous function
findFirst[Int](Array(1,2,3,4,5), x => x == 5) //4

findFirst[String](Array("a", "b", "c"), x => x == "c") //2

Another example of anonymous functions

val square: Int => Int = x => x * x
// OR
val square = (x:Int) => x * x

square(2) // 4
square(3) // 9

• Call-by-value, also known as strict evaluation, evaluates the function arguments before the function is applied. This means that the arguments are evaluated regardless of whether they are actually used by the function. Here is an example of call-by-value in Scala:

def square(x: Int): Int = x * x

val result = square(2 + 2)

In this code, the square function takes an Int argument and returns the square of that argument. When the square function is called with the argument 2 + 2, the argument is evaluated first, and the result is 4. Then, the square function is applied to the value 4, and the result is 16.

• Call-by-name evaluates the function arguments only if and when they are used by the function. This means that the arguments are only evaluated if they are actually needed to compute the result of the function. Here is an example of call-by-name in Scala:

def square(x: => Int): Int = x * x

val result = square(2 + 2)

In this code, the square function takes an Int argument, but the argument is preceded by the => symbol. This indicates that the argument is evaluated by-name, rather than by-value. When the square function is called with the argument 2 + 2, the argument is not immediately evaluated. Instead, the square function is applied to the unevaluated argument 2 + 2, and the result is 4 * 4 or 16.

• Data Abstraction: The ability to choose different implementations of the data without affecting clients.