# Scala 2

## Tail Recursion

### Evaluating a Function Application

One simple rule: One evaluates a function application `f(e1,e2,...,en)`

1. `e1...en`进行求值，得到`v1...vn`
2. 把等号右边的函数体展开
3. `v1,...,vn`替换函数内的参数`e1,...,en`

### Application Rewriting Rule

This can be formalized as rewriting of the program itself

``````//定义一个函数f
def f(x1,...,xn) = B; ...f(v1...vn)

//调用了这个函数
f(v1,...,vn)

//将f展开
[v1/x1,...,vn/xn]B
``````
• Here, `[v1/x1,...,vn/xn]` 意味着:
• The expression `B` in which all occurrences of `xi` have been replaced by `vi`
• `[v1/x1,...,vn/xn]` is called a substitution

### Example #1

``````
def gcd(a:Int, b:Int) : Int =
if (b == 0) a else gcd(b,a%b)

``````

`gcd(14,21)` is evaluated as follows:

``````-> `if(21 == 0) 14 else gcd (21,14%21) `
-> `if(false) else gcd (21,14%21) `
-> `gcd (21,14%21)`
-> `gcd (21,14)`
-> `if(14) == 0 21 else gcd (14,21%14) `
-> ...
-> `gcd (14,7)`
-> ...
-> `gcd (7,0)`
-> `if (0==0) 7 else gcd(0,7%0)`
-> `7`
``````

### Example #2

``````def factorial(x:Int):Int =
if (x == 0 ) 1 else x*factorial(x-1)

``````

factorial(4) is evaluated as follows:

``````-> `if (4==0) 1 else 4*factorial(4-1)`
-> ...
-> `4*factorial(3)`
-> `4*3*factorial(2)`
-> `4*3*2factorial(1)`
-> `4*3*2*1*factorial(0)`
-> `4*3*2*1*1`
-> 24
``````

### Tail Recursion

Implementation Consideration: if a function calls itself as its last action, the function’s stack frame can be reused. This is called tail recursion

In general, if the last action of a function consists of calling a function（maybe the same, maybe some other functions）, one stack frame would be sufficient for both functions. Such calls are called `tail-calls`

``````object exercise {
def factorial(x:Int):Int =
{
def loop(acc:Int, x:Int):Int =

if ( x== 0 ) acc
else
loop(acc*x,x-1)

loop(1,x)
}
factorial(4)
}
``````

## Higher Order Function

• first-class values
• like any other value, a function can be passed as a parameter and returned as a result
• This provides a flexible way to compose programs
• Function takes other functions as parameters or that return functions as results are called HOF
``````def sum(f: Int=>Int, a:Int, b:Int):Int =
if (a>b) 0
else f(a) + sum(f,a+1,b)
``````

We can then write:

``````def sumInts(a:Int, b:Int) 		= sum(id,a,b)
def sumCubes(a:Int, b:Int) 		= sum(cube,a,b)
def sumFactorials(a:Int,b:Int) = sum(fact,a,b)
``````

where:

``````def id(x:Int):Int = x
def cube(x:Int):Int = x * x * x
def fact(x:Int):Int = if(x==0) 1 else fact(x-1)
``````

### Function Types

The type `A => B` is the type of a function that takes an argument of type A and returns a result of type B

### Anonymous Functions

``````(x:Int) => x * x * x
``````

Here,`(x:Int) => x * x * x`是匿名函数

• 参数的类型可以省略，他可以被编译器推断
``````(x:Int, y:Int) => x+y
``````

``````(x1:T1,...,xn:Tn) => E
//等价于
{
def f(x1:T1,...,xn:Tn) = E;
f
}
``````

`````` //return a function using block
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

}
``````

``````def sumInt(a:Int, b:Int) = sum(x => x, a, b)
def sumCubes(a:Int,b:Int) = sum(x=>x*x*x,a,b)

``````

## Currying

### Motivation

Look again at the summation functions:

``````def sumInts(a:Int, b:Int) = sum(x=>x ,a,b)

``````
• Question

Note that a and b get passed unchanged from `sumInts` and `sumCubes` into `sum`. Can we be even shorter by getting rid of these parameters?

### Functions Returning Functions

Let’s rewrite sum as follows:

``````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

}
``````

`sum` is now a function that returns another function. The returned function `sumF` applies the given function parameter `f` and sums the result

``````def sumIncrease = sum( x=>x+1 )
val result = sumIncrease(2,4)

//也可以直接计算:
val result = sum (x => x+1 )(2,4)
``````

Generally,function application associates to the left. 代码中，函数的运算是左结合：

``````sum(x=>x+1)(1,10) = (sum(x=>x+1))(1,10)
``````

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

### Expansion of Multiple Parameter Lists

In general, a definition of a function with multiple parameter lists

``````
//带有参数列表的函数
def f(args1)...(argsn) = E

``````

where `n>1`, 等价于

``````
def f(args1)...(argsn-1) = {def g(argsn)=E; g}

``````

• arg1,args2,…,argsn-1实际上都表示匿名函数:

• `def ((f(g)h)z) ... = {def g(x) = E; g}`

• 其中g(x)是所有这些匿名函数代入后的最终函数

whare `g` is a fresh identifier. Or for short:

``````
def f(args1)...(argsn-1) = (argsn => E)

``````

``````
def f = (args1 => (args2 => ... (argsn => E)...))

``````

• 分析`sum`
``````
def sum(f:Int=>Int)(a:Int,b:Int):Int = E

``````

what is the type of sum?

``````
(Int => Int) => (Int, Int) => Int

- 输入是(Int => Int)

- 输出是(Int,Int)=>Int

- 因此，上面的式子等价于 `(Int => Int) => ((Int, Int) => Int)`

- 但是函数是右结合的，因此左后的括号可以免掉

###Summation with Anonymous Functions

```scala

def sumInts(a:Int,b:Int) = sum(x=>x, a,b)
def sumCubes(a:Int,b:Int) = sum(x * x * x, a,b)

``````

###MapReduce

• map,reduce这种函数的基础就是currying
``````
def product(f:Int => Int)(a:Int, b:Int):Int =

if (a > b) 1
else f(a) * product(f)(a+1,b)     //> product: (f: Int => Int)(a: Int, b: Int)Int

def fact(n:Int) = product(x => x)(1,n)          //> fact: (n: Int)Int

fact(3)                                         //> res1: Int = 6

def mapReduce(map:Int=>Int, combine:(Int,Int)=>Int,zero:Int)(a:Int, b:Int):Int =

if (a>b) zero
else combine(map(a), mapReduce(map,combine,zero)(a+1,b))
//> mapReduce: (map: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int,
//| b: Int)Int

mapReduce(x=>x,(x,y)=>x*y,1)(2,4)         //> res2: Int = 24

def new_product(f:Int=>Int)(a:Int,b:Int) = mapReduce(f,(x,y)=>x*y,1)(a,b)
//> new_product: (f: Int => Int)(a: Int, b: Int)Int
def new_fact(n:Int) = new_product(x=>x)(1,n)
//> new_fact: (n: Int)Int
new_fact(4)                               //> res3: Int = 24

``````

##2-3: Finding a fixed point of a function

A number `x` is called a fixed point of a function `f` if

``````f(x) = x

``````

For some functions `f` we can locate the fixed points by starting with an initial estimate and then by applying `f` in a repetitive way.

``````x, f(x), f(f(x)), f(f(f(x))),....

``````

until the values does not vary anymore(or the change is sufficiently small).

This leads to the following function for finding a fixed point:

``````
val tolerance = 0.0001                    //> tolerance  : Double = 1.0E-4

def isCloseEnough(x:Double,y:Double) = abs((x-y)/x)/x < tolerance
//> isCloseEnough: (x: Double, y: Double)Boolean

def fixedPoint(f:Double => Double)(firstGuess:Double):Double =
{
def iterate(guess:Double):Double = {

val next = f(guess)

if (isCloseEnough(guess,next)) next
else
iterate(next)
}

iterate(firstGuess)

}

``````

###Summary

• 上周我们知道了Function是first-class的

• 这周我们知道HOF可以将function combine起来，可以做入参也可以做返回值

• As a programmer, one must look for opportunities to abstract and reuse.

• The highest level of abstraction is not always the best, but it is important to know the techniques, so as to use them properly.

##2-4:Scala syntax summary

We have seen language elements to express types, expressions and definations.

Below, we give their context-free syntax in Extended Backus-Naur form(EBNF), where:

• `|` denotes an alternative

• `[...]` an option(0 or 1)

• `{...}` a repetition (0 or more)

###Types

 Type = SimpleType FunctionType

FunctionType = SimpleType `=>` Type

``````		 | `( [Types] )` `=>` Type
``````

SimpleType = Ident

Types = Type {‘,’ Type}

A type can be:

• A numeric type : Int, Double, Byte, Short, Char, Long, Float

• Boolean type : true,false

• String type

• function type, like `Int => Int`, `(Int,Int) => Int`

###Expressions

An expression can be:

• An identifier such as` x, isGoodEnough`

• An literal, like `0,1.0,"abc"`

• An function application, like `sqrt(x)`

• An operator application, like `-x,y+x`

• An selection , like `math.abs`

• An conditional expression, like `if(x<0) -x else x`

• A block like `{val x= math.abs(y) ; x+2}`

• An anonymous function, like `x => x+1`

###Definiations:

Definition:

• A function definition like `def sum(x:Int,y:Int) = x+y`

• A value definitions like `val y = square(2)`

Parameter

• A call-by-value param, like`(x:Int)`

• A call-by-name para like `(y: => Double)`