Structural Induction on Trees

Martin开篇耿直的说这对于在线课程是可选的(暗示可以跳过)

但是马上又补充了一句说如果你是EPFL的学生,最好别跳,因为考试可能会考

之前的课程中,我们写了一个function set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
abstract class Intset {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}

object Empty extends IntSet {
def incl(x: Int): IntSet = NonEmpty(x, Empty, Empty)
def contains(x: Int): Boolean = false
}

case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def incl(x: Int): IntSet = {
if (x < elem) NonEmpty(elem, left incl x, right)
else if (x > elem) NonEmpty(elem, left, right incl x)
else this
}

def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
}

如果我们想证明对于某个树T,满足性质P,即P(T)

  • 需要先证明对于所有叶子节点l,有P(l)
  • 再需要证明对于所有的非叶子节点t, 对于它的所有子树集合s1,...,sn,都满足P(s1) ^ ... ^ P(sn)

对于这段代码,需要证明它的正确性

那么,什么是代码的正确性

这里指的是代码按照我们预期的方式进行工作,比如,我们可以定义如下规则

  • Empty contains x = false
  • (s incl x) contains x = true
  • (s incl x) contains y = s contians y

对于这段代码,该如何证明呢?

即得易见平凡,仿照上例显然。留作习题答案略,读者自证不难。
反之亦然同理,推论自然成立,略去过程QED,由上可知证毕

Empty contains x = false 这条最简单,看定义易得

1
2
3
4
object Empty extends IntSet {
def incl(x: Int): IntSet = NonEmpty(x, Empty, Empty)
def contains(x: Int): Boolean = false
}

(s incl x) contains x = true

对于Empty的情况

1
2
3
(Empty incl x) contains x
= NonEmpty(x, Empty, Empty) contians x //由Empty.incl定义可知
= true //由NonEmpty.contains的定义可知

对于NonEmpty(x, l, r)

1
2
3
(NonEmpty(x, l, r) incl x) contains x
= NonEmpty(x, l, r) contains x
= true

对于NonEmpty(z, l, r), z < x

1
2
3
4
(NonEmpty(z, l, r) incl x) contains x
= NonEmpty(z, l, r incl x) contains x
= (r incl x) cotains x
= true // 由NonEmpty(x, l, r)的推论可得

对于NonEmpty(z, l, r), z > x 同理可得

(s incl x) contains y = s contians y

第三种情况留作习题

Streams, or LazyList ?

从 Scala 2.13 版本开始,Streams被废弃,推荐使用LazyList,所以下面用到的例子都是LazyList

1
2
val xs = LazyList.cons(1, LazyList.cons(2, LazyList.empty))
val ys = LazyList(1,2,3)

List做个简单对比

1
2
3
4
5
def lazyListRange(lo: Int, hi: Int): LazyList[Int] = 
if (lo >= hi) LazyList.empty else LazyList.cons(lo, streamRange(lo+1, hi))

def listRange(lo: Int, hi: Int): List[Int] =
if (lo >= hi) List.empty else lo :: listRange(lo+1, hi)

两者的结构基本相同,不同点在于元素是否立刻计算

嗯,还可以用特殊的符号#::代替LazyList.cons

这里的延迟计算实际上使用传名参数来实现的(call by name)

下面是一个简单的函数签名示例(仅供参考,并不能通过编译)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
trait LazyList[+A] extends Seq[A] {
def isEmpty: Boolean
def head: A
def tail: LazyList[A]
...
}

object LazyList {
def cons[T](hd: T, tl: => LazyList[T]) = new LazyList[T] {
override def isEmpty = false
override def head = hd
override def tail = tl
}

val empty = new LazyList[Nothing] {
override def isEmpty = true
override def head = throw new NoSuchElementException("empty.head")
override def tail = throw new NoSuchElementException("empty.tail")
}
}

本节的习题

1
2
3
4
5
6
def lazyListRange(lo: Int, hi: Int): LazyList[Int] = {
print(lo+" ")
if (lo >= hi) LazyList.empty else LazyList.cons(lo, streamRange(lo+1, hi))
}

lazyListRange(1, 10).take(3) 输出什么
  • Nothing
  • 1
  • 1 2 3
  • 1 2 3 4
  • 1 2 3 4 5 6 7 8 9

Lazy Evaluation

什么是Lazy

Do things as late as possible and never do them twice.

这一点其实受到 Haskell 相当大的影响——这个语言默认就是 Lazy 计算的

为什么 Scala 不这样做呢?

Martin给出的解释:

Scala 允许可变的变量和副作用,这个和Lazy一起搞容易出玄学错误

e.g. 从 StackOverflow 找的一个典型例子

1
2
3
4
5
6
7
scala> def square(a: =>Int) = a * a
def square(a: => Int): Int

scala> square({println("calculating");5})
calculating
calculating
val res0: Int = 25

由于入参 a 是 Call by name 的形式,所以是被延迟计算的,这会导致在a * a的步骤中被调用了两次println的副作用——这恰恰是我们不希望发生,却又很容易被忽视的一个问题

所以 Scala 被设计成默认立即计算,但是也可以支持延迟计算

本节习题:

1
2
3
4
5
6
7
def expr = {
val x = { print("x"); 1}
lazy val y = { print("y"); 2}
def z = { print("z"); 3}
z + y + x + z + y + x
}
expr

执行expr的副作用导致输出结果是什么

  • zyxzyx
  • xzyz
  • xyzz
  • zyzz
  • something else

Computing with Infinite Sequences

本节简单介绍了下LazyList的应用

  • 筛法求素数
  • 牛顿开方

习题

1
2
3
4
val N = 3
def from(n: Int): LazyList[Int] = n #:: from(n + 1)
val xs = from(1) map (_ * N)
val ys = from(1) filter (_ % N == 0)

上面两个表达式哪个生成速度较快?

显然答案是上面那个表达式,因为map操作不需要额外生成新的元素,

filter操作则是每隔N个元素要判断N-1

Case Study: the Water Pouring Problem

本节探讨的问题是倒水问题

倒水问题的简单版本,就是已知有一个水龙头,和一个足够大的水槽,有两个不同容量,没有刻度的水杯。

现在允许做的操作有

  • 把水导入水槽
  • 从水龙头接水把杯子装满水
  • 把一个水杯的水倒入另外一个水杯,知道某个水杯为空或者倒满

现在问,为了量出若干容量的水,所需要的步骤是什么

这个问题讲的很好,Martin一步步抽象问题,解释每一步的意图。

这里就不具体讲代码了,可以直接看课程

编程作业Bloxorz

这个编程作业,是对一个游戏的简化版本自动求解,游戏可以在这里玩到

Game Setup

位置的定义如下

1
case class Pos(row: Int, col: Int)
  • 行坐标确定垂直方向的位置
  • 列坐标确定水平方向的位置
  • 坐标原点在左上角,坐标值从上到下,从左到右依次增加

这里用的是坐标系

1
2
3
4
5
6
7
8
9
10
  0 1 2 3   <- col axis
0 o o o o
1 o o o o
2 o # o o # is at position Pos(2, 1)
3 o o o o

^
|

row axis

我们这样定义地面(Terrain)

1
type Terrain = Pos => Boolean

地面可以使用StringParserTerrain.scala里的方法快速创建

我们需要先实现这个文件里的方法

1
2
def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean = ???
def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = ???

具体的要求,在对应的 Scaladoc 里能找到

一个简单的实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean = {
val rows = levelVector.length
val cols = levelVector.head.length
def valid(r: Int, c: Int): Boolean = {
r >= 0 && c >= 0 && r < rows && c < cols
}
(p: Pos) => valid(p.row, p.col) && levelVector(p.row)(p.col) != '-'
}

def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = {
val index = levelVector.flatten.indexWhere(p => p == c)
val cols = levelVector.head.length
Pos(index / cols, index % cols)
}

对场景的函数做好定义后,我们还需要定义好砖块

砖块可以被视为 2*1*1 的立方体

需要用两个字段来描述

1
case class Block(b1: Pos, b2: Pos)

砖块可以往平面上的四个方向滚动

需要实现这么几个函数

1
2
3
4
5
6
7
8
// 砖块是否处于直立状态
def isStanding: Boolean = ???

// 砖块是否处于地面上
def isLegal: Boolean = ???

// 砖块的初始状态
def startBlock: Block = ???

下面是一个简单的实现

1
2
3
def isStanding: Boolean = b1 == b2
def isLegal: Boolean = terrain(b1) && terrain(b2)
def startBlock: Block = Block(startPos, startPos)

如上所言,我们需要让砖块能在平面上的四个方向滚动,滚动时需要判定新位置是否合法

1
2
3
4
5
6
7
8
9
10
11
/**
* Returns the list of blocks that can be obtained by moving
* the current block, together with the corresponding move.
*/
def neighbors: List[(Block, Move)] = ???

/**
* Returns the list of positions reachable from the current block
* which are inside the terrain.
*/
def legalNeighbors: List[(Block, Move)] = ???

简单实现如下

1
2
3
4
5
6
7
8
9
10
11
12
def neighbors: List[(Block, Move)] = {
List(
(left, Left),
(right, Right),
(up, Up),
(down, Down)
)
}

def legalNeighbors: List[(Block, Move)] = {
neighbors.filter(x => terrain(x._1.b1) && terrain(x._1.b2))
}

Solving the Game

我们把前期的准备工作做完了,接下来就是具体的求解 Solver.scala 实现了

我们可以用LazyList[Block]来表示具体的解,但是从倒水问题的经验来看,还是很有必要保存之前达到过的状态的,避免重复走到之前走过的位置。

因此,我们用LazyList[(Block, List[Move])]来表示解答

其中,第二部分List[Move]表示之前的移动路径

最后一个移动路径,是List[Move]的首元素 (由于List在头部插入效率远高于尾部插入)

判断是否到达终点的代码很简单

1
2
3
def done(b: Block): Boolean = {
b.b1 == b.b2 && b.b1 == goal
}

然后是实现获取下一个状态, 并排除掉已经经过的状态

1
2
3
4
5
6
7
8
def neighborsWithHistory(b: Block, history: List[Move]): LazyList[(Block, List[Move])] = {
LazyList(b.legalNeighbors: _*).map{case (block, move) => (block, move :: history)}
}

def newNeighborsOnly(neighbors: LazyList[(Block, List[Move])],
explored: Set[Block]): LazyList[(Block, List[Move])] = {
neighbors.filter(b => !explored.contains(b._1))
}

Finding Solutions

现在问题的关键在如何求解

现在需要构造from函数,这个函数会更加初始砖块的位置和已经遍历过的位置,求出所有可能的解空间集合

1
2
def from(initial: LazyList[(Block, List[Move])],
explored: Set[Block]): LazyList[(Block, List[Move])] = ???

这里可以参照倒水问题的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
def from(initial: LazyList[(Block, List[Move])],
explored: Set[Block]): LazyList[(Block, List[Move])] = {
if (initial.isEmpty) LazyList.empty
else {
val more = for {
(block, history) <- initial
neighbors = neighborsWithHistory(block, history)
newNeighbors = newNeighborsOnly(neighbors, explored)
neighbor <- newNeighbors
} yield neighbor
initial #::: from(more, explored ++ more.map(_._1))
}
}

详细讲解下这段代码的意图

  • 首先处理传参为空的情况
  • 对于非空的情况,获取到当前状态的下一个状态
  • 过滤掉之前抵达过的砖块状态

把这些结果保存下来,作为下一步可以到达的解空间,同时维护已经抵达过的状态数

剩下的几个函数就是水到渠成的了

1
2
3
4
5
6
7
8
9
lazy val pathsFromStart: LazyList[(Block, List[Move])] = {
from(LazyList((startBlock, Nil)), Set[Block]())
}

lazy val pathsToGoal: LazyList[(Block, List[Move])] = {
pathsFromStart.filter(x => done(x._1))
}

lazy val solution: List[Move] = pathsToGoal.headOption.map(_._2).getOrElse(Nil).reverse