Contents

1. 1. 寒暄
2. 2. 正文
   1. 2.1. 环境准备
   2. 2.2. REPL
   3. 2.3. Evaluation Rules
   4. 2.4. 递归与尾递归
   5. 2.5. High order functions
   6. 2.6. Currying
   7. 2.7. Classes
   8. 2.8. Class Hierarchies
   9. 2.9. Class Organization
   10. 2.10. Polymorphism
   11. 2.11. Pattern Matching
   12. 2.12. Collections
   13. 2.13. Ordering
   14. 2.14. For-Comprehensions
   15. 2.15. Stream and Lazy Evaluation
3. 3. 作业
   1. 3.1. FuncSet
   2. 3.2. Huffman Code
   3. 3.3. Bloxorz
4. 4. 终于写完了

寒暄

昨天刚完成了Coursera上Scala课程的最后一周作业，十分激动兴奋！这门课由Scala的作者Martin Odersky亲自教授，展示了不少Scala尤其是应用函数式编程的最佳实践。学完有个最大的感受就是这门语言真的是非常复杂灵活，不知道跟C++相比如何（完全没学过C++）。每次做作业都会觉得可以实现的方式太多了（如果没有给出框架的话……），各种语法糖也是令人眼花缭乱，比起Perl，Ruby来真是有过之而无不及啊！如果光从教授函数式编程的方面来看，这门课跟Dan Grossman的Programming Language还是有点距离的，后者的讲解真是系统详尽，娓娓道来，让人回味无穷啊！

Scala这门课的讲课内容不多，很多作业练习据作者说是借鉴了神书SICP的，感觉的确还挺有趣的！为了加深理解，巩固记忆，就在这里略微总结一下知识点把！

正文

环境准备

第一周先介绍了Scala环境的安装准备，整个课程基本都是用sbt（类似maven）来构建项目，自动提交作业的，所以也没了解过不用sbt要怎么搞……sbt的具体介绍可以看这里。

IDE的话老师推荐的是Eclipse，不过出于对IntelliJ的疯狂热爱，我还是选了IntelliJ + Scala plugin，跟老师视频演示对比了下感觉成熟稳定性暂时还不及Eclipse，经常有些诡异的小问题，比如在worksheet里加package名限定的话evaluate时候输出直接是空白的……还有很多地方提示语法有问题，但是编译运行都可以通过……感觉Eclipse的Scala插件应该是亲生的，会比较靠谱些。

REPL

貌似现代语言没个REPL环境都不好意思出来混啊，Scala里也自带了REPL，直接敲Scala回车即可。不过我基本没怎么用过它，因为Scala里有更加牛逼的worksheet，也就是Swift里面的playground哈哈！另外有个IDE叫LightTable也附带了这个功能，在使用Clojure时表现良好，值得推荐！有了worksheet，实时编写实时显示结果，调试代码的确轻松愉快很多啊！

Evaluation Rules

Scala里默认用的是Call by value，另外一种是Call by name，有点像Haskell里的lazy evaluation，不知道怎么具体翻译，就给个例子吧：

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

一个简单的函数，直接返回第一个参数。值得注意的是Scala里的变量类型是放在后面的，跟Go和Swift一样哈哈。然后我们调用它：

first(1, loop)

这里loop是个无限循环，如果是默认的Call by value，Scala会先把每一个参数的value算出来再执行函数后面的代码逻辑，所以哪怕函数并没有用到第二个参数，这个调用还是会进入死循环。不过Scala的灵活牛逼之处立马就开始展现了，我们可以改写这个函数成：

def first(x: Int, y: => Int) = x

加了一个=>符号，这个参数立刻就成了Call by name，这样只有在用到它的时候才会去evaluate，哪怕是个无限循环也照样可以跑啦！这个技巧在之后讲到Streams时还会用到。

递归与尾递归

这个大家应该都知道吧，用递归的确能写出一些很漂亮的代码来……大多数例子都是阶乘，Fib函数之类，课程中用了个牛顿法算开方的：

def sqrt(x: Double) = {
  def sqrtIter(guess: Double): Double =
    if (isGoodEnough(guess)) guess
    else sqrtIter(improve(guess))
 
  def isGoodEnough(guess: Double): Boolean =
    math.abs(guess * guess - x) / x < 0.001
 
  def improve(guess: Double): Double =
    (guess + x / guess) / 2
  sqrtIter(1.0)
}

很直观吧！不过递归如果层数过深可能导致stack overflow的问题，所以就有了尾递归优化，比如这个例子：

def gcd(a: Int, b: Int): Int =
  if (b == 0) a else gcd(b, a % b)

这里进入if判断后如果条件不成立，就直接转到了函数本身的调用gcd(b, a % b)，相当于变成了一个等价的调用而不需要在stack上保留其它变量的信息，这样就可以重用这个stack了。但另一种常见的递归形式如下：

def factorial(n: Int): Int =
  if (n == 0) 1 else n * factorial(n - 1)

假设调用个factorial(4)，它需要一层一层展开直到4*(3*(2*(1*factorial(0))) -> 4*(3*(2*(1*1)))，每一层stack都要储存那个n的值等到下一层的函数返回后再做具体计算，所以就不能重用stack了！所以我们可以尽量对需要做层数很深的递归的函数进行优化改写成尾递归或者直接改成循环来做。

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)
}

Like this!用一个acc来存储中间结果并传到下一层去，算是个常用方法吧。另外Scala中还可以用@tailrec来指定函数必须为尾递归，否则会在编译时报错。

High order functions

这应该是FP里最著名的概念了吧。大致就是可以在一个函数里返回一个函数，也可以把函数作为参数传入一个函数……看看代码比较直观：

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

直接放了尾递归的版本，这个函数接受3个参数，第一个是一个输入一个Int返回一个Int的函数，后面a和b是sum的范围，比如从5累加到10之类。如果我们需要直接做累加，可以这样调用：sum(x => x, a, b)，如果要算立方和，就可以改成sum(x => x * x * x, a, b)，方便，优雅，高逼格！

Currying

又是一个很著名的概念，名字来源于Haskell Curry大神……我要是成了大神是不是也能像他那样名和姓还能分别来命名程序语言和编程技术……Currying，顾名思义，就是采用了这种牛逼的技术后的代码，会让使用者在阅读和应用过程中感受到若有若无的咖喱香，其中以青咖喱最为爽辣过瘾……好吧，正经点，传说中编程语言的函数在一开始都是只能接受单个参数的，那要传多个参数怎么办呢？那就传一个参数，返回一个函数，然后再传一个，再返回一个函数，and so on……比如还是我们的老朋友sum函数，现在它将披上咖喱的外衣……

def sum_c(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
}

简化一下

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

我们还可以用这个方法来写连乘的!

def product(f: Int => Int)(a: Int, b: Int): Int = {
  if (a > b) 1 else f(a) * product(f)(a + 1, b)
}

写个咖喱版阶乘！

def factorial(a: Int): Int = {
  product(x => x)(1, a)
}

就是这么简单！上面的sum和product长得很像，我们还可以提取一下共同点：

def mapReduce(f: Int => Int, combine:(Int, Int) => Int, zero: Int)(a: Int, b: Int): Int = {
  if (a > b) zero
  else combine(f(a), mapReduce(f, combine, zero)(a + 1, b))
}

于是就有了神奇的map-reduce！感觉我可以给这篇文章加上一个big-data的tag了有没有！
用新鲜火烫的mapReduce表达一下我们激动的心情：

def excitingProduct(f: Int => Int)(a: Int, b: Int): Int = {
  mapReduce(f, (x, y) => x * y, 1)(a, b)
}

另外还有个跟Currying不太一样的组合函数方式compose，比如我们定义一个简单的取绝对值开方函数：

def sqrt_of_abs(i: Int) = math.sqrt(intToDouble(math.abs(i)))

这里是连续调用3个函数，我们可以直接把它们拼在一起！

val sqrt_of_abs = math.sqrt _ compose intToDouble _ compose math.abs _

还可以按apply的次序来组合：

val sqrt_of_abs = math.abs _ andThen intToDouble _ andThen math.sqrt _

然后就可以直接调用sqrt_of_abs(-9)啦！

Classes

讲了半天FP，老师忽然来了个转折，开始介绍Scala中一些OO的概念，新一轮头脑风暴又开始了……类这个东西跟其他的OO语言还是挺像的，下面这个例子是实现一个有理数类：

class Rational(x: Int, y: Int) {
  require(y != 0, "demoninator must be non-zero")
 
  def this(x: Int) = this(x, 1)
 
  private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  private val g = gcd(x, y)
  def numer = x / g
  def denom = y / g
 
  def + (that: Rational) = {
    new Rational(
      numer * that.denom + that.numer * denom,
      denom * that.denom
    )
  }
 
  def unary_- : Rational = new Rational(-numer, denom)
 
  def - (that: Rational) = {
    this + -that
  }
 
  def * (that: Rational) = {
    new Rational(
      numer * that.numer,
      denom * that.denom
    )
  }
 
  def < (that: Rational) = numer * that.denom < that.numer * denom
 
  def max(that: Rational) = {
    if (this < that) that else this
  }
 
  override def toString = numer + "/" + denom
}

这里唯一有点奇怪的就是那个unary了，这里有一个关于为啥要用unary的解释！主要目的就是用它来实现一些前缀方法啦！（上例中是用它来表示负数）

Class Hierarchies

课上主要讲了abstract class，感觉跟别的语言里的抽象类也没啥区别，继承，override这些也都一样。另外Scala里的单例可以用object来实现：

abstract class TopLevel {     // abstract class  
  def method1(x: Int): Int   // abstract method  
  def method2(x: Int): Int = { ... }  
}
 
class Level1 extends TopLevel {  
  def method1(x: Int): Int = { ... }  
  override def method2(x: Int): Int = { ...} // TopLevel's method2 needs to be explicitly overridden  
}
 
object MyObject extends TopLevel { ... } // defines a singleton object. No other instance can be created

另外可以用带有main方法的object来创建一个可执行程序：

object Hello {  
  def main(args: Array[String]) = println("Hello world")  
}

Class Organization

Scala的命名空间，import之类也没什么特别之处，各种类可以放在package myPackage里，然后在使用的时候可以import myPackage.myClass或者import myPackage._来import所有内容，也可以选几个import比如import myPackage.{MyClass1, MyClass2}，import myPackage.{MyClass1 => A}。
Scala支持多重继承，这里又引入一个新的关键词trait：

trait Planar { ... }
class Square extends Shape with Planar

所有的classes, objects, traits可以继承最多一个class，但是可以继承任意多个traits（中英混合还考虑单复数，哥哥我真是严谨的一比）。Trait跟Java中的Interface很像，但是trait里是可以有field和具体实现的方法的！
另外还有Scala里的type继承关系图，懒得翻译了：

General object hierarchy:

• scala.Any base type of all types. Has methods hashCode and toString that can be overloaded
• scala.AnyVal base type of all primitive types. (scala.Double, scala.Float, etc.)
• scala.AnyRef base type of all reference types. (alias of java.lang.Object, supertype of java.lang.String, scala.List, any user-defined class)
• scala.Null is a subtype of any scala.AnyRef (null is the only instance of type Null), and scala.Nothing is a subtype of any other type without any instance.

然后老师还提了提fuctions as objects……哥不是函数式编程语言么，但是哥的函数也都是对象……就不怕搞不晕你！

trait Function1[A, B] {
  def apply(x: A): B
}

于是(x: Int) => x * x这样的一个函数，就变成了这样一个拥有apply方法的Object：

{ class AnonFun extends Function1[Int, Int] {
  def apply(x: Int) = x * x
  }
  new AnonFun
}

怎么样，有种天下大统的感觉了么？这个东西后面还会用到。不过这样的转化会发现Function1这个trait是接受单个参数的，上课时老师提到在Scala里建了很多种这种trait以处理多个参数的情况，目前最多是22个参数……这个感觉不是很优雅啊，像SML中所有函数都只接受一个参数，然后用pattern matching来做具体的“多参数”处理，然后函数直接就可以直接用类似Unix中的pipeline一样做流畅的链式调用，简洁优美啊！

另外老师还表示我大Scala是纯OO语言……比如自然数我们可以这么搞：

abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor = new Succ(this)
  def + (that: Nat): Nat
  def - (that: Nat): Nat
}
 
object Zero extends Nat {
  def isZero = true
  def predecessor = throw new Exception("Not a natrual number")
  def + (that: Nat): Nat = that
  def - (that: Nat): Nat = if (that.isZero) Zero else throw new Exception("Not a natrual number")
}
 
class Succ(n: Nat) extends Nat {
  def isZero = false
  def predecessor = n
  def + (that: Nat): Nat = new Succ(n + that)
  def - (that: Nat): Nat = if (that.isZero) this else n - that.predecessor
}

这种既OO又FP的感觉真是太酸爽太劲道了呢……

Polymorphism

这个部分是整个课程中比较复杂的部分了……包含subtyping和generics：

• generics，也就是一个函数或一个类的参数中可以用type parameter，大家应该都挺熟悉比如Java里的public class Entry<K, V>。
• subtyping，也就是说一个子类实例可以在要求为其父类实例的地方使用，这个也好理解，因为子类必定是实现了所有父类中的方法的嘛。

Scala中的generics：

class MyClass[T](arg1: T) { ... }
new MyClass[Int](1)
new MyClass(1)   // the type is being inferred, i.e. determined based on the value arguments

有时候会有需求说我这个Class只接受某种type的子类型，换作动态语言估计得用issubclass之类的方法来写了吧，Java中有<T extends Animal> void addAnimal(T animal)，其他不熟悉……但是我们高大上的Scala却有更加眼花缭乱的方法！这就是type bounds：

def myFct[T <: TopLevel](arg: T): T = { ... } // T must derive from TopLevel or be TopLevel
def myFct[T >: Level1](arg: T): T = { ... }   // T must be a supertype of Level1
def myFct[T >: Level1 <: Top Level](arg: T): T = { ... }

不得不承认，真是太酷炫了！甚至还能同时指定写成这样：[S >: NonEmpty <: IntSet]。看到这个，是不是有点 > . < 了……

另外一种是Variance，不知道怎么翻译，直接看例子：

比如一个父类为IntSet，其中有两个子类Empty和NonEmpty，已知NonEmpty <: IntSet，那么我们是否可以认为List[NonEmpty] <: List[IntSet]呢？直觉上是可以的，但是仔细一想会有问题，比如以下Java代码：

NonEmpty [] a = new NonEmpty []{ new NonEmpty (1 , Empty , Empty )}
IntSet [] b = a
b [0] = Empty
NonEmpty s = a [0]    // Boom!

可以看到我们在最后一行把一个Empty类型的变量assign给了NonEmpty类型变量！所以在可变类型中，这种covariant的关系是不存在的！

发现我还没写什么是covariant……

假设A <: B，C[T]是parameterized type，那么C[A] <: C[B]即为covariant，C[A] >: C[B]为contravariant

注意！Scala屌炸天的语法又要出现了！

class C[+A] { ... } // C is covariant
class C[-A] { ... } // C is contravariant
class C[A]  { ... } // C is nonvariant

呵呵，世界真奇妙！刚才我们说了，函数也是Object，所以还可以看看函数在输入和输出类型上到底是神马个关系，比如我们有两个函数：

type A = IntSet => NonEmpty
type B = NonEmpty => IntSet

那他们哪个是爸爸哪个是儿子呢！如果我们有个参数接受类型A，也就是输入一个IntSet输出一个NonEmpty，那我们能用B传进去吗？貌似不行哦，因为A里我还可以接受Empty呢，而B里面可能输出一个Empty又不满足是个NonEmpty，但是反过来就可以了！所以在这里A <: B！这就是函数类型的特殊variance规则，表示如下：

trait Function1[-T, +U] {
  def apply(x: T): U
} // Variance check is OK because T is contravariant and U is covariant

而之前那个generic array的继承关系的问题其实正好违反了这个规则：

class Array[+T] {
  def update(x: T)
} // variance checks fails

另一个例子是immutable的List类型，展现了如何正确地通过variance type check：

trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
  def prepend[U >: T](elem: U): List[U] = new Cons(elem, this)
}
 
class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
}
 
object Nil extends List[Nothing] {
  def isEmpty: Boolean = true
  def head: Nothing = throw new NoSuchElementException("Nil.head")
  def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

这里应用了两个关键点：

1. Nothing在Scala里是所有type的subtype，所以可以以此搞出一个Nil的单例来！
2. 应用了function的variance规则，在prepend方法里设置了lower bound。然后在一个List[NonEmpty]里prepend一个Empty，就会返回一个List[IntSet]！这个很牛逼了……大家理解一下……从此之后NonEmpty与Empty幸福地生活在了一起，而不用担心其中一个被抓出去调用一个它没有的方法！What a happy ending！

Pattern Matching

这个又是FP中比较常见的decomposing数据结构的方法。这个在Dan的课中也有很大篇幅的介绍，因为这涉及到了OO与FP思想的一些重要的不同。两门课都用了计算表达式这个例子，不过还是Dan讲的比较清晰啊！假设我们有各种类型，基类是Expr，然后一个表达式里可能有Int，有Add，有Negate，有Multiply等类型，然后每个类中都有一些共同的方法比如都可以eval（求值），可以toString来显示表达式等：

• 在OO中一般用的是继承和重载方法，这样在每个类里面实现各自的方法就可以处理不同情况了。所以我们只要在Int，Add等类里实现方法即可，而且要添加一个类也很方便。但是万一我们需要添加一个共同的方法，比如hasZero，那就得在每个类里都写一遍，会比较麻烦。
• 在FP中用的就是Pattern Matching了，一般是在各个处理方法中去match参数的类型，然后做相应的操作。优劣点跟上面OO的方法正好相反。
  正是因为OO与FP在decomposing上的不同，所以他们适用的范围也不同，比如OO就很适合GUI编程，因为对于界面元素的操作相对固定，就点击啊拖拽之类的，但是界面元素的种类却相当繁多，所以添加各种子类的case也要多一些。而很多其他的应用比如数据类型没什么变化，但是会增加很多不同的处理方式，那就可以考虑采用FP风格的pattern matching了！下面这个表格摘自Dan的课程，采用OOP时增加一行也就是一种类型是比较容易的，而要增加一种操作就要去修改你所有之前的类的实现了。FP则正好反之。当然OOP中也有解决这些问题的方法比如Visitor模式，就是不如FP那么自然啦。

	Eval	toString	hasZero
Int	…	…	…
Add	…	…	…
Negate	…	…	…
Multiply	…	…	…

在Scala中的Pattern Matching语法如下：

(someList: List[T]) match {
  case Nil => ...          // empty list
  case x :: Nil => ...     // list with only one element
  case List(x) => ...      // same as above
  case x :: xs => ...      // a list with at least one element. x is bound to the head,
                           // xs to the tail. xs could be Nil or some other list.
  case 1 :: 2 :: cs => ... // lists that starts with 1 and then 2
  case (x, y) :: ps => ... // a list where the head element is a pair
  case _ => ...            // default case if none of the above matches
}

和之前写过的SML比感觉基本没区别……不过Scala跟SML不同之处在于SML里用的是type来表示类型（如果没记错的话……）而在Scala里引入了case class这样就可以不需要调用new myClass就来做匹配了：

case object MyObject extends Somthing
case class MyClass(a: Int, b: Int)
unknownObject match {
  case MyObject => ...
  case MyClass(a, b) => ...
}

case class还有些别的特性比如自动生成了hashCode，equals方法等。具体可以参考这篇文章的详细介绍。

另外SML里有option类型的值，Scala也照单全收。比如如果直接访问Map类型中不存在的key会抛exception，而使用Map.get的方法则默认返回一个Option[T]，可能是Some[T]也可能是None：

val myMap = Map("a" -> 42, "b" -> 43)
def getMapValue(s: String): String = {
  myMap get s match {
    case Some(nb) => "Value found: " + nb
    case None => "No value found"
  }
}
getMapValue("a")  // "Value found: 42"
getMapValue("c")  // "No value found"

上面的代码还可以简写成：

def getMapValue(s: String): String =
  myMap.get(s).map("Value found: " + _).getOrElse("No value found")

恩，反正各种写法都可以，让人开始怀疑人生……另外还有遇到匿名函数时的简写法：

val pairs: List[(Char, Int)] = ('a', 2) :: ('b', 3) :: Nil
val chars: List[Char] = pairs.map(p => p match {
  case (ch, num) => ch
})

=>

val chars: List[Char] = pairs map {
  case (ch, num) => ch
}

Collections

Scala里的各种collections也是大杂烩啊，包含了普通语言中常见的那些Array, List, Map, Set，也有FP中经典的Tuple，Stream……借用一下别人的归纳：

基类

• Iterable
• Seq
• Set
• Map

不可变类

• List (linked list, provides fast sequential access)
• Stream (same as List, except that the tail is evaluated only on demand)
• Vector (array-like type, implemented as tree of blocks, provides fast random access)
• Range (ordered sequence of integers with equal spacing)
• String (Java type, implicitly converted to a character sequence, so you can treat every string like a Seq[Char])
• Map (collection that maps keys to values)
• Set (collection without duplicate elements)

可乱变类

• Array (Scala arrays are native JVM arrays at runtime, therefore they are very performant)
• scala.collection.mutable.Map and scala.collection.mutable.Set (除非默认的Map，Set性能太差，否则不建议使用)

直接从wiki拖个例子列表：

val fruitList = List("apples", "oranges", "pears")
// Alternative syntax for lists
val fruit = "apples" :: ("oranges" :: ("pears" :: Nil)) // parens optional, :: is right-associative
fruit.head   // "apples"
fruit.tail   // List("oranges", "pears")
val empty = List()
val empty = Nil
 
val nums = Vector("louis", "frank", "hiromi")
nums(1)                     // element at index 1, returns "frank", complexity O(log(n))
nums.updated(2, "helena")   // new vector with a different string at index 2, complexity O(log(n))
 
val fruitSet = Set("apple", "banana", "pear", "banana")
fruitSet.size    // returns 3: there are no duplicates, only one banana
 
val r: Range = 1 until 5 // 1, 2, 3, 4
val s: Range = 1 to 5    // 1, 2, 3, 4, 5
1 to 10 by 3  // 1, 4, 7, 10
6 to 1 by -2  // 6, 4, 2
 
val s = (1 to 6).toSet
s map (_ + 2) // adds 2 to each element of the set
 
val s = "Hello World"
s filter (c => c.isUpper) // returns "HW"; strings can be treated as Seq[Char]
 
// Operations on sequences
val xs = List(...)
xs.length   // number of elements, complexity O(n)
xs.last     // last element (exception if xs is empty), complexity O(n)
xs.init     // all elements of xs but the last (exception if xs is empty), complexity O(n)
xs take n   // first n elements of xs
xs drop n   // the rest of the collection after taking n elements
xs(n)       // the nth element of xs, complexity O(n)
xs ++ ys    // concatenation, complexity O(n)
xs.reverse  // reverse the order, complexity O(n)
xs updated(n, x)  // same list than xs, except at index n where it contains x, complexity O(n)
xs indexOf x      // the index of the first element equal to x (-1 otherwise)
xs contains x     // same as xs indexOf x >= 0
xs filter p       // returns a list of the elements that satisfy the predicate p
xs filterNot p    // filter with negated p 
xs partition p    // same as (xs filter p, xs filterNot p)
xs takeWhile p    // the longest prefix consisting of elements that satisfy p
xs dropWhile p    // the remainder of the list after any leading element satisfying p have been removed
xs span p         // same as (xs takeWhile p, xs dropWhile p)
 
List(x1, ..., xn) reduceLeft op    // (...(x1 op x2) op x3) op ...) op xn
List(x1, ..., xn).foldLeft(z)(op)  // (...( z op x1) op x2) op ...) op xn
List(x1, ..., xn) reduceRight op   // x1 op (... (x{n-1} op xn) ...)
List(x1, ..., xn).foldRight(z)(op) // x1 op (... (    xn op  z) ...)
 
xs exists p    // true if there is at least one element for which predicate p is true
xs forall p    // true if p(x) is true for all elements
xs zip ys      // returns a list of pairs which groups elements with same index together
xs unzip       // opposite of zip: returns a pair of two lists
xs.flatMap f   // applies the function to all elements and concatenates the result
xs.sum         // sum of elements of the numeric collection
xs.product     // product of elements of the numeric collection
xs.max         // maximum of collection
xs.min         // minimum of collection
xs.flatten     // flattens a collection of collection into a single-level collection
xs groupBy f   // returns a map which points to a list of elements
xs distinct    // sequence of distinct entries (removes duplicates)
 
x +: xs  // creates a new collection with leading element x
xs :+ x  // creates a new collection with trailing element x
 
// Operations on maps
val myMap = Map("I" -> 1, "V" -> 5, "X" -> 10)  // create a map
myMap("I")      // => 1  
myMap("A")      // => java.util.NoSuchElementException  
myMap get "A"   // => None 
myMap get "I"   // => Some(1)
myMap.updated("V", 15)  // returns a new map where "V" maps to 15 (entry is updated)
                        // if the key ("V" here) does not exist, a new entry is added
 
// Operations on Streams
val xs = Stream(1, 2, 3)
val xs = Stream.cons(1, Stream.cons(2, Stream.cons(3, Stream.empty))) // same as above
(1 to 1000).toStream // => Stream(1, ?)
x #:: xs // Same as Stream.cons(x, xs)
         // In the Stream's cons operator, the second parameter (the tail)
         // is defined as a "call by name" parameter.
         // Note that x::xs always produces a List
 
val pair = ("answer", 42)   // type: (String, Int)
val (label, value) = pair   // label = "answer", value = 42  
pair._1 // "answer"  
pair._2 // 42

这下大家满足了吧！某一周的作业就是用这些方法来写一个霍夫曼树编码，相当精炼的感觉！重点来几个语法糖酷炫一下：

def sum(xs: List[Int]): Int = xs match {
  case Nil => 0
  case y :: ys => y + sum(ys)
}

这是最初版本，然后我们用上reduceLeft：

def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x, y) => x + y)

恩，怎么有个0 :: xs，不优雅！换foldLeft，顺便把那个匿名函数也搞成颜文字把！

def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _)

简单吗？还可以更犀利！

def sum(xs: List[Int]) = (0/:xs) (_ + _)

这样是不是不太好啊！

Ordering

写了这么多有点累了，接下来写的简洁点，如果不够以后再补充。Ordering主要是实现了一些比较函数如lt()，gt()等，我们可以利用它（大多数还是上面的collection的操作）来写个merge sort：

import math.Ordering  
 
def msort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
  val n = xs.length / 2
  if (n == 0) xs
  else {
    def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x :: xs1, y :: ys1) => {
        if (ord.lt(x, y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
      }
    }
    val (fst, snd) = xs splitAt n
    merge(msort(fst), msort(snd))
  }
}
msort(fruits)(Ordering.String)
msort(fruits)   // the compiler figures out the right ordering

这样就可以自动对数字或者字符排序了！当然Scala其实自己也有很多排序函数，比如可以这样对一个Map根据其Key的长度来排序：

myMap.toSeq.sortBy(_._1.length).reverse

For-Comprehensions

Scala的for语句还是很有特色的，大致的形式就是for (s) yield e其中s中是生成器（p <- e）和过滤器（if cond），如果有多个生成器就相当于多重循环了！最后的e是要返回的内容，然后可以把整个返回的内容作为一个collection再应用上面列举的那些方法做各种处理。示范代码：

// list all combinations of numbers x and y where x is drawn from
// 1 to M and y is drawn from 1 to N
for (x <- 1 to M; y <- 1 to N)
  yield (x,y)

这还不够，课程中还提到for语句可以完全转换成另一种形式：

(1 to M) flatMap (x => (1 to N) map (y => (x, y)))

详细的规则如下：

• for (x <- e1) yield e2 is translated to e1.map(x => e2)
• for (x <- e1 if f; s) yield e2 is translated to for (x <- e1.withFilter(x => f); s) yield e2
• for (x <- e1; y <- e2; s) yield e3 is translated to e1.flatMap(x => for (y <- e2; s) yield e3)

再来个应用例子：

for {
  i <- 1 until n
  j <- 1 until i
  if isPrime(i + j)
} yield (i, j)

就可以直接转化成：

(1 until n) flatMap (i => (1 until i) withFilter (j => isPrime(i+j))
  map (j => (i, j)))

也就是说如果你在类中定义了flatMap，withFilter，map就可以自由地对你的类型使用for语句啦！(类似实现Iterator？)

课上还用它写了个实际的8皇后问题：

def isSafe(col: Int, queens: List[Int]): Boolean = {
  val row = queens.length
  val queensWithRow = (row - 1 to 0 by -1) zip queens
  queensWithRow forall {
    case (r, c) => col != c && math.abs(col - c) != row - r
  }
}
 
def queens(n: Int): Set[List[Int]] = {
  def placeQueens(k: Int): Set[List[Int]] = {
    if (k == 0) Set(List())
    else for {
      queens <- placeQueens(k - 1)
      col <- 0 until n
      if isSafe(col, queens)
    } yield col :: queens
  }
  placeQueens(n)
}
 
def show(queens: List[Int]) = {
  val lines = {
    for (col <- queens.reverse)
    yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString
  }
  "\n" + (lines mkString "\n")
}
(queens(8) take 1 map show) mkString "\n"

Stream and Lazy Evaluation

Stream也是在collections里的一种，但它性质有些特别，所以就单独拿出来看一下。Stream基本可以当成一个惰性求值的list来看，课上给了一个这样的例子：

((1000 to 10000) filter isPrime)(1)

这行代码会寻找在1000到10000范围内的质数，然后取第2个。但虽然我们只需要取2个质数，程序还是会先把所有在范围内的质数取出来再取第二个，浪费了很多无用的计算。这时候就可以利用我们的stream来优化性能了：

((1000 to 10000).toStream filter isPrime)(1)

还可以生成无限长度的序列并进行计算：

def from(n: Int): Stream[Int] = n #:: from(n+1)
val nats = from(0)
def sieve(s: Stream[Int]): Stream[Int] =
  s.head #:: sieve(s.tail filter (_ % s.head != 0))
val primes = sieve(from(2))
primes.take(10).toList

这里首先是生成一个自然数的stream，然后sieve函数取出这个stream的头，把后面所有能被它整除的数都过滤掉，这样就可以生成一个质数的stream，看起来挺违反直觉的，不过课上有详细的展开，我们这边就拿个最简单的take(1)来看下吧：

(from(2).head #:: sieve(from(2).tail filter (_ % from(2).head != 0))).take(1)

然后由于是个stream，#::操作符后面那部分是惰性求值的，这里跑take(1)所以直接拿from(2).head就行了，后面的都不会被求值，最终输出2。

Racket跟Scala一样是call-by-value的，所以函数中的参数也必须先求值。但Racket里也可以生成stream，用的是一种叫thunk的技术！大致就是把函数原来的参数变成一个匿名函数，只有在call它的时候才会去求值，然后同理就可以用递归构造出一个无穷的stream来啦！

另外Scala里的lazy evaluation还可以用来做mutual recursion，来解释一些哲学问题：

class Chicken (e: => Egg) {
  lazy val offspring = e
}
 
class Egg (c: => Chicken) {
  lazy val mother = c
}
 
lazy val chicken: Chicken = new Chicken(egg)
lazy val egg: Egg         = new Egg(chicken)

作业

最后讲讲这门课的作业吧！总共7周的作业，选几个有趣的来看看。

FuncSet

这个作业是用函数方式来表示一个集合（Set）。我们传统概念中的集合，自然而然会联想到数组啊链表啊这样的数据结构，然后在此基础上去实现集合的各种接口。但是在这个作业里，我们要用函数来表示一个集合，用操作集合的规范来定义这个集合。这么说有点抽象，可以直接看代码：

type Set = Int => Boolean
def contains(s: Set, elem: Int): Boolean = s(elem)
def singletonSet(elem: Int): Set = (i: Int) => i == elem
def union(s: Set, t: Set): Set = (i: Int) => s(i) || t(i)
def intersect(s: Set, t: Set): Set = (i: Int) => s(i) && t(i)
def diff(s: Set, t: Set): Set = (i: Int) => s(i) && !t(i)
def filter(s: Set, p: Int => Boolean): Set = (i: Int) => s(i) && p(i)
val bound = 1000
def forall(s: Set, p: Int => Boolean): Boolean = {
  def iter(a: Int): Boolean = {
    if (a > bound) true
    else if (s(a) && !p(a)) false
    else iter(a + 1)
  }
  iter(-bound)
}
def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, !p(_))
def map(s: Set, f: Int => Int): Set = (i: Int) => exists(s, f(_) == i)

直接用了(Int => Boolean)的函数来表示一个集合，然后各种操作也都是去改变这个函数的行为。不过用这种方式没法做出一个迭代器来，要改成线性表形式才行。当然线性表形式结构也是可以用函数式方法来表示的。

Huffman Code

用Scala来实现Huffman编码，与实际问题结合更能体验函数式编程的表达方式。给出的框架代码把问题分割地很好，只要一块一块实现下来就行，每个函数基本上都在十行以内，逻辑也很顺畅明了：

// Huffman code tree的类定义
  abstract class CodeTree
  case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree
  case class Leaf(char: Char, weight: Int) extends CodeTree
 
// 统计char的出现次数
  def times(chars: List[Char]): List[(Char, Int)] = {
    def incr(acc: Map[Char, Int], c: Char) = {
      val count = (acc get c).getOrElse(0) + 1
      acc + ((c, count))
    }
    (Map[Char, Int]() /: chars)(incr).toList
  }
 
// 生成叶子节点的list，每个char出现的次数即为节点的权重
  def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = freqs.sortBy(_._2) map((f) => Leaf(f._1, f._2))
 
// 把上面生成的叶子节点的list缓缓地merge成一整棵树！
// Huffman code tree中出现频数最小的char应该在树中的层越深，所以在merge过程中保持排序
  def combine(trees: List[CodeTree]): List[CodeTree] = trees match {
    case left :: right :: cs => (makeCodeTree(left, right) :: cs).sortBy(weight(_))
    case _ => trees
  }
 
  def until(isSingleton: List[CodeTree] => Boolean, combineTree: List[CodeTree] => List[CodeTree])
           (listOfTree: List[CodeTree]): CodeTree = {
    if(isSingleton(listOfTree)) listOfTree.head
    else until(isSingleton, combineTree)(combineTree(listOfTree))
  }
 
  def createCodeTree(chars: List[Char]): CodeTree = {
    until(singleton, combine)(makeOrderedLeafList(times(chars)))
  }
 
// Decode - 根据生成的树来decode，走到leaf就表示成功decode了一个char
  def decode(tree: CodeTree, bits: List[Bit]): List[Char] = {
    def travel(remainingTree: CodeTree, remainingBits: List[Bit]): List[Char] = remainingTree match {
      case Leaf(c, _) => {
        if (remainingBits.isEmpty) List(c)
        else c :: travel(tree, remainingBits)
      }
      case Fork(left, right, _, _) => {
        if (remainingBits.head == 0) travel(left, remainingBits.tail)
        else travel(right, remainingBits.tail)
      }
    }
    travel(tree, bits)
  }
 
// Encode - 同理，根据生成的树来encode
  def encode(tree: CodeTree)(text: List[Char]): List[Bit] = {
    def lookup(tree: CodeTree)(char: Char): List[Bit] = tree match {
      case Leaf(_, _) => List[Bit]()
      case Fork(left, right, _, _) => {
        if (chars(left).contains(char)) 0 :: lookup(left)(char)
        else 1::lookup(right)(char)
      }
    }
    if (text.length == 0) List[Bit]()
    else lookup(tree)(text.head) ::: encode(tree)(text.tail)
  }
 
// 已经这么长了后面的就不贴了吧，还可以先把codeTree转成一个Map来做快速encode，做做性能优化
...

Bloxorz

这是最后一次作业，用stream来解决一个游戏的解法问题。就那么几行代码，就写出了一个bfs……

def from(initial: Stream[(Block, List[Move])],
         explored: Set[Block]): Stream[(Block, List[Move])] = {
  if (initial.isEmpty) Stream.Empty
  else {
    val more = for {
      (block, moves) <- initial
      newNeighbor <- newNeighborsOnly(neighborsWithHistory(block, moves), explored)
    } yield newNeighbor
    initial ++ from(more, explored ++ (more map (x => x._1)))
  }
}
 
lazy val pathsFromStart: Stream[(Block, List[Move])] = from(Stream.cons((startBlock, List()), Stream.Empty), Set(startBlock))
 
lazy val pathsToGoal: Stream[(Block, List[Move])] = pathsFromStart filter (p => done(p._1))
 
lazy val solution: List[Move] = {
  if (pathsToGoal.isEmpty) List()
  else pathsToGoal.head._2
}

当然真实的游戏还有机关什么的会更复杂点……应该很多人都玩过吧，大家可以在这里重温一下。

终于写完了

今天真是有意义的一天！