ScalaFunctional.md

object Lists {

  /**
   * This method computes the sum of all elements in the list xs. There are
   * multiple techniques that can be used for implementing this method, and
   * you will learn during the class.
   *
   * For this example assignment you can use the following methods in class
   * `List`:
   *
   *  - `xs.isEmpty: Boolean` returns `true` if the list `xs` is empty
   *  - `xs.head: Int` returns the head element of the list `xs`. If the list
   *    is empty an exception is thrown
   *  - `xs.tail: List[Int]` returns the tail of the list `xs`, i.e. the the
   *    list `xs` without its `head` element
   *
   *  ''Hint:'' instead of writing a `for` or `while` loop, think of a recursive
   *  solution.
   *
   * @param xs A list of natural numbers
   * @return The sum of all elements in `xs`
   */
    def sum(xs: List[Int]): Int = if (xs.isEmpty) 0 else xs.head + sum(xs.tail)
  
  /**
   * This method returns the largest element in a list of integers. If the
   * list `xs` is empty it throws a `java.util.NoSuchElementException`.
   *
   * You can use the same methods of the class `List` as mentioned above.
   *
   * ''Hint:'' Again, think of a recursive solution instead of using looping
   * constructs. You might need to define an auxiliary method.
   *
   * @param xs A list of natural numbers
   * @return The largest element in `xs`
   * @throws java.util.NoSuchElementException if `xs` is an empty list
   */
    def greater(a: Int, b: Int): Int = if (a>=b) a else b
    def max(xs: List[Int]): Int = if (xs.isEmpty) 0 else greater(xs.head, max(xs.tail))
  }

Functional Programming Aims:

• Avoid Mutation
• Have powerful ways to abstract and compose functions
• Defining theories for operators expressed as functions

Mathematical theory = data types + operations + relationships - mutable operations

In restricted sense FP is programming without imperative control structures such as mutable variables, loops, assignments etc, in a wider sense, FP is focusing on functions. Functions can be produced, composed and consumed. In Particular, functions are First Class Citizens:

• They can be Defined Anywhere, inside or outside other functions
• Can be passed as params and returned
• there exists a set of operators to compose functions

Moore's Law states that no of transistors in a chip will double every two years, thereby making processors faster, however, this has stopped being the case and growth is now been observed in the horizontal direction, whereby the no of cores in a CPU are increasing, giving rise to the need of programming models for concurrent and parallel programming. Mutability of data structures makes this quite complex, therefore, FP can come to the rescue by eliminating Mutability.

In Imperative programming, you think time wise, while in functional programming you think space wise.

Definitions in Scala:

scala> def pi = 3.14
pi: Double

scala> def square(x: Double) = x * x
square: (x: Double)Double

scala> square(9)
res0: Double = 81.0

scala> square(square(4))
res1: Double = 256.0

scala> def sumOfSquares(x: Double, y: Double) = square(x) + square(y)
sumOfSquares: (x: Double, y: Double)Double

scala> sumOfSquares(3, 4)
res2: Double = 25.0

If return type is given, it follows after the parameter list Primitive types are as in Java, but capitalized

def power(x: Double, y: Int): Double = ...

Expressions in Scala are evaluated using the substitution model. This substitution model is formalised in λ-calculus, which gives foundation for functional programming. Re-write the expression until it's a value.

Does every expression reduce to a value in a finite no of steps? No! Example:-

def loop: Int = loop

loop

Call by value, Call by name reduce to the same final values as long as

• The reduced expression consists of pure functions
• Both Evaluations terminate

If CBV of an expression terminates => CBN of the expression will also terminate, converse is not true

def first(x: Int, y: Int) =  x

Under CBV	Under CBN
first(1, loop)	first(1, loop)
Evaluates infinately	1 step evaluation

Scala generally uses CBV for evaluation, since its exponentially more effective than CBN for evaluation.

If function parameter starts with =>, then it uses call by name

def constOne(x: Int, y: => Int) = x

Under this constOne(1+2, loop) will evaluate in 2 steps

Conditionals and Value Definations

if-else in scala is used as an expression, not a statement

def abs(x: Int) = if (x>0) x else -x

Boolean expressions can be composed just like in Java

Value Definitions

def form = Call by Name, it's right hand side is evaluated on each use

val form = Call by Value

val x = 2
val y = square(y)

For instance, y above refers to 4, not square(2)

Difference between val and def becomes apparent when RHS doesn't terminate

scala> def loop: Boolean = loop
<console>:7: warning: method loop does nothing other than call itself recursively
       def loop: Boolean = loop
                           ^
loop: Boolean

scala> def x = loop
x: Boolean

scala> val y = x
Execution interrupted by signal

Write a function such that for all execution expressions x and y

• and(x, y) = x && y

Do not use && in implementation

Answer:-

def and(x: Boolean, y: => Boolean): Boolean = if (x) y else false 

You need to specify the return type of a function if it is recursive, i.e. the right hand side calls the function itself. If the function isn't recursive, then you dont have to specify return type.