This blog lists key points I noticed while trying to shift gears to Functional Programming using Scala JVM language coming from a traditional Object-oriented programming background for over a decade. I’ve extensively used Coursera’s Scala course and online documentation/blogs to come-up with this content.

### What is Functional programming

Mainstream languages like C, C++, Java etc were based on the idea of *update in place*. They presuppose that the way to solve a programming problem is to have procedures that read and write values to memory locations, be it directly visible to the programmer (by means of pointers) or not.

Other languages, like Lisp, are based on a different assumption: a computation is best expressed as a set of functions over immutable values. So, in order to produce any kind of repetitive computation, *recursion* is essential. This assumption has strong roots in lambda calculus and related mathematical formalisms.

**Function evaluation strategies**

Scala function can be evaluated either Call-by-name or Call-by-value. Call-by-value has the advantage that it evaluates every function argument only once. Call-by-name has the advantage that a function argument is not evaluated if the corresponding parameter is unused in the evaluation of the function body.

Scala uses Call-by-value generally, unless the type of function parameter starts with ‘=>’ in which Call-by-name is used.

**Tail-recursion**

Recursion has been looked-down upon in Imperative style programming but its the basic building block for Functional Programming. Stack-overflow issue still exists if you have too many recursive calls and thats where Tail-recursion comes into play. We can convert any Recursive function into Tail-recursion by using an intermediate function containing an Aggregator. This lets Compiler use the same stack-space for all recursive method calls instead of creating a new one for each Recursive call. Below is an example of **factorial** definition.

1 2 3 |
def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1) |

A tail-recursive solution is as follows:

1 2 3 4 5 6 |
def fact(n: Int): Int = { def loop(acc: Int, n: Int) = if (n == 0) acc else loop(acc*n, n-1) loop(1,n) } |

Note that Recursive functions needs explicit return type declared in function definition whereas its optional for non-recursive types.

**Higher-order functions and Currying**

Functions are first-class citizens which gets treated just like any primitive types, i.e. you can pass it as a parameter to a function, return it from a function and define a var to hold a function.

Currying is when you break down a function that takes multiple arguments into a series of functions that take part of the arguments. Advantage of this is that it offers great amount of expressiveness and reusability to a function. Function arguments associate to the left in context of Currying. Basically, this lets you express your solution just as if you you write a mathematical equation.

We’ll develop motivation for Currying step-by-step:

1 2 3 4 5 6 7 |
def sum(f: Int => Int, a: Int, b: Int) = { def loop(a: Int, acc: Int): Int = if (a > b) acc else loop(a + 1, f(a) + acc) loop(a, 0) } sum(x => x * x, 3, 5) |

1 2 3 4 5 |
def sumInts(a: Int ,b: Int) = sum(x => x, a, b) def sumCubes(a: Int, b: Int) = sum(x => x*x*x, a, b) def sumFactorials(a: Int, b: Int) = sum(fact, a, b) |

Since a and b are getting passed unchanged from **sumInts** and **sumCubes** into sum, we can get their definitions even shorter by getting rid of params as follows:

1 2 3 4 5 6 |
def sum(f: Int => Int): (Int, Int) => Int = { def sumF(a : Int, b: Int): Int = if (a > b) 0 else f(a) + sumF(a + 1, b) sumF } |

Here **sum** is now a function that returns another function. Returned functions **sumF** applies the given function parameter **f** and sums the results. We can now define earlier 3 functions as follows:

1 2 3 4 5 |
def sumInts = sum(x => x) def sumCubes = sum(x => x*x*x) def sumFactorials = sum(fact) |

These functions can in turn be applied like any other function:

1 |
sumCubes(1, 10) + sumFactorials(10, 20) |

In above example, we can avoid **sumInts**, **sumCubes** & **sumFactorials** middlemen as follows:

**sum (cube) (1,10)**

**sum(cube)**applies**sum**to cube and returns ‘sum of cubes’ function**sum(cube)**is therefore equivalent to**sumCubes**- This function is next applied to arguments (1,10)

Generally, function application associates to the left:

**sum (cube)(1,10) **==** (sum (cube)) (1,10)**

The definition of functions that return functions is so useful in functional programming that there is a special syntax for it in Scala. For example, the following definition of sum is equivalent to the one with the nested sumF function, but shorter:

1 2 3 |
def sum(f: Int => Int)(a : Int , b: Int) : Int = if (a> b) 0 else f(a) + sum(f)(a + 1, b) |

Thus** Currying** resembles the process of evaluating a function of multiple variables, when done by hand, on paper as follows:

For example, given the function **f(x,y)=y/x**

- To evaluate
**f(2,3)**, first replace**x**with**2** - Since the result is a function of
**y**, this new function**g(y)**can be defined as**g(y)**=**f(2,y)**=**y/2** - Next, replace the
**y**argument with**3**, producing**g(3)**=**f(2,3)**=**3/2**

On paper, using classical notation, this is usually done all in one step. However, each argument can be replaced sequentially as well. Each replacement results in a function taking exactly one argument. Below is an example where we can use wildcard as a placeholder for unknown param that’ll be provided later:

1 2 3 4 5 6 7 8 |
scala> def concat(w1: String)(w2:String) = w1 + " " +w2 concat: (w1: String)(w2: String)String scala> val hello = concat("hello")_ hello: String => String = scala> hello("world") res0: String = hello world |

Example: MapReduce

Below is screenshot of IDE where **product **function is implemented with Currying principles. **mapReduce **generalizes this further more by supporting any operation like sum, product etc.

With above context, we can re-implement **product** in terms of **mapReduce **as follows**:**

1 |
def product(f: Int => Int)(a: Int, b:Int): Int = mapReduce(f, (x,y) => x*y,1)(a,b) |

**Function**

**Function-type:**

Every function has a type that is declared as `A => B`

(in its simplest form). This function takes argument of type A and returns result of type B.

1 2 3 4 |
def cube(x: Int): Int = x * x * x def sum(f: Int => Int, a:Int, b:Int): Int = if (a>b) 0 else f(a) + sum(f,a+1,b) |

Here **f **is an anonymous function.

We can also declare function type as follows where **MyFunction** is a function-type that takes two Ints and returns a Boolean:

1 |
type MyFunction = (Int,Int) => Boolean |

Note that Function-types associate to right

### Persistent Data-structures:

### Classes:

Scala will create a new Type and a Constructor for every class definition as in below examples

1 |
class Example(x: Int, y:Int) |

1 2 3 4 5 6 7 8 9 |
class Rational(x: Int, y:Int) { def numer = x def denom = y override def toString = numer + "/" } denom } val x = new Rational(1,2) x.numer x.denom |

Functions within Class are called ‘method’s. They differ quiet a bit which we’ll see later.

We can add ‘require‘ method to the class definition to enforce some restrictions on class variables during constructions.

1 2 3 4 |
class Rational(x: Int, y: Int) { require(y > 0, ”denominator must be positive”) ... } |

**Require**is a pre-defined function that takes a condition and an optional message string. An

`IllegalArgumentException`

will be thrown if condition is not met.
Similarly, there exists assert method with same signature which throws a `AssertionError`

.

`require`

enforces pre-condition on caller of function`assert`

checks the function code itself

Every class def introduces an implicit constructor called ‘**primary**‘ constructor that takes all parameters and executes all statements in class body such as ‘require’ etc.

An **Auxiliary** constructor lets us add new constructor by using **this** keyword as shown below. We can define multiple auxiliary constructors.

1 2 3 4 5 6 |
class Rational(x: Int, y:Int) { def this(x: Int) = this (x,1) //the latter refers to primary constructor ... } new Rational(2) //evals to: 2/1 |

Any method with a parameter can be used as an Infix operator such as:

** x.add(y)** can be re-written as

`x add y`

Symbols can be used as Identifiers for Variable or Methods such as +, *&^%, etc

We can define prefix operators like -y by declaring it as unary operator as follows:

1 |
def unary_- : Rational = new Rational (-numer, denom) |

You can create a **singleton** class by replacing “class” identifier with “object”

### Traits

**Traits **lets us achieve multiple inheritance in Scala. They’re similar to Java Interfaces except that Traits can contain method definitions (Java 8 supports methods in Interfaces) It cannot define variable/parameters though.

1 |
class Shape extends Shape with Planar with Movable ... |

We can instantiate Traits using Anonymous classes as follows:

1 2 3 4 5 6 7 8 |
trait Generator[+T] { def generate: T } cal integers = new Generator[Int] { val rand = new java.util.Random def generate = rand.nextInt() } |

We are not instantiating Trait directly, but rather creating a suitable object for the Trait to attach itself to so you can use the Trait’s functionality without needing to define a class that extends the Trait.

### Scala class Hierarchy

All Scala classes automatically import classes belonging to following packages: `scala`

, `java.lang`

and `scala.Predef`

_ is the wildcard in Scala

“Any” is base type of all classes containing methods like ‘==’

“AnyRef” is just alias of java.lang.Object and is the base class of all reference types

“AnyVal” is base type of all primitive types

“Nothing” is sub-type of every other type. It’s used to signal abnormal termination (for eg. ‘throw Exc’ expressionn is used to abort evaluation and its type is Nothing) and, also as element type of empty collections as in Set[Nothing]

“Null” is subtype of every class/ref inherited from Object/Any thus incompatible with AnyVal. Every reference class type also has **null** as a value.

As in Java, Polymorphism is achieved by both sub-classing and generics. Below is an example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
trait List[T] { def isEmpty: Boolean def head: T def tail: Lis[T] } class Cons[T] (val head: T, val tail: List[T]) extends List[T] { def isEmpty = false } class Nil[T] extends List[T] { def isEmpty = true def head = throw new NoSuchElementException("Nil.head") def tail = throw new NoSuchElementException("Nil.tail") } def singleton[T](elem : T) = new Cons[T](elem, new Nil[T]) |

Note that:

- Type parameters doesn’t effect Scala during runtime as it uses
**Type-erasure**(type info is used only by compiler and not preserved for runtime) - If we define a method param as
**val**, it implicitly defines a**val**with same name in method definition - Generics in methods: singleton method can be invoked as follows with the type info:

12singleton[Int](1)singleton[Boolean](true)

Alternatively, we can let Scala deduce type info from the context thus letting us invoke singleton as follows:

12singleton(1)singleton(true) - Above code creates what is called as Immutable linked list. This is fundamental to Functional programming which is constructed using 2 basic elements:

Nil: the empty list

Cons: cell containing an element and remainder of listBelow is graphical representation of Immutable linked lists:

### Functions as Objects

Function-types relates to Classes and function value relate to objects. Functions type `A => B`

is just abbreviation for scala.Function1[A,B] which is define as follows:

1 2 3 4 |
package scala trait Function1[A,B] { def apply(x: A): B } |

There are also traits with Function2, Function3 etc to support upto 22 params.

Anonymous function such as `(x: Int) => x * x`

would be expanded as follows:

1 2 3 4 |
class AnonFun extends Function1[Int, Int] { def apply(x: Int) = x * x } new AnonFun |

This in turn gets converted to as follows using Java anonymous class syntax:

1 2 3 |
new Function1[Int, Int] { def apply(x:Int) = x*x } |

Function calls such as f(a,b) is expanded to `f.apply(a,b)`

. For eg:

1 2 |
val f = (x: Int) => x*x f(7) |

would be translated to:

1 2 3 4 |
val f = new Function1[Int, Int] { def apply(x: Int) = x*x } f.apply(7) |

#### ETA Expansion

Note that method such as `def f(x: Int): Boolean = ...`

is not a function value as it ends in infinite expansion. But when name of method is used in place where function type is expected, then its converted to function value `(x: Int) => f(x)`

which gets expanded as below. This is known as ETA expansion :

1 2 3 |
new Function1[Int, Boolean] { def apply(x: Int) = f(x) } |

This blog has a great explanation about ETA expansion.

In summary, functions and methods are not the same in Scala (although most of the cases we can ignore this difference). A Scala method, as in Java, is a part of class whereas Function is a complete object (instance of class that implement one the Traits Function0,Function1,Function3..)

### Pattern matching

Pattern matching provides a functional way of object decomposition. A case class definition adds feature to pattern match on classes. This modifier adds the benefits of

- add companion ‘object’ singleton declarations for syntactic convenience
- provides concrete subclass with no body
- ‘==’: does a structural equality comparison, i.e two case class instances with same params are equal
- toString: method that gives string representation of class members
- copy(): we can copy whole of a case class instance values into a new instance.
- all params will be declared with ‘val’ by default. Note that if you use currying fashion, only the first param(s) will be provided with ‘val’

Since the concrete sub-class has no body, we will be using Pattern matching using ‘match’ keyword.

For eg,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
trait Expr //declare case classes case class Number(n: Int) extends Expr case class Sum(e1: Expr, e2: Expr) extends Expr //This internally declares Number and Sum singleton objects that //lets us simply invoke Number(2) and Sum(2,3) // object Number { def apply(n: Int) = new Number(n) } // object Sum { def apply(e1: Expr, e2: Expr) = new Sum(e1,e2) //provide implementation for case classes def eval(e: Expr): Int = e match { case Number(n) => n case Sum(e1,e2) => eval(e1) + eval(e2) } |

Note **match** statement execution is sequential as it executes all cases starting from top to bottom one-by-one and skips after a matching case.

A good side-effect of such a matching is that it provides an alternative way to design functions. For example, consider the **factorial** function. If you choose the recursive version, usually, you would define it like this:

1 2 3 |
def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1) |

Where-as a Pattern matching based solution is:

1 2 3 4 |
def fact(n: Int): Int = n match { case 0 => 1 case n => n * fact(n - 1) } |

### Lists

Lists are immutable and are recursive whereas Arrays are mutable and flat.

` val l = List(1,2,3)`

is similar to using Cons (short form for constructor) operator as `1::2::3::Nil`

.

Note that operators ending in ‘:’ are right associative and thus above can be translated as `Nil.::3.::2.::1`

All operations on lists can be expressed in terms of ‘head’, ‘tail’ and ‘isEmpty’

Lists can also be used in pattern matching as follows:

** 1 :: 2 :: xs** Lists starting with 1 and then 2

**or**

`x :: Nil`

**Lists with length 1**

`List(x)`

**or**

`List()`

**Empty list**

`Nil`

**List containing only element as another list that start with 2**

`List(2 :: xs)`

Below is an example of a typical way to decompose lists with pattern-matching using Insertion sort as an example:

1 2 3 4 |
def isort(xs: List[Int]): List[Int] = xs match { case List() => List() //check if list is empty case y :: ys => insert(y, isort(ys)) //if not empty, decompose list into its head and tail and then process } |

More methods on lists `xs.length ; xs.last ; xs.init ; xs take n ; xs drop n ; xs(n) ; xs ++ ys ; ::: (concatenating lists) ; xs.reverse ; xs updated (n, x) ; xs indexof x ; xs contains x`

### Pairs and Tuples

Pairs consisting of x and y is written as (x,y).

`val pair = ("answer",42)`

Type of above pair is (String,Int). Pairs can be used as patterns.

`val (label,pair) = pair`

This returns `label: String = answer, value: Int = 42`

A tuple expression (e1,…,en) is an abbreviation of parameterized type `scala.Tuplen(e1,...,en)`

### Type inference

Consider below code

1 2 3 |
def msort[T](xs: List[T])(lt: (T,T) => Boolean): List[T] = {......} val nums = List(2,4,-1,9) msort(nums)((x: Int,y: Int) => x < y) |

msort call can be re-written to `msort(nums)(x,y)`

as Scala compiler can infer the parameter types of x & y based on type of `nums`

.

### Implicit parameters

1 2 3 4 5 6 7 8 9 |
scala> implicit def v = 7 v: Int scala> implicit var x = 10L x: Long // i is implicit scala> def pp(a:Int)(implicit i:Int) = println(a,i) pp: (a: Int)(implicit i: Int)Unit scala> pp(3) (3,7) |

In above example, Scala compiler searches for **implicit** definition based on below rules:

– is marked ‘implicit’

– has type compatible

– is visible at point of function call or is defined in companion object associated with implicit’s type

### Higher order List functions

Normal List operations include the following:

- transforming each element of a list
- retrieving list of all elements satisfying a criteria
- combining elements of a list

Scala allows generic functions to implement above patterns using **higher-order functions.**

Below is a screenshot of my IntelliJ IDEA workspace with some examples:

#### Reduction of Lists

Common operation on Lists is to combine elements of List with a given operator.

`reduceLeft`

inserts given binary operator between adjacent elements of a list

List(x1,….,xn) reduceLeft op = (…(x1 op x2) op …) op xn

Using reduceLeft, we define sum and product op as follows:

1 2 |
def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x,y) => x + y) def product(xs: List[Int]) = (1 :: xs) reduceLeft ((x,y) => x*y) |

Above ops can be re-written using wildcard pattern as follows

1 2 |
def sum(xs: List[Int]) = (0 :: xs) reduceLeft (_ + _) def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _) |

`foldLeft`

is similar to reduceLeft except for it takes an accumulator as a additional param which will be returned when foldLeft is called on empty list.

1 2 |
def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _) def product(xs: List[Int]) = (xs foldLeft 1) (_ * _) |

foldLeft and foldRight are equivalent (possible differences in efficiency) only if the operators are associative and commutative

### Other Collections

Lists are linear, i.e access to first element is faster than middle or end element.

Scala offers alternative sequence implementation: Vector which is **immutable** and offers more balanced access patterns.

#### When is a List preferred to a Vector ?

**List**: if our operations involve having a Head and Tail of a sequence as these are done at constant-time with Lists whereas its complicated with a Vector

**Vector**: when we need bulk operations like Map, Filter, Fold

Vectors are created analogous to Lists including its operations. Only exception is we’ll replace **::** with **:+**. **x +: xs** creates new Vector with leading element x followed by elements of xs and **+:** creates new Vector with trailing element x preceded by all elements of xs.

#### More functions on Sequences

**xs** **zip** **ys** A sequence of pairs drawn from corresponding elements of sequences **xs** & **ys**

**xs unzip ys** Splits a sequence of pairs xs into two sequences consisting of the first and second half of all pairs.

1 2 3 |
<strong>(1 to 2) flatMap (x => (3 to 4) map (y => (x,y)))</strong> res8: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,3), (1,4), (2,3), (2,4)) |

Above functions lists all combinations of numbers x and y where x is from 1 to 2 and y is from 3 to 4

Below function:

1 |
<strong>def scalarProduct(xs: Vector[Double],ys: Vector[Double]) : Double = (xs zip ys).map(xy => xy._1 * xy._2).sum</strong> |

is equivalent to following def which uses `case`

1 |
<strong>def scalarProduct_WithCase(xs: Vector[Double],ys: Vector[Double]) : Double = (xs zip ys).map{case (x,y) => x * y}.sum</strong> |

Note that `{case p1 => e1, ... case pn => en}`

is same as `x => x match {case p1 => e1 ... case pn => en}`

We can combine Sequence of Sequences using `flatten`

Its also true that `xs flatMap f`

is equal to `(xs map f).flatten`

All collection types share common set of general core methods: `map, flatMap,filter,foldLeft & foldRight`

. Latter two reduces to single value

### For Expressions

Higher-order functions like map,flatMap and filter might make program difficult to understand in which case we can use **for** expressions.

For eg: if `persons`

is a list of elements of class Person with fields `name`

and `age`

,

1 |
case class Person(name: String,age: Int) |

we can obtain names of persons over 20 as follows:

1 |
for (p 20) yield p.name |

which is equivalent to below non-intuitive expression using map.

1 |
persons filter (p=> p.age > 20) map (p => p.name) |

A **for** expression is of the form:

1 |
for (s) yield e |

where s is a sequence of generators and filters and e is expression whose value is returned by an iteration.

We can also use {s} instead of (s) which lets us write sequence of generators and filters in multiple lines without need of semi-colons.

With For expression, we can re-write scalarProduct as follows:

1 |
def scalarProduct(xs: List[Double], ys: List[Double]) : Double = (for ((x,y) |

More examples from Coursera scala course:

1 2 3 |
//given a positive integer n, find all pairs of positive integers (i,j) such that 1 <= j < i < n, and i + j is prime for { i |

1 2 3 4 5 6 7 8 9 10 |
val books: List[Book] = List( Book(title = "Effective Java", author = List("Bloch, Joshua")), Book(title = "Java Puzzlers", author = List("Bloch, Joshua")), Book(title = "Programming in Scala", author = List("Odersky, Martin", "Spoon, Lex", "Venners, Bill"))) //find titles of book whose author name is "Bloch": for (b |

### Sets

`Set`

is written analogous to a sequence:

1 2 |
val fruit = Set("apple","banana","pear") val s = (1 to 6).toSet |

Most ops on sequences are available for Sets as it inherits them from `Iterable`

as follows:

1 2 3 |
s map (_ + 2) fruit filter (_.startsWith == "app") s.nonEmpty |

Differences between Set and Sequence:

- Sets are un-ordered
- No duplicate elements.
`s map (_ / 2) //Set(2,0,3,1)`

- Fundamental operation on Set is contains just as head/tail for Lists and index for Vector

### Maps

Class Map[Key, Value] extends collection type Iterable[(Key, Value)] thus it supports all operations that iterables do.

1 2 |
val capitalOfCountry = Map("US" -> "Washington", "Switzerland" -> "Bern") val countryOfCapital = capitalOfCountry map {case(x,y) => (y,x)} |

Note that maps extends iterables of key/value pairs. So, `key -> value`

is just an alternatetive way of writing `(key, value)`

Class Map[Key, Value] also extends the function type `Key => Value`

so maps can be used anywhere functions can. In particular, it can be applied to key arguments.

Applying a map to a non-existent key gives error:

`capitalOfCountry("Andorra")//java.util.NoSuchElementException: key not found: Andorra`

To query a map without knowing if key exists or not, we can use `get`

which returns a `Option`

value

1 2 |
capitalOfCountry get "US" //Some("Washington") capitalOfCountry get "Andorra" //None |

Since Option classes are case classes, we can decompose them using pattern matching

1 2 3 4 5 |
def showCapital(country: String) = capitalOfCountry.get(country) match { case Some(capital) => capital case None => "missing data" } showCapital("US") //"Washington" |

Maps are partial functions as they could lead to exception if no key found. The operation `withDefaultValue`

turns a map into a total function.

1 2 |
val cap1 = capitalOfCountry withDefaultValue "" cap1("Andorra") //"" |

#### Repeated parameter

For convenience, we can convert below function call:

1 2 3 4 |
def Polynom(val terms: Map[Int, Douoble]) { ... } Polynom(Map(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)) |

to

1 2 3 4 |
def Polynom(bindings: (Int, Double)*) = new Polycom(bindings.toMap withDefaultValue 0) ... Polynom(1 -> 2.0, 3 -> 4.0, 5 -> 6.2) |

Inside Polynom function, binding is seen as a `Seq[(Int,Double)]`

#### sortWith and groupBy

1 2 3 |
val fruit = List("apple","pear","orange","pineapple") fruit sortWith (_.length < _.length)//List("pear","apple","orange","pinepapple") fruit.sorted //List("pear","apple","orange","pinepapple") |

`groupBy`

partitions a collection into a map of collections according to a discriminator function f

1 |
fruit groupBy (_.head) //Map(p -> List(pear,pineapple), a -> List(apple), o -> List(orange)) |