Functional Scala

Page content

Tail calls and tail-call optimizations:

A recursion is called tail call recursion which occurs when a function calls itself as its final operation.

Easiest way to optimize by conversion into a loop. Loops eliminates the potential of stack overflow.

The tail-call optimization won’t be applied when a method that calls itself might be overridden in a derived type. The method must be private or final defined in an object or nested in another method(like fact). @tailrec annotation will trigger an error if the compiler can’t optimize the annotated method.

Trampoline for tail calls:

is a loop that works through a list of functions calling each one in turn. A kind of recursion where funA -> funB -> funA -> funB .. this type of back and forth recusion can also be converted into a loop using a trampoline.

Functional data structures

1. Lists in fn prg:

Appending elements to a list creates a new list.

val list1 = List("Scala","Haskell") val list2 = "Some"::"New21"::list1

  • scala also provide immutable list types such as ListBuffer and LinkedList *

2. Maps

  • referred to as hash or dictionary in other languages.
  • do not confuse it with * map * function.
  • there are derived types of immutable and mutable maps which define + and - operators for adding and removing elements. ++ and – for removing elements defined in Iterators of Pairs.

3. Sets

  • unique lists. doesn’t allow duplicates

4. Other data structures in fn prg:

  • Tuples and arrays are used just for convenience but they can be replaced with lists.

Traversing, Mapping, Filtering, Folding and Reducing:

Traversal:(foreach)

List(1,2,3,4,5) foreach { i => println(i) }

Mapping: map

val map2 = states map { kv => (kv._1, kv._2.length) } val lengths = Map[String,Int]() ++ map2

flatMap:

used to flatten a hierarchial data structure, remove empty elements etc. unlike map it may not return a new collection of the same size as the original collection.

Filtering: filter

Other common filtering methods are: drop(n:Int) - drops the first n elements

dropWhile(p:(A) => Boolean) - returns the longest suffix of this iterable whose first elements does not satisfy the predicate p.

exists(p: (A) => Boolean) - apply a predicate p to all elements of this iterable and return true if there is atleast 1 element yields true. *

filter, find, findIndexOf - returns index or -1* *forall(p: (A) => Boolean):Boolean* - apply a predicate p to all elements of this iterable object and return true if the predicate yields true for all elements.

indexOf - returns the index of the 1st occurence of the specified object in the iterable object

partition(p:(A) => Boolean) - partition this iterable in 2 iterables according to a predicate.

sameElements[ B >: A ](that: Iterable[B]): Boolean - checks if the other iterable contains the same elements

take(n:Int): Collection[A] - takes the first n elements of this iterable*

takeWhile(p:(A) => Boolean):Iterable[A] - returns the longest prefix of this iterable whose elements satisfy this predicate*

Folding and reducing:

both are operaions for shrinking a collection down to a smaller collection or a single value.

Option container:

Option container supports filter, map, flatMap and other functionally oriented methods that are applied only of if the option isn’t empty(i.e if its a Some and not a None).

Partial functions:

  • are expressions in which not all arguments defined in a fn are supplied as parameters to the function.

Currying

transforms a function that takes multiple parameters into a chain of functions each taking a single parameter.

def cat(s1:String)(s2:String) = s1+s2

We can also convert a fn that take multiple parameters into a curried form using Function.curried

Implicits:

When you have an instance of one type and you need to use it in a context where a different but a similar type is required. In general case you might have an automated conversion mechanism.