Scala 函数式程序设计原理 Week1 笔记

Getting Started

安装SBT

SBT 是一个类似 Maven 的项目管理工具,提交作业需要用到,课程里给了详细的介绍,SBT Reference Manual SBT tutorial

配置 IDE

视频课程里用的是 Eclipse,但我还是选的 IDEA。

Functions & Evaluation

Paradigm 范式

In science, a paradigm describes distinct concepts or thought patterns in some scientific discipline.

函数式编程定义:

  • 狭义概念:没有可变变量、指向或者命令式控制
  • 广义概念:集中于函数编写

函数式编程优势

  • 更简单的因果法则
  • 更易模块化
  • 适于多核或云计算上并行化处理

call-by-name:按照定义的顺序进行计算
call-by-value:按照数值的顺序进行计算
Scala 用的是 CBV(call-by-value)

if-else

1
2
3
if (conditional statement1) a 
else if (conditional statement2) b
else c

指定 val 是 CBV,如 val x = 2; val y = square(x) 中,y是4,而不是 sqare(x)。

recursion

tail-recursion 尾递归: If a function calls itself as its last acton, the function’s stack frame can be reused.

编程作业

这周的编程作业主要是考递归。前两个题目都不难,最后一个 Coin Change问题 有些难度,在网上找到一个比较靠谱的解析,可以这样理解这个递归过程:

首先考虑 bad case情况,两个变量 money 和 coins 的异常值分别是 monty < 0 和 coins.isEmpty,出现这种情况说明这条链路是不通的,故而返回值是 0。

再考虑 money = 0 的情况,money = 0可以理解为找零已经完成,或者把 coins 里的空集找给对方就可以,所以是一条完成的链路,返回值是 1。

最后就是 money > 0、 coins 不为空的正常状态。这时可以将 countChange(money, coins) 按照 coins.head 的状态进行拆解,即第一种状态是使用 coins.head ,第二种状态是不使用 coins.head。使用 coins.head 后,可能的找零方式为 countChange(money - coins.head, coins),如果不使用 coins.head ,则找零方式为 countChange(money, coins.tail),两种状态分别的合集即是 countChange(money, coins)。