Functional Programming: Repetition and Data

Repetition in Functional Programming

• Achieved through recursion, where a function calls itself.
• Compilers can optimize recursive code for performance.
• Scala function definition syntax: def fnName(v1: Type1, v2: Type2, ..., vN: TypeN): RetType = { ... }
• Return type is optional unless the function is recursive.
• Example function fooBar taking an integer and computing 2x + 5: def fooBar(x: Int) = 2*x + 5
• Recursive functions require explicit return type specification.
• Example recursive function pow(x, y) calculates x to the power of y: def pow(x: Int, y: Int): Int = if (y == 0) 1 else pow(x, y-1)*x
• Functions can refer to previously defined functions.
• Recursion is a powerful construct.
• Defining a function binds an expression to a name, without immediate execution.

Compound Data Structures

• Tuples: fixed size, elements can have different types.
• Lists: variable size, elements must have the same type.

Tuples

• Simplest tuple is a pair: (e1, e2)
• Example: ("hello", 42) is of type (String, Int).
• Value of a pair (e1, e2) evaluates to (v1, v2) if e1 evaluates to v1 and e2 evaluates to v2.
• Type of a pair (e1, e2) is (T1, T2) if e1 is of type T1 and e2 is of type T2.
• Access components of a tuple t using t._1, t._2, etc.
• Unpacking a pair using val: val (st, num) = t
• Functions can take and return pairs.
• Example:
  • def swap(p: (String, Int)) = (p._2, p._1)
• Create k-tuples: (e1, e2, e3, ..., ek)
  • Value: If e1 evaluates to v1, ..., ek evaluates to vk, the tuple evaluates to (v1, v2, ..., vk).
  • Type: If e1 is of type T1, ..., ek is of type Tk, the tuple is of type (T1, T2, ..., Tk).
• Tuple nesting is allowed.

Lists

• Lists allow for a variable amount of data, unlike tuples
• Lists are front-access lists by default in Scala.
• Front-access lists are immutable, and modifications create new lists.
• Cons list: a front-access linked list
  • Nil is the empty list.
  • h::t creates a new list with element h cons-ed with list t.
  • Does not mutate the existing list.
  • Cons-ing an element is constant time.
• Front of the list is efficient to work with.
• Accessing the k-th position requires walking k steps.
• List concatenation is expensive.

Working with Scala Lists

• Create empty list: List() or Nil which is of type List[Nothing].
• Force a List of Ints: List(): List[Int]
• Create a list with elements: List(3,1,4,1,5) which is of type List[Int].
• e1 :: e2 adds element e1 to the front of list e2, resulting in a new list of type List[T].
• Example:
  • val lst = List("is", "awesome")
  • val brag = "cs"::lst
  • brag is of type List[String]
• Check if a list l is empty using l.isEmpty.
• Access the head of a list l using l.head.
• Access the tail of a list l using l.tail.
• Examples:
  • def sumList(xs: List[Int]): Int = if (xs.isEmpty) 0 else xs.head + sumList(xs.tail)
  • def descRange(n: Int): List[Int] = if (n==0) Nil else n::descRange(n-1)
  • def concat(xs: List[Int], ys: List[Int]): List[Int] = if (xs.isEmpty) ys else (xs.head)::concat(xs.tail, ys)

Pattern Matching

• Advanced form of switch statement.
• Syntax: selector match { alternatives }
• Example:
  • def sumList(xs: List[Int]): Int = xs match { case Nil => 0 case h::t => h + sumList(t) }
• Pattern matching is preferred.
  • The compiler warns of missing cases.
  • The compiler warns of duplicate cases.

Combining Tuples and Lists

• Form a list of pairs: List((1,2), (3,-1), (2, 5))
• Pattern matching can extract the head and break down tuples.
• Example:

xs match {
  // other cases omitted
  case (number, name)::t =>...
}

Recursion, Shadow, Style

• A function produces a list [1, 2, 3, ..., n].
• Example:

def countUpFrom1(n: Int): List[Int] = {
def count(from: Int, to: Int): List[Int] =
if (from == to) Nil else from :: count(from+1, to)
count(1, n)
}

• Helper functions should be defined inside the functions they help if they are unlikely to be used elsewhere, likely to be misused if available elsewhere or likely to be changed or removed later.

(In-class) Exercises

• sumPairList(xs: List[(Int, Int)]): Int adds up all the numbers.
  • sumPairList(List((5,2), (1,4), (2, 7))) ==> 21 // 5+2+1+4+2+7
• firsts(xs: List[(Int, Int)]): List[Int] returns a list of first coordinates.
  • firsts(List((5,2), (1,4), (2, 7))) ==> List(5, 1, 2)
• seconds(xs: List[(Int, Int)]): List[Int] returns a list of second coordinates.
  • seconds(List((5,2), (1,4), (2, 7))) ==> List(2, 4, 7)
• pairSumList(xs: List[(Int, Int)]): (Int, Int) returns a pair with the sum of first coordinates and the sum of second coordinates.
  • pairSumList(List((5,2), (1,4), (2, 7))) ==> (8, 13) // 5+1+2 and 2+4+7