前言

Scala Puzzle系列要暂时停更一段时间了,之前我以为Scala Puzzle是一本趣味读物,结果发现是进阶读物,做到一半发现做不下去了(摔

回过头来重新系统学习Scala基础知识,这里选择遵循Scala官网的课程列表

第一门课程在coursea上叫Functional Programming Principles in Scala,由Martin Odersky主讲,课程的主要语言为英文,提供字幕。

这个系列的笔记名称就叫”Progfun”,因为原文“Scala 函数式程序设计原理”是在太长

主要按周为进度记录每周的视频中的练习和留下的课后习题部分。

环境准备

在第一周的课程材料里有详细的环境搭建过程说明,这里就不再赘述了。

我使用的开发环境是Windows + Intellij IDEA + WSL + XShell + SBT

本系列使用的REPL版本为 Scala 2.11.12(当前时间最新的Scala版本为2.13.0)

Week 1: Getting Start , Function & Evaluation

第一周的课程视频过程约1小时20分钟,讲了下Scala和其他语言的对比和特性

1
def loop: Int = loop

1.2 Element of Programming

对于同样的表达式,有两种计算方法

  • call by value
  • call by name

call by value的好处是对于每一个函数的参数,只用进行一次计算

call by name的好处是对于函数体内没有使用到的参数不用进行计算

这样说有些抽象,让我们看下下面的例子

假设你有一个函数def test(x: Int, y: Int) = x * x

对于下面几种函数参数的调用

  • test(2,3)
  • test(3+4,8)
  • test(7,2*4)
  • test(3+4,2*4)

是call by value更快,call by name更快,还是两者一样快(这里把加法和乘法看作一样快)?

我们先来看第一个例子test(2,3)

call by value :

  • test(2,3) = 2 * 2 = 4

call by name:

  • test(2,3) = 2 * 2 = 4

可以看到,在最简单的情况下,两者的步骤是一样多的。

对于第二个例子 test(3+4,8)

call by value:

  • test(3+4,8) = test(7, 8) = 7 * 7 = 49

call by name:

  • test(3+4,8) = (3+4) * (3+4) = 7 * (3+4) = 7 * 7 = 49

这里就体现出差距了,call by value由于在参数进入是就做了计算,所以只用了三步,而call by name则直接把参数传了下去,需要四步。

再来看第三个例子 test(7,2*4)

call by value:

  • test(7,2 * 4) = test(7,8) = 7 * 7 =49

call by name:

  • test(7,2 * 4) = 7 * 7 = 49

这里由于第二个参数不参与函数体内的计算,call by name反而更胜一筹

最后一个例子 test(3+4, 2*4)

call by value:

  • test(3+4, 2 * 4) = test(7, 2 * 4) = test(7, 8) = 7 * 7 = 49

call by name:

  • test(3+4, 2 * 4) = (3+4) * (3+4) = 7 * (3+4) = 7 * 7 = 49

最后还是使用了相同的步骤数。

1.3 Evaluation Strategies and Termination

大多数情况下,call by value的计算效率比call by name高,因为它避免了传入参数的重复计算,

但是,对于call by name 能终止的条件,call by value可能会一直执行,这也很好理解,因为call by value需要计算

出所有的参数值,比如

1
2
3
def loop: Int = loop

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

注意,这里 y: => Int里,不能把冒号和等号连写,要不然会被识别成标识符

1
2
3
4
5
scala> def constOne(x: Int, y:=> Int) = 1

<console>:1: error: ':' expected but identifier found.
def constOne(x: Int, y:=> Int) = 1

y: => Int这样的写法,是为了指明对于参数y用call by name的方式来使用

那么,对于以上的函数,下面两个调用的结果如何呢?

  • constOne(1+2, loop)
  • constOne(loop, 1+2)

constOne(1+2, loop) :

  • constOne(1+2, loop) = constOne(3, loop) = 1

constOne(loop, 1+2):

  • constOne(loop, 1+2) = constOne(loop, 1+2) = ….

你会发现,第二种写法造成了死循环

如果对上面的例子还不太明白,下面有个直观的样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
scala> def something() = {
| println("calling something")
| 1 // return value
| }
something: ()Int

scala> def callByValue(x: Int) = {
| println("x1=" + x)
| println("x2=" + x)
| }
callByValue: (x: Int)Unit

scala>

scala> def callByName(x: => Int) = {
| println("x1=" + x)
| println("x2=" + x)
| }
callByName: (x: => Int)Unit

scala> callByValue(something())
calling something
x1=1
x2=1

scala> callByName(something())
calling something
x1=1
calling something
x2=1

1.4 Conditions and Value Definitions

1
2
3
4
// and(x,y) == x && y
// 要求不用 && 或 || 来实现这个函数

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

这里由于 && 的短路机制,即如果x的值 为真,就不需要再计算y的值,因而y的传参使用的是call by name的方法。

也可以写成def and(x: Boolean, y: => Boolean) = if (x) y else false

类似的,or函数的实现自然也能写出来

1
def or(x: Boolean, y: => Boolean) = if (x) true else y

1.5 Example: square roots with Newton’s method

以下是对牛顿迭代法求平方根的一个简易解释

首先我们选定一个值作为初始条件,如y = 1

对于求sqrt(2), 2/y = 2, 如果我们求解的y = sqrt(x), 那么 x / y = y

这里可以看出1<2我们估计的值不对,为了下一次估计更加准确,我们取 (y + x /y ) /2 作为下一次估计值

这里y2 = (1 + 2)/2 = 1.5 2/1.5=1.3333

可以发现这里估计的更准了,因为 x/y 与y的差值更小了,这里可以证明,重复这个步骤,结果是一个收敛的数列(证明略)。

那么,只要我们的估计值 |y - x/y| < e , e为一个足够小的数,如0.0001,我们就能进近似的认为,我们现在估计的y值为sqrt(2)

实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
object session {
def abs(x: Double) = if (x < 0) -x else x

def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(imporve(guess, x), x)

def isGoodEnough(guess: Double, x: Double) =
abs(guess - x / guess) < 0.001 * guess

def imporve(guess: Double, x: Double) =
(guess + x / guess) / 2

def sqrt(x: Double) = sqrtIter(1.0, x)

}

看起来似乎没啥问题

1
2
3
4
5
scala> session.sqrt(2)
res0: Double = 1.4142156862745097

scala> res0 * res0
res1: Double = 2.0000060073048824

然而并不是,Martin接下来立刻就丢过来三个问题

  1. isGoodEnough函数对于非常小的数字不太准确,对于很大的数字看起来又无法终止,能解释原因吗

  2. 重新实现isGoodEnough函数以规避上述问题

  3. 测试以下样例

    • 0.0001
    • 0.1e-20
    • 1.0e20
    • 1.0e50
  4. 对比较小的数据不准确是因为isGoodEnough用的是绝对误差,可对该函数做简单修改,以输出中间值

    1
    2
    def isGoodEnough(guess: Double, x: Double) =
    {println(guess, x/guess);abs(guess * guess - x) < 0.001}

    运行结果为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    scala> session.sqrt(1e-6)
    (1.0,1.0E-6)
    (0.5000005,1.999998000002E-6)
    (0.250001249999,3.999980000116E-6)
    (0.12500262498950004,7.999832004199894E-6)
    (0.06250531241075212,1.5998640138433748E-5)
    (0.031260655525445276,3.198909246116188E-5)
    res2: Double = 0.031260655525445276

    这里 0.03 * 0.03 - 0.0001 < 0.001但是显然最后的结果不好

    我们当然可以直接把0.001改成一个更小的值,但更好的一个做法是用相对误差,修改后的函数如下

    1
    2
    def isGoodEnough(guess: Double, x: Double) = 
    abs(guess - x / guess) < 0.001

    修改后的结果看起来更正常了

    1
    2
    3
    4
    5
    6
    scala> session.sqrt(1e-6)
    res3: Double = 0.0012961915927068783

    scala> session.sqrt(1e50)
    //REPL 会卡住

    对应地,对于较大的输入的数,它根本不会收敛到终止条件。

    这是因为double 类型浮点数,在IEEE 754标准中,用64位来存储,其中分配了52位来存储浮点数的有效数字,11位存储指数,1位存储正负号

    在二进制表示中,有效数字大于52位的部分会舍去

    1
    2
    3
    4
    5
    6
    7
    8

    scala> def log2 = (x:Double) => Math.log(x)/Math.log(2.0)
    log2: Double => Double

    scala> log2(1e50)
    res1: Double = 166.09640474436813


    这里可以看到1e60转换成二进制有近166位,而浮点数的精度只有52位,也就是说,最小误差也是2^114远大于0.001,所以自然不会到达终止条件

  5. 基于以上的分析,我们重新实现的函数如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    object session {
    val eps = 0.001

    def abs(x: Double) = if (x < 0) -x else x

    def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(imporve(guess, x), x)

    def isGoodEnough(guess: Double, x: Double) =
    abs(guess - x / guess) < eps * guess

    def imporve(guess: Double, x: Double) =
    (guess + x / guess) / 2

    def sqrt(x: Double) = sqrtIter(1.0, x)

    }
  6. 运行测试

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    scala> session.sqrt(0.0001)
    res3: Double = 0.010000714038711746

    scala> session.sqrt(1e20)
    res4: Double = 1.0000021484861237E10

    scala> session.sqrt(1e-20)
    res6: Double = 1.0000021484861236E-10

    scala> session.sqrt(1e50)
    res7: Double = 1.0000003807575104E25

1.6 Blocks and Lexical Scope

下面这段代码的运行结果是什么

1
2
3
4
5
6
7
8
val x = 0

def f(y: Int) = y + 1

val result = {
val x = f(3)
x * x
} + x

要理解这段代码,首先要理解变量的作用域,对于变量x来说,它在这段代码中被定义了两次,在外部的值为0,而在result的内部,x = f(3) = 4,result代码块返回的结果x*x为16,因而result = 16 + 0 = 16

1.7 Tail Recursion

设计一个尾递归的阶乘函数

1
2
3
4
5
6
7
8
9
10
def factorial(n: Int): BigInt = {
def loop(result: BigInt, n: Int): BigInt =
if (n == 0) result
else loop(result * n, n - 1)
loop(1, n)
}

scala> factorial(233)
res0: BigInt = 96880983124035637644628191427119032733410705766804841418415225561765762804210624629481224430320029511142586282867348560105183527088477325371186685286160118876894338289245202198092574546071969642723246616617867678202922360665112163722099321474343230404599030924937888027299552398154265468854355637510534924861247309970389790443978423417096800652347264383303351164354900418398161431781398827918950400000000000000000000000000000000000000000000000000000000

Example Assignment

这一步之前,首先需要配置好运行环境,这里就不赘述了。

将课程提供的example.zip下载到本地解压,用Intellij打开

我们需要完成的就是src/main/scala/example/Lists.scala这个文件

Notes: 注意不要修改已经实现的方法或名称

从IDE中打开sbt shell,首次运行需要下载依赖包,这可能会花费一段时间,长短视网络情况而定。

1
2
3
4
5
6
7
8
9
10
> console

scala> import example.Lists._
import example.Lists._

scala> max(List(1,3,2))
scala.NotImplementedError: an implementation is missing
at scala.Predef$.$qmark$qmark$qmark(Predef.scala:230)
at example.Lists$.max(Lists.scala:41)
... 42 elided

这里报错因为这个方法尚未被实现,这个作业的任务就是这个了,实现List的sum和max方法

这两个方法的详细说明,注释里已经解释地很清楚了,这里就不在赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def sum(xs: List[Int]): Int = {
def reduceLeft(sum:Int, xs: List[Int]): Int = {
if (xs.isEmpty)
sum
else
reduceLeft(sum + xs.head, xs.tail)
}

reduceLeft(0, xs)
}

def max(xs: List[Int]): Int = {
if (xs.isEmpty) throw new java.util.NoSuchElementException

def reduceLeft(max:Int, xs: List[Int]): Int = {
if (xs.isEmpty)
max
else
reduceLeft(Math.max(max,xs.head), xs.tail)
}

reduceLeft(Int.MinValue, xs)
}

这里用递归的方式实现

这里还需要写单元测试来检验我们的答案。

对应的文件为src/test/scala/example/ListSuite

该文件内有详细的说明编写单元测试的注意事项,你需要对里面的代码进行修改,使得程序在sbt shell中运行test命令时,能顺利通过。

正确通过时如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
> test

[IJ]> test
[info] ListsSuite:
[info] - one plus one is two
[info] - one plus one is three?
[info] - details why one plus one is not three
[info] - intNotZero throws an exception if its argument is 0
[info] - sum of a few numbers
[info] - max of a few numbers
[info] - sum of a few negative numbers
[info] - sum of zeros
[info] - max of null List show throw NoSuchElementException
[info] Run completed in 1 second, 54 milliseconds.
[info] Total number of tests run: 9
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 9, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 3 s, completed 2019-7-17 21:52:55

具体修改步骤就不列出了。

最后完成时记得提交,提交步骤也是在sbt shell里运行,在作业的网页右侧可以生成识别码

在sbt shell中运行submit <email-address> <your-code>就可以提交

submit [email protected] HEmio6RWZ7ribfh1

之后你可以在网页中查看自己的分数,至此示例作业就完成了。

作业: Recursion

  1. 帕斯卡三角(杨辉三角)

    1
    2
    3
    4
    5
    1
    1 1
    1 2 1
    1 3 3 1
    1 4 6 4 1

    pascal(0,2) = 1, pascal(1,2) = 2, pascal(1,3) = 3

    求paccal(col, row)的值,col和row都是从0开始计算

    如果你还记得二次项系数(二项式定理),那么就好办了
    $$
    若 C^m_n = \frac{n!m!}{(n-m)!} ,n >= m 且 m,n∈N^+
    $$
    那么有
    $$
    C_n^m = C_{n-1}^{m-1} + C_n^{m-1}
    $$

    已知
    $$
    C_n^0 = C_n^n = 1
    $$

    代码实现如下

    1
    2
    3
    def pascal(c: Int, r: Int): Int = 
    if (c == 0 || c == r) 1
    else pascal(c - 1, r - 1) + pascal(c, r - 1)
  2. 判断括号是否平衡

    判断一串字符串文本中包含的括号是否“平衡”

    例如,以下序列为平衡

    • (if (zero? x) max (/ 1 x))
    • I told him (that it’s not (yet) done). (But he wasn’t listening)

    以下序列为不平衡

    • :-)
    • ())(

    简单来说 可以总结为如下规则

    • 空串或者不含括号的字符串为平衡的
    • 如果R为平衡的,那么(R)也是平衡的
    • 如果R为平衡的,S为平衡的,那么RS也是平衡的

    代码实现如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], count: Int): Boolean = {
    if (chars.isEmpty) count == 0
    else if (chars.head == '(') balanced(chars.tail, count + 1)
    else if (chars.head == ')') count > 0 && balanced(chars.tail, count - 1)
    else balanced(chars.tail, count)
    }

    balanced(chars, 0)
    }

    思路是,一个平衡的序列,()数量必须相同且合法。

    • 空串是合法的序列
    • 如果字符串的第一个字符为(, 当前计数+1,递归执行剩下的字符串
    • 如果字符串的第一个字符为), 且当前计数大于零,那么递归执行剩下的字符串,当前计数-1
    • 如果不符合以上条件,递归执行剩下的字符串
  3. 计算找零

    给你一定数目的钱money,问用coins(一个整型数组)中的零钱,有多少种方法能凑够

    例如,对于money = 4 , coins = List(1, 2)

    有3种方法(交换顺序算一种方法)

    4 = 1 + 1 + 1 + 1

    = 1 + 1 + 2

    = 2 + 2

    • 显然,当money = 0 时,结果为0

    • 当 money != 0时,设当前的答案为f(money, coins)

      那么 f(money, coins) = f(money - coins.head, conins) + f(money, coins.tail)

      即当前状态的结果,为用零钱里第一种面额的找零方案,加上不用零钱里第一种面额的找零方案,这两个结果的数目之和

      易知这个划分是互不相交且并集为完整结果集

    • 再考虑到边界条件

    代码实现如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def countChange(money: Int, coins: List[Int]): Int = {
    def count(money: Int, coins: List[Int]): Int =
    if (coins.isEmpty) 0
    else if (money == coins.head) 1
    else if (money < coins.head) 0
    else count(money - coins.head, coins) + count(money, coins.tail)

    count(money, coins.sorted)
    }