Principles in Scala(一)
https://www.coursera.org/learn/progfun1
该课程更像是Scala版本的SICP
WEEK 1 notes:
这周主要是sbt、idea插件等环境准备,然后通过几个案例简单介绍下Scala的语法
Prepare
$ brew install sbt |
Evaluation Rules
- Call by value: evaluates the function arguments before calling the function
- Call by name: evaluates the function first, and then evaluates the arguments if need be
def test(x: Int, y: Int) = x * x |
- If CBV evaluation of an expression e terminates, then CBN evaluation of e terminates, too
- The other direction is not true
def test(x: Int, y: Int) = x |
- Scala normally use
call-by-value
, but if the type of a function parameter starts with=>
it usescall-by-name
def example = 2 // CBN, evaluated when called |
SICP Newton’s method
def abs(x: Double) = if (x < 0) -x else x |
the isGoodEnough
test is not very precise for small numbers and lead to Non-termination for very large numbers.
- 0.001
- 0.1e-20
- 1.0e20
- 1.0e50
the improved isGoodEnough
def isGoodEnough(guess: Double, x: Double) =
abs(guess * guess - x) / x < 0.001
Blocks and Lexical Scope
def abs(x: Double) = if (x < 0) -x else x |
much cleanerdef abs(x: Double) = if (x < 0) -x else x
def sqrt(x: Double) = {
def sqrtIter(guess: Double): Double =
if (isGoodEnough(guess)) guess
else sqrtIter(improve(guess))
def isGoodEnough(guess: Double) =
abs(guess * guess - x) / x < 0.001
def improve(guess: Double) =
(guess + x / guess) / 2
sqrtIter(1.0)
}
Tail Recursion
If a function calls itself as its last action, the function’s stack frame can be reused.
参照SICP 1.2节,递归计算过程的两种形式
- linear recursive process 线性递归计算过程
构造阶段会形成一个很长的链条,收缩阶段再执行具体计算操作 - iterative process 迭代计算过程
常量空间中执行迭代计算,即使这一计算是用递归过程描述的
Tail recursive functions are iterative processes.
不要混淆recursive process(递归计算过程)和recursive procedure(递归过程);递归过程只是一个概念,而它的进展方式可以是迭代的,也可以是线性递归的
// Tail Recursion |
Tail Recursion in Scala
尾递归一直被当做一种编译技巧,有了尾递归的实现,就可以用常规的调用机制表述迭代,所以能使各种复杂的专用迭代结构包装成各种语法糖;比如Scala @tailrec
编译器优化尾递归,如果实现方法不是尾递归会报异常//a tail recursive version of factorial
def factorialTailRecursion(n: Int): Int = {
def loop(acc: Int, n: Int): Int =
if (n == 0) acc
else loop(acc * n, n-1)
loop(1, n)
}