@abbed 2017-05-07T14:04:43.000000Z 字数 4767 阅读 556

Scala 学习笔记

scala

Week 1

Lesson 1 Programming Paradigms

Scala 是一种函数式编程语言，与之并列的类型有命令式编程语言（例如C、C++、Java、Python），逻辑式编程语言（比如Prolog）。而常见的面向对象和面向过程的分类可以看作是另外一个正交维度上的分类，即一个语言既可以是命令式+面向对象（比如Java），也可以是函数式+面向对象（比如Scala）。

命令式编程语言的特点有：

能够修改可变变量
使用赋值语句
使用控制结构（例如 if-then-else，循环，break，continue，return）

函数式编程语言的特点有：

用函数来定义一个理论（包含一个或多个数据类型，数据类型上的操作，一些运算定律）
变量的值不可变
强于抽象和组织函数

严格地说，函数式编程语言不能有可变变量、赋值、命令式的控制流结构。函数是函数式编程语言的一等公民。

Lesson 2&3 Evaluation Strategies

1. 定义值和函数

对于非递归的函数，返回值类型可以省略。

def a = 10
val b =5
def power(x: Double, y: Int): Double = ...

2. call by value 和 call by name

有两种不同对表达式求值的代换过程（称为替代模型），分别是call by value和call by name。加入我们要对下面代码中最后一行的表达式求值

def square(x: Double): Double = x * x
def sumOfSquares(x: Double, y: Double): Double = square(x) + square(y)
sumOfSquares(3, 2+2)

call by value	call by name
sumOfSquares(3,4)	square(3)+square(2+2)
square(3)+sqaure(4)	3*3+square(2+2)
3*3+square(4)	9+square(2+2)
9+square(4)	9+(2+2)*(2+2)
9+4*4	9+4*(2+2)
9+16	9+4*4
25	9+16
	25

两种替代策略都能化简到最终值只要保证

化简后的表达式只含有纯函数
能在有限步终止

一个不能在有限步终止的函数例子如下

def loop: Int = loop

call by value策略的优点是它对每个函数参数只计算一次
call by name策略的优点是如果一个参数未被使用，那么就不会对它进行求值
对于下面这个例子

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

CBN策略可以终止而CBV策略则不能终止。
实际上，CBV策略下会终止的表达式在CBN策略下一定会终止，反之则不一定成立。
在Scala中，我们通常用CBV，因为实际中它比CBN会快指数倍。当然，我们也可以显式地指定某些参数用CBN策略，例如下面代码中的参数y：

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

Lesson 4 Conditionals and Value Definitions

Scala中也有if-else的结构，只不过它是一种表达式而不是语句，类似于Python表达式中的if-else

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

对于变量定义，也有对应的代换策略，def默认为CBN，而val为CBV。在下面这个例子中，y指的是4，而不是square(2)。

val x = 2
val y = square(x)

Lesson 5 Some Writting Details

在Scala中，如果一个表达式要跨行，可以用圆括号括起来；或者在第一行末尾放一个中缀运算符。
每一个表达式结尾一般不加分号。
可以用大括号包裹一个代码块。
外层变量会被内层同名变量屏蔽，否则就是可见的。

Lesson 6 Tail Recursion

如果一个函数在最后一步调用自身，那么函数的栈就可以重用，称为尾递归。尾递归要比一般递归的效率高很多，因为它相当于循环。下面计算阶乘的函数例子中，第一个不是尾递归，第二个是。注意到在第二种实现中用到了一个helper函数loop，这个技巧十分常用。

// Version 1
def fact(n: Int): Int = if (n == 1) 1 else n * fact(n-1)
// Version 2
def fact(n: Int): Int = {
  def loop(acc: Int, n: Int): Int = {
    if (n == 0) acc
    else loop(acc * n, n - 1)
  }
  loop(1, n)
}

Week 1 参考资料

Week 2

Lesson 1 Higher Order Functions

如前面说过的，函数在Scala中是一等公民，它既可以作为其他函数的参数，也可以作为其他函数的返回值。这个特点可以让我们能够灵活地组织程序。以其他函数作为参数或返回值的函数称为高阶函数。
例如下面这个例子，我们想计算a到b之间所有整数的和、平方和、立方和。

def cube(x: Int) = x * x * x
def sumInts(a: Int, b: Int): Int = 
  if (a > b) 0 else a + sumInts(a + 1, b)
def sumSquares(a: Int, b: Int): Int =
  if (a > b) 0 else square(a) + sumSquares(a + 1, b)
def sumCubes(a: Int, b: Int): Int =
  if (a > b) 0 else cube(a) + sumCubes(a + 1, b)

注意到，上面三个函数的形式都是

$\sum_{n=a}^b f(n)$ 的特例，取决于不同的

$f$ 。那么，有没有简便的方法可以定义这样的形式呢？Scala允许我们定义一个函数接收一个函数作为参数

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

这样的话，上面的三个函数就可以定义为

def id(x: Int) = x
def sumInts(a: Int, b: Int): Int =    sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumCubes(a: Int, b: Int): Int =   sum(cube, a, b)

这里我们有一个新的类型，即函数类型typeA => typeB。
我们还可以用匿名函数来更简化一些，以立方和为例

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

如果有多个参数也是类似的，例如 (x: Int, y: Int) => x + y
上面的sum函数使用线性递归的，我们可以将它改写成更高效、安全的尾递归版本

def sum(f: Int => Int, a: Int, b: Int) = {
  def loop(a: Int, acc: Int): Int =
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  loop(a, 0)
}

Lesson 2 Currying

在上一节的三个改进后的例子中，传递参数a和b似乎是多余的。我们可以重新定义 sum 函数，来避免这种情况

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 函数的返回值为一个函数。于是，三个求和函数的定义变为

def sumInts    = sum(x => x)
def sumSquares = sum(x => x * x)
def sumCubes   = sum(x => x * x * x)

更简便地，我们可以省略掉这三个函数，以计算1到10的立方和为例

sum (x => x * x * x)(1, 10)

Scala提供一个语法糖可以简化上面 sum 函数的定义

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

参数列表可以继续扩展到更多层，这样的函数定义风格称为currying。更一般地，我们可以将求和 $\sum$ 扩展到求积 $\prod$ 以及任意的算子

def mapReduce(map: Int => Int, reduce: (Int, Int) => Int, unit:Int)(a: Int, b:Int): Int = 
  if (a > b) unit
  else reduce(map(a), mapReduce(map, reduce, unit)(a + 1, b))

求立方和的函数就可以定义成

def sumCubes = mapReduce(x => x * x * x, (x, y) => x + y, 0)

Lesson 3 Classes,Methods,Operators,Identifiers

在Scala中，我们也可以定义类和方法。以有理数为例

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y
}

如果我们要创建一个有理数对象，就用

val x = new Rational(1,2)

我们可以在类里定义有理数的一些计算，称为方法。以加法为例

def add(that: Rational) = 
  new Rational(
    numer * that.denom + that.numer * denom,
    denom * that.denom)

其中，numer 指的是 this.numer，可以省略掉 this。
注意这样可能会产生未化简的有理数，为了使每次的结果都自动化简，我们可以在对象创建时进行化简，而不是在每次计算后显式地化简一遍，即

class Rational(x: Int, y: Int) {
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  def numer = x/gcd(x, y)
  def denom = y/gcd(x, y)
}

其中，gcd 是计算最大公约数的函数。
同样的，我们也可以定义 neg，用来得到一个有理数的相反数

def neg: Rational = new Rational(-numer, denom)

对有理数来说，分母不能为0。因此，我们可以用 require 来保证这一点。在类的代码块中添加

require(y != 0, "denominator must be nonzero")

其中，第一个参数是一个返回值为 Boolean 的表达式，第二个参数为提示语。
除了默认的构造函数外，我们还可以自定义别的版本的，比如接收一个参数 $n$ ，返回 $n/1$ 的有理数

def this(x: Int) = this(x, 1)

另外，对中缀运算，我们可以直接这样定义，以加法为例

def + (that: Rational) = 
  new Rational(
    numer * that.denom + that.numer * denom,
    denom * that.denom)

因为在Scala中，+ 也算是一个合法的识别符。一个识别符可以是

Alphanumeric：以一个字母开头，后面是任意个字母或数字
Symbolic：以一个运算符开头，后面是任意个其他运算符

注意，下划线算作字母；Alphanumeric识别符也可以是以下划线结尾，后面是其他运算符。这些都是合法的识别符：x1，*，+?%&，vector_++，counter_= 。注意在定义的时候，+ 后面一定要留一个空格，不然后面的括号就会被识别为同一个识别符。
对于前缀运算，比如 neg，我们可以添加一个说明 unary_

def unary_- : Rational = new Rational(-numer, denom)

在Scala中，运算符优先级由第一个字符确定

字符	优先级
任意字母（包括下划线）	最高
\|
^
&
< >
= !
:
+ -
* / %
任意其他特殊字符	最低

Week 2 参考资料

Progfun Course Notes