Functional Programming Principles in Scala

a a’s    v v’s     a a’s 2.5    das dsa


scala> def loop() = loop    //infinite loop             OR def loop: Boolean = loop

Call by value [only evaluate once] - Call by Name [arg not evaluated if not used]
scala> def test(x:Int, y: Int) = x
scala> test(3+4, 8)
 Call by Value
 Call by Name
test(7,8)
7 * 7
49
(3+4) * (3+4)
7 * (3+4)
7 * 7
49

def func(x:Int, y: => Int) = x + y     //y is call by name because of    =>
func(1+2, loop)    1+2     3                                      func(loop, 1+2)      //infinite


If is a statement not an expression
scala> def abs(x: Int) = if (x > 0) x else -x
def is call by name, function body will not be evaluated until called. but val is call by value and the function is evaluated right there.
def x = loop        //OK
val x = loop        //INFINITE LOOP

implement && function:
def and(x: Boolean, y: => Boolean) = if (x) y else false    //=> let's us have short circuiting and in case x is false we won't go to evaluate y.
and(false, loop)   // if y is not call by name we will stick to infinite loop otherwise it evaluates to false.

Blocks {}

is an expression itself. sequence of expressions, the last expression is the value of the block
val x = 0
def f(y: int) = y + 1
val result = {
   val x = f(3)
    x * x
} + x
 result is 16.
Semicolons are optional. when writing expressions in multiple lines scala assumes they are differnet expressions but we only want to have them in multiple lines. To avoid use parenthesis, OR write operator as character on previous line

nesting functions you can inherit variables instead of sending them as explicit parameters.


Tail Recursion

In a tail recursive function, all calculations happen first and the recursive call is the last thing that happens.
Imagine a tail recursive function.  It runs.  It completes all its computation.  As its very last action, it is ready to make its recursive call.  What, at this point, is the use of the stack frame?  None at all.  We don’t need our local variables anymore because we’re done with all computations.  We don’t need to know which function we’re in because we’re just going to re-enter the very same function.  Scala, in the case of tail recursion, can eliminate the creation of a new stack frame and just re-use the current stack frame.  The stack never gets any deeper, no matter how many times the recursive call is made.  That’s the voodoo that makes tail recursion special in scala.

Incidentally, some languages achieve a similar end by converting tail recursion into iteration rather than by manipulating the stack.

This won’t work with head recursion.  Do you see why?  Imagine a head recursive function.  First it does some work, then it makes its recursive call, then it does a little more work.  We can’t just re-use the current stack frame when we make that recursive call.  We’re going to NEED that stack frame info after the recursive call completes.  It has our local variables, including the result (if any) returned by the recursive call.

def listLength2(list: List[_]): Int = {
  def listLength2Helper(list: List[_], len: Int): Int = {
    if (list == Nil) len
    else listLength2Helper(list.tail, len + 1)
  }
  listLength2Helper(list, 0)
}
 
println( listLength2( list1 ) )
println( listLength2( list2 ) )

this function first checks for a Nil list, but this time returns the len parameter rather than 0.  If list is non-Nil then we make the recursive call.  But there’s still an addition going on here, len + 1.  Does that ruin the tail recursion?  No.  That term is evaluated first.  Only after all the parameters have been evaluated does the recursive call happen.  This function does indeed qualify for tail recursion optimization. ONLY ONE STACK IS ENOUGH!!! each time it is replaced/swapped with the last call. because that is what is returned.

This is not tail recursive:
def listLength1(list: List[_]): Int = {
  if (list == Nil) 0
  else 1 + listLength1(list.tail)
}
You need to maintain the stack of each call as it is being reused in call-return calculations.
---------------------------

def factorial(n:BigInt):BigInt={
 if (n == 0) 1
 else n*factorial(n-1)
}

versus

@tailrec   //tell scala to tail recursive it
def factorial(n:BigInt):BigInt={
 def loop(n:BigInt, acc:BigInt):BigInt = if (n <= 0) acc else loop(n-1,acc*n)
 loop(n,1)
}

functions that take other functions as parameters or that return functions as results are called higher order functions
function as an argument
sum(f: Int => Int, x: Int, y: Int) : Int = if (x<=y) f(x) + sum(x + 1, y) else 0       //sigma f(i)      i from x to y
def sumcube(a: Int, b: Int) = sum(x => x * x * x, a, b)        //the type can be omitted if it can be inferred from context
anonymous
 (x:Int, y:Int) => x+y

























Comments