4
20
2013

Scala学习笔记-Part.02

样本类和模式匹配

样本类（case class）和模式匹配（pattern matching）。

简单的例子

假设要建立一个操作数学表达式的库，就要先定义输入的数据。为了简单，现在只关注由变量、数字、一元及二元操作符组成的数学表达式上：

样本类

  abstract class Expr
  case class Var(name: String) extends Expr
  case class Number(num: Double) extends Expr
  case class UnOp(operator: String, arg: Expr) extends Expr
  case class BinOp(operator: String,
      left: Expr, right: Expr) extends Expr

上面为表达式定义了一个抽象的基类，四个子类分别代表四种具体的表达式。要注意的是每个子类都有一个case修饰符，会被编译器识别为样本类。

样本类在使用工厂方法创建时可以省掉new：

val v = Var("x")

这个特点让方法嵌套时少写new让代码看起来更加简洁：

val op = binOp("+", Number(1), v)

样本类的另一个特点是参数列表中所有的参数隐式获得了val前缀，被作为字段维护：

scala> v.name
res0: String = x

scala> op.left
res1: Expr = Number(1.0)

编译器为样本类添加了可读性更强的toString、hashCode和equals方法：

  scala> println(op)
  BinOp(+,Number(1.0),Var(x))

  scala> op.right == Var("x")
  res3: Boolean = true

先来看一下格式。在格式上相当于把Java的switch格式：

  switch (selector) { alternatives }

中括号里的选择器移到了match关键字的前面：

  selector match { alternatives }

下面了一些基本的数学简化操作。下面的操作不用计算，因为值是不会变的：

  UnOp("-", UnOp("-", e)) => e // 负负得正
  BinOp("+", e, Number(0)) => e // 加0
  BinOp("*", e, Number(1)) => e // 乘1

定义一个simplifyTop来简化运算：

  def simplifyTop(expr: Expr): Expr = expr match {
    case UnOp("-", UnOp("-", e)) => e // Double negation
    case BinOp("+", e, Number(0)) => e // Adding zero
    case BinOp("*", e, Number(1)) => e // Multiplying by one
    case _ => expr
  }

方法simplifyTop接收一个Expr类型的参数。这里参数expr作为选择器匹配各个备选项，_为通配模式能匹配所有的值，相当于Java中的default。箭头=>分开的模式与表达式。调用：

  scala> simplifyTop(UnOp("-", UnOp("-", Var("x"))))
  res4: Expr = Var(x)

match是一种表达式，所以有返回结果。
一个case不会走到下一个case。
如果一项也没有匹配成功，会抛出MatchError异常。如果不想要异常要么把所有可能性都写上；要么加一个_的默认情况。

  expr match {
    case BinOp(op, left, right) =>
      println(expr +" is a binary operation")
    case _ =>
  }

这个表达式在两种情况下都会返回Unit值'()'。

模式的种类

通配模式

通配模式“_”匹配所有的结果：

  expr match {
    case BinOp(op, left, right) =>
      println(expr +"is a binary operation")
    case _ =>
  }

通配符还可以省略省略不用关注的内容，比如函数的参数名：

  expr match {
    case BinOp(_, _, _) => println(expr +"is a binary operation")
    case _ => println("It's something else")
  }

常量模式

任何字面量都可以用作常量，如nil，5，true和"hello"：

  def describe(x: Any) = x match {
    case 5 => "five"
    case true => "truth"
    case "hello" => "hi!"
    case Nil => "the empty list"
    case _ => "something else"
  }

效果：

  scala> describe(5)
  res5: java.lang.String = five

  scala> describe(true)
  res6: java.lang.String = truth

  scala> describe("hello")
  res7: java.lang.String = hi!

  scala> describe(Nil)
  res8: java.lang.String = the empty list

  scala> describe(List(1,2,3))
  res9: java.lang.String = something else

变量模式

变量类似通配模式，只不过有个变量名所以可以在后面的表达式中操作这个变量：

  expr match {
    case 0 => "zero"
    case somethingElse => "not zero: "+ somethingElse
  }

变量模式与常量模式的区别

常量不止有字面形式，还有用符号名的（比如Nil）。这样看起来就很容易与变量模式搞混：

  scala> import Math.{E, Pi}
  import Math.{E, Pi}

  scala> E match {
       | case Pi => "strange math? Pi = "+ Pi
       | case _ => "OK"
       | }
  res10: java.lang.String = OK

上面的E与Pi都是常量。对Scala编译器来说小写字母开头都作为变量，其他引用被认为是常量。下面的例子中想建立一个小写的pi就匹配到常量Pi了：

  scala> val pi = Math.Pi
  pi: Double = 3.141592653589793

  scala> E match {
       | case pi => "strange math? Pi = "+ pi
       | }
  res11: java.lang.String = strange math? Pi = 2.7182818...

在这个变量模式情况下，不能使用通配模式。因为变量模式已经可以匹配所有情况了：

  scala> E match {
       | case pi => "strange math? Pi = "+ pi
       | case _ => "OK"
       | }
  <console>:9: error: unreachable code
           case _ => "OK"
                     ^

其实也有强制使用小写常量名的方式：this.pi或obj.pi的形式表示是常量模式；如果这样还没有用，可以用反引号包起来，如：

  scala> E match {
       | case `pi` => "strange math? Pi = "+ pi
       | case _ => "OK"
       | }
  res13: java.lang.String = OK

反引号也可以用来处理其他的编码问题，如对于标识符来说，因为yield是Scala的保留字所以不能写Thread.yield()，但可以写成：

Thread.`yield`()

构造器模式

这个模式是真正牛X的模式，不仅检查对象是否是样本类的成员，还检查对象的构造器参数是否符合指定模式。

Scala的模式支持深度匹配（deep match）。不止检查对象是否一致而且还检查对象的内容是否匹配内层模式。由于额外的模式自身可以形成构造器模式，因此可以检查到对象内部的任意深度。

如下面的代码不仅检查了顶层的对象是BinOp，而且第三个构造参数是Number，而且它的值为0：

  expr match {
    case BinOp("+", e, Number(0)) => println("a deep match")
    case _ =>
  }

序列模式

指定匹配序列中任意元素，如指定开始为0：

  expr match {
    case List(0, _, _) => println("found it")
    case _ =>
  }

不固定长度用_*：

  expr match {
    case List(0, _*) => println("found it")
    case _ =>
  }

元组模式

  def tupleDemo(expr: Any) =
    expr match {
      case (a, b, c) => println("matched "+ a + b + c)
      case _ =>
    }

调用：

  scala> tupleDemo(("a ", 3, "-tuple"))
  matched a 3-tuple

类型模式

可以当成类型测试和类型转换的简易替代：

  def generalSize(x: Any) = x match {
    case s: String => s.length
    case m: Map[_, _] => m.size
    case _ => -1
  }

调用的例子：

  scala> generalSize("abc")
  res14: Int = 3

  scala> generalSize(Map(1 -> 'a', 2 -> 'b'))
  res15: Int = 2

  scala> generalSize(Math.Pi)
  res16: Int = -1

注意方法中s和x虽然都指向同一个对象，但一个类型是String一个类型是Any。所以可以写成s.length不可以写成x.length。

另一个测试类型的方法：

expr.isInstanceOf[String]

另一个转换类型的方法：

expr.asInstanceOf[String]

使用类型转换的例子：

  if (x.isInstanceOf[String]) {
    val s = x.asInstanceOf[String]
    s.length
  } else ...

类型擦除

和Java一样，对于除了数组以外其他集合都采用了泛型擦除（erasure）。就是在运行时不知道集合泛型类型。

如对于Map[Int,Int]，到了运行时就不知道两个类型是什么类型了。所以对于泛型的模式匹配，编译器会有警告信息：

  scala> def isIntIntMap(x: Any) = x match {
       | case m: Map[Int, Int] => true
       | case _ => false
       | }
  warning: there were unchecked warnings; re-run with
     -unchecked for details
  isIntIntMap: (Any)Boolean

在启动编译器时加上检查开关可以看到更多详细信息：

  scala> :quit
  $ scala -unchecked
  Welcome to Scala version 2.7.2
  (Java HotSpot(TM) Client VM, Java 1.5.0_13).
  Type in expressions to have them evaluated.
  Type :help for more information.

scala> def isIntIntMap(x: Any) = x match {
     | case m: Map[Int, Int] => true
     | case _ => false
     | }
  <console>:5: warning: non variable type-argument Int in
  type pattern is unchecked since it is eliminated by erasure
           case m: Map[Int, Int] => true
                   ^

所以对于不同的类型，上面函数结果都是true：

  scala> isIntIntMap(Map(1 -> 1))
  res17: Boolean = true

  scala> isIntIntMap(Map("abc" -> "abc"))
  res18: Boolean = true

数组和Java一样，是没有类型擦除的：

  scala> def isStringArray(x: Any) = x match {
       | case a: Array[String] => "yes"
       | case _ => "no"
       | }
  isStringArray: (Any)java.lang.String

  scala> val as = Array("abc")
  as: Array[java.lang.String] = Array(abc)

  scala> isStringArray(as)
  res19: java.lang.String = yes

  scala> val ai = Array(1, 2, 3)
  ai: Array[Int] = Array(1, 2, 3)

  scala> isStringArray(ai)
  res20: java.lang.String = no

变量绑定

除了独立的变量模式外，还可以对任何其他模式添加变量。作用时在匹配成功后，变量就是匹配成功的对象了。方式为写上变量名、一个@符号和模式。

比如要匹配abs出现了两次的地方（做了两次绝对值计算等于没有算）：

  expr match {
    case UnOp("abs", e @ UnOp("abs", _)) => e
    case _ =>
  }

守卫模式

Scala要求模式是线性的，即模式变量只能在模式中出现一次。

如，想要把e+e这个重复加法替换成乘法e*2：

  BinOp("+", Var("x"), Var("x"))

等于：

  BinOp("*", Var("x"), Number(2))

用下面的方式x重复出现了，所以有问题：

  scala> def simplifyAdd(e: Expr) = e match {
       | case BinOp("+", x, x) => BinOp("*", x, Number(2))
       | case _ => e
       | }
  <console>:10: error: x is already defined as value x
           case BinOp("+", x, x) => BinOp("*", x, Number(2))
                              ^

守卫模式（pattern guard）很像for循环中的if过滤条件。接在匹配模式后面的、用if开始的、使用模式中变量的表达式：

  scala> def simplifyAdd(e: Expr) = e match {
       | case BinOp("+", x, y) if x == y =>
       | BinOp("*", x, Number(2))
       | case _ => e
       | }
  simplifyAdd: (Expr)Expr

其他的例子，如只匹配正整数和只匹配以a开始的字符串：

  // match only positive integers
  case n: Int if 0 < n => ...

  // match only strings starting with the letter `a'
  case s: String if s(0) == 'a' => ...

模式重叠

  def simplifyAll(expr: Expr): Expr = expr match {
    case UnOp("-", UnOp("-", e)) =>
      simplifyAll(e) // `-' is its own inverse
    case BinOp("+", e, Number(0)) =>
      simplifyAll(e) // `0' is a neutral element for `+'
    case BinOp("*", e, Number(1)) =>
      simplifyAll(e) // `1' is a neutral element for `*'
    case UnOp(op, e) =>
      UnOp(op, simplifyAll(e))
    case BinOp(op, l, r) =>
      BinOp(op, simplifyAll(l), simplifyAll(r))
    case _ => expr
  }

注意这个方法的第四个和第五个匹配样本的参数都是变量，而且对应的操作采用递归。因为四和五的匹配范围比前三个更加广，所以建立放在后面。如果放在前面的话会有警告。

如下面的第一个样本能匹配任何第二个样本能匹配的情况：

  scala> def simplifyBad(expr: Expr): Expr = expr match {
       | case UnOp(op, e) => UnOp(op, simplifyBad(e))
       | case UnOp("-", UnOp("-", e)) => e
       | }
  <console>:17: error: unreachable code
           case UnOp("-", UnOp("-", e)) => e
                                           ^

封闭类

前面说过Scala里如果所有的样本都没有匹配，那是会抛异常的。为了全都匹配，程序员会给匹配加上一个默认匹配项处理默认情况。

实际上Scala编译器已经可以检测match表达式中遗漏的情况，但新的样本类可以定义在任何地方。比如我们的Expr有四个样本类，但可以在别的编译单元中再写其他的实现类。

所以有一个方案：让样本类的超类被封闭（sealed），这样就不能在别的文件中添加新的子类。格式只要加一个sealed关键字：

  sealed abstract class Expr
  case class Var(name: String) extends Expr
  case class Number(num: Double) extends Expr
  case class UnOp(operator: String, arg: Expr) extends Expr
  case class BinOp(operator: String,
      left: Expr, right: Expr) extends Expr

如果代码里漏掉可能的模式：

  def describe(e: Expr): String = e match {
    case Number(_) => "a number"
    case Var(_) => "a variable"
  }

编译器会警告UnOp和BinOp没有处理：

  warning: match is not exhaustive!
  missing combination UnOp
  missing combination BinOp

如果程序员确实知道这两种情况不可能发生，就是要在这两种情况下抛异常。可以手动加上让编译器闭嘴：

  def describe(e: Expr): String = e match {
    case Number(_) => "a number"
    case Var(_) => "a variable"
    case _ => throw new RuntimeException // Should not happen
  }

还有一个方法是对变量e添加注释@unchecked：

  def describe(e: Expr): String = (e: @unchecked) match {
    case Number(_) => "a number"
    case Var(_) => "a variable"
  }

Option类型

非必填类型：可以存值，也可以为None对象代表没有值。形式为Some(x)，x表示非必要。比如Scala的Map类型：

  scala> val capitals =
       | Map("France" -> "Paris", "Japan" -> "Tokyo")
  capitals:
    scala.collection.immutable.Map[java.lang.String,
    java.lang.String] = Map(France -> Paris, Japan -> Tokyo)

  scala> capitals get "France"
  res21: Option[java.lang.String] = Some(Paris)

  scala> capitals get "North Pole"
  res22: Option[java.lang.String] = None

应用模式匹配处理有值和没有值的情况：

  scala> def show(x: Option[String]) = x match {
       | case Some(s) => s
       | case None => "?"
       | }
  show: (Option[String])String

  scala> show(capitals get "Japan")
  res23: String = Tokyo

  scala> show(capitals get "France")
  res24: String = Paris

  scala> show(capitals get "North Pole")
  res25: String = ?

在Java里Map没有值时返回的是null，如果忘记检查会引起空指针异常。而在Scala里对于一个Map[Int,Int]是不可能返回null的。

使用Option类型的优点在于：

Option[String]从字面上看就已经提醒了程序员内容可能为None；
在Java中如果变量为空要到运行时才抛出空指针异常，而Scala中Option类型让编译器就已经提供了检查：编译器会在把Option[String]当作String使用时报错。

模式无处不在

变量定义

通过类型定义变量：

  scala> val myTuple = (123, "abc")
  myTuple: (Int, java.lang.String) = (123,abc)

用模式匹配代替类型声明：

  scala> val (number, string) = myTuple
  number: Int = 123
  string: java.lang.String = abc

这种方式用在指定精确类型的样本类时用得比较多：

  scala> val exp = new BinOp("*", Number(5), Number(1))
  exp: BinOp = BinOp(*,Number(5.0),Number(1.0))

  scala> val BinOp(op, left, right) = exp
  op: String = *
  left: Expr = Number(5.0)
  right: Expr = Number(1.0)

偏函数的样本序列

花括号case对应的样本本来就是函数字面量，可以用在任何用函数字面量的地方。而且还是有相当多个可选的函数字面量。如：

  val withDefault: Option[Int] => Int = {
    case Some(x) => x
    case None => 0
  }

调用：

  scala> withDefault(Some(10))
  res25: Int = 10

  scala> withDefault(None)
  res26: Int = 0

这样的方式很适合Actor应用：

  react {
    case (name: String, actor: Actor) => {
      actor ! getip(name)
      act()
    }
    case msg => {
      println("Unhandled message: "+ msg)
      act()
    }
  }

顺带提一下应用在偏（partial）函数上的应用。如果是不支持的值上会产生一个运行时异常。

如，下面的偏函数能返回整数列表的第二个元素：

  val second: List[Int] => Int = {
    case x :: y :: _ => y
  }

编译器会提示匹配不全：

  <console>:17: warning: match is not exhaustive!
  missing combination Nil

如果传递给它一个三元素列表，它的执行没有问题。但是一个空列表就不行了：

  scala> second(List(5,6,7))
  res24: Int = 6

  scala> second(List())
  scala.MatchError: List()
   at $anonfun$1.apply(<console>:17)
   at $anonfun$1.apply(<console>:17)

如果要检查一个偏函数是否有定义，一定要告诉编译器正在使用的函数是偏函数。类型Lint[Int] => Int包含了不管是否是偏函数的，从整数列表到整数的所有函数。仅包含整数列表到的偏函数的，应该写成`Partialfunction[List[Int],Int]。

下面是偏函数的定义例子：

  val second: PartialFunction[List[Int],Int] = {
    case x :: y :: _ => y
  }

偏函数有一个idDefineAt方法来测试函数对某个值是否有定义。以这个例子来说，对于至少两个元素的列表是有定义的：

  scala> second.isDefinedAt(List(5,6,7))
  res27: Boolean = true

  scala> second.isDefinedAt(List())
  res28: Boolean = false

Scala在编译器在把这样的表达式转为偏函数时会对模式进行两次翻译：一次是真实函数的实现；另一次是测试函数是否对参数有定义的实现。

例如上面的函数宣布量`{case x :: y: _ => y`会被翻译成：

  new PartialFunction[List[Int], Int] {
    def apply(xs: List[Int]) = xs match {
      case x :: y :: _ => y
    }
    def isDefinedAt(xs: List[Int]) = xs match {
      case x :: y :: _ => true
      case _ => false
    }
  }

这只有在声明类型为PartialFunction时才会发生。如果只是Function1或没有声明，函数字面量会编译为完整的函数。

偏函数可能会引起运行时的异常，所以在调用前用isDefineAt检查一下。

for表达式

典型例子，每个元素都是(country,city)：

  scala> for ((country, city) <- capitals)
       | println("The capital of "+ country +" is "+ city)
  The capital of France is Paris
  The capital of Japan is Tokyo

当然也有元素不匹配模式的情况，下面例子中不匹配的会被丢弃：

  scala> val results = List(Some("apple"), None,
       | Some("orange"))
  results: List[Option[java.lang.String]] = List(Some(apple),
      None, Some(orange))

  scala> for (Some(fruit) <- results) println(fruit)
  apple
  orange

大型的例子

目标是生成公式((a / (b * c) + 1 / n) / 3)显示形式为：

  a 1
----- + -
b * c n
---------
    3

先来看：

  BinOp("+",
        BinOp("*",
              BinOp("+", Var("x"), Var("y")),
              Var("z")),
        Number(1))

应该输出(x+y)*z+1，(x+y)是有括号的，但是最外层不要括号。所以要先解决优先级问题：

  Map(
    "|" -> 0, "||" -> 0,
    "&" -> 1, "&&" -> 1, ...
  )

当然还有改进的空间，更好的方法是只定义递减的优先级操作符。然后根据它来计算：

    // Contains operators in groups of increasing precedence
    private val opGroups =
      Array(
        Set("|", "||"),
        Set("&", "&&"),
        Set("^"),
        Set("==", "!="),
        Set("<", "<=", ">", ">="),
        Set("+", "-"),
        Set("*", "%")
      )

再定义一个操作符与优先级映射的变量precedence，映射的内容是通过处理上面定义的层级生成的：

    // A mapping from operators to their precedence
    private val precedence = {
      val assocs =
        for {
          i <- 0 until opGroups.length
          op <- opGroups(i)
        } yield op -> i
      Map() ++ assocs
    }

    private val unaryPrecedence = opGroups.length
    private val fractionPrecedence = -1

如：

BinOp("-", Var("a"), BinOp("-", Var("b"), Var("c")))

将被处理为a - (b - c)。如果当前操作符优先级小于外部操作符的优先级，那oper就要被放在括号里，不然按原样返回。

具体实现：

      case BinOp(op, left, right) =>
        val opPrec = precedence(op)
        val l = format(left, opPrec)
        val r = format(right, opPrec + 1)
        val oper = l beside elem(" "+ op +" ") beside r
        if (enclPrec <= opPrec) oper
        else elem("(") beside oper beside elem(")")

最后再给一个公开的方法，不用优先级参数就可以格式化公式：

    def format(e: Expr): Element = format(e, 0)

全部代码：

//compile this along with ../compo-inherit/LayoutElement.scala

  package org.stairwaybook.expr
  import layout.Element.elem
  
  sealed abstract class Expr
  case class Var(name: String) extends Expr
  case class Number(num: Double) extends Expr
  case class UnOp(operator: String, arg: Expr) extends Expr
  case class BinOp(operator: String,
      left: Expr, right: Expr) extends Expr
  
  class ExprFormatter {
  
    // Contains operators in groups of increasing precedence
    private val opGroups =
      Array(
        Set("|", "||"),
        Set("&", "&&"),
        Set("^"),
        Set("==", "!="),
        Set("<", "<=", ">", ">="),
        Set("+", "-"),
        Set("*", "%")
      )
  
    // A mapping from operators to their precedence
    private val precedence = {
      val assocs =
        for {
          i <- 0 until opGroups.length
          op <- opGroups(i)
        } yield op -> i
      Map() ++ assocs
    }
  
    private val unaryPrecedence = opGroups.length
    private val fractionPrecedence = -1
  
    // continued in Listing 15.21...

  import org.stairwaybook.layout.Element

  // ...continued from Listing 15.20
  
  private def format(e: Expr, enclPrec: Int): Element =
  
    e match {
  
      case Var(name) =>
        elem(name)
  
      case Number(num) =>
        def stripDot(s: String) =
          if (s endsWith ".0") s.substring(0, s.length - 2)
          else s
        elem(stripDot(num.toString))
  
      case UnOp(op, arg) =>
        elem(op) beside format(arg, unaryPrecedence)
  
      case BinOp("/", left, right) =>
        val top = format(left, fractionPrecedence)
        val bot = format(right, fractionPrecedence)
        val line = elem('-', top.width max bot.width, 1)
        val frac = top above line above bot
        if (enclPrec != fractionPrecedence) frac
        else elem(" ") beside frac beside elem(" ")
  
      case BinOp(op, left, right) =>
        val opPrec = precedence(op)
        val l = format(left, opPrec)
        val r = format(right, opPrec + 1)
        val oper = l beside elem(" "+ op +" ") beside r
        if (enclPrec <= opPrec) oper
        else elem("(") beside oper beside elem(")")
    }
  
    def format(e: Expr): Element = format(e, 0)
  }

具体调用的例子：

  import org.stairwaybook.expr._

  object Express extends Application {

    val f = new ExprFormatter

    val e1 = BinOp("*", BinOp("/", Number(1), Number(2)),
                        BinOp("+", Var("x"), Number(1)))
    val e2 = BinOp("+", BinOp("/", Var("x"), Number(2)),
                        BinOp("/", Number(1.5), Var("x")))
    val e3 = BinOp("/", e1, e2)

    def show(e: Expr) = println(f.format(e)+ "\n\n")

    for (val e <- Array(e1, e2, e3)) show(e)
}

  scala Express

下一个问题是格式化方法的实现。定义一个format方法，参数为表达式类型的e: Expr和操作符的优先级enclPrec: Int（如果没有这个操作符，那优先级就应该是0）。

注意format是私有方法，完成大部分工作。最后一个公开的同名方法format提供入口。内部还有一个stripDot方法来去掉如2.0的.0部分。

  private def format(e: Expr, enclPrec: Int): Element =

    e match {

      case Var(name) =>
        elem(name)

      case Number(num) =>
        def stripDot(s: String) =
          if (s endsWith ".0") s.substring(0, s.length - 2)
          else s
        elem(stripDot(num.toString))

      case UnOp(op, arg) =>
        elem(op) beside format(arg, unaryPrecedence)

      case BinOp("/", left, right) =>
        val top = format(left, fractionPrecedence)
        val bot = format(right, fractionPrecedence)
        val line = elem('-', top.width max bot.width, 1)
        val frac = top above line above bot
        if (enclPrec != fractionPrecedence) frac
        else elem(" ") beside frac beside elem(" ")

      case BinOp(op, left, right) =>
        val opPrec = precedence(op)
        val l = format(left, opPrec)
        val r = format(right, opPrec + 1)
        val oper = l beside elem(" "+ op +" ") beside r
        if (enclPrec <= opPrec) oper
        else elem("(") beside oper beside elem(")")
    }

    def format(e: Expr): Element = format(e, 0)
  }

分析具体的逻辑：

如果是变量，结果就是变量名。

  case Var(name) =>
    elem(name)

如果是数字，结果是格式化后的数字，如2.0格式化为2：

      case Number(num) =>
        def stripDot(s: String) =
          if (s endsWith ".0") s.substring(0, s.length - 2)
          else s
        elem(stripDot(num.toString))

对于一元操作符的处理结果为操作op和最高环境优先级格式化参数arg的结果组成。这样如果arg是除了分数以外的二元操作就不会出现在括号中。

      case UnOp(op, arg) =>
        elem(op) beside format(arg, unaryPrecedence)

如果是分数，则按上下位置放置。但仅仅上下的位置还不够。因为这样公不清主次：

a
-
b
-
c

有必要强化层次：

 a
 -
 b
---
 c

实现的代码这个样子的：

      case BinOp("/", left, right) =>
        val top = format(left, fractionPrecedence)
        val bot = format(right, fractionPrecedence)
        val line = elem('-', top.width max bot.width, 1)
        val frac = top above line above bot
        if (enclPrec != fractionPrecedence) frac
        else elem(" ") beside frac beside elem(" ")

然后了除法以外的其他二元操作符。在这里要注意一下优先级问题：

左操作数的优先级是操作符op的opPrec，而右操作数的优先级要再加1。这样保证了括号也同样反映正确的优先级。

使用列表

列表字面量

再简单回顾一下：

  val fruit = List("apples", "oranges", "pears")
  val nums = List(1, 2, 3, 4)
  val diag3 =
    List(
      List(1, 0, 0),
      List(0, 1, 0),
      List(0, 0, 1)
    )
  val empty = List()"brush: scala"

注意列表是不呆变的。

列表类型

列表是同质化的（homogeneous），所有的成员都有相同的类型，中括号描述成员类型List[T]。

val fruit: List[String] = List("apples", "oranges", "pears")
  val nums: List[Int] = List(1, 2, 3, 4)
  val diag3: List[List[Int]] =
    List(
      List(1, 0, 0),
      List(0, 1, 0),
      List(0, 0, 1)
    )
  val empty: List[Nothing] = List()

Scala里的列表类是协变的（covariant）。如果S是T的子类，那List[S]也是List[T]的子类。

由于Nothing是所有类的子类，所以List[Nothing]是所有List[T]类型的子类：

  // List() is also of type List[String]!
  val xs: List[String] = List()

构造列表

Nil代表空列表；::（发音为“cons”），elm::list把单个元素elm接在列表list的前面。

  val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
  val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
  val diag3 = (1 :: (0 :: (0 :: Nil))) ::
              (0 :: (1 :: (0 :: Nil))) ::
              (0 :: (0 :: (1 :: Nil))) :: Nil
  val empty = Nil

由于操作符::是右结合性，所以：

A :: (B :: C)

相当于：

A :: B :: C

所以前一个例子中很多括号都可以省略：

  val nums = 1 :: 2 :: 3 :: 4 :: Nil

列表的基本操作

三个基本操作：head、tail、isEmpty。

  val fruit = "apples" :: "oranges" :: "pears" :: Nil
  val nums = 1 :: 2 :: 3 :: 4 :: Nil
  val diag3 = (1 :: (0 :: (0 :: Nil))) ::
              (0 :: (1 :: (0 :: Nil))) ::
              (0 :: (0 :: (1 :: Nil))) :: Nil
  val empty = Nil
  
empty.isEmpty // true
fruit.isEmpty // flase
fruit.head // "apples"
fruit.tail.head // "organges"
diag3.head // List(1, 0, 0)

head与tail只能用在非空列表上，不然抛异常：

  scala> Nil.head
  java.util.NoSuchElementException: head of empty list

一个排序的例子，使用插入排序：对于非空列表x::xs可以先排序xs。然后再把x插入正确的地方：

  def isort(xs: List[Int]): List[Int] =
    if (xs.isEmpty) Nil
    else insert(xs.head, isort(xs.tail))

  def insert(x: Int, xs: List[Int]): List[Int] =
    if (xs.isEmpty || x <= xs.head) x :: xs
    else xs.head :: insert(x, xs.tail)

列表模式

简单的模式匹配，在确定长度的情况下取出列表里的元素：

  scala> val List(a, b, c) = fruit
  a: String = apples
  b: String = oranges
  c: String = pears

不确定具体长度但知道至少有几个，或是只要取前几个：

  scala> val a :: b :: rest = fruit
  a: String = apples
  b: String = oranges
  rest: List[String] = List(pears)

要注意这里的List(...)和::并不是之前定义的模式匹配。

实际上List(...)是将来会在抽取器章节介绍的抽取器模式。

“cos”模式x::xs是中缀操作符模式的特例，一般中缀表达式p op q视为p.op(q)。但是如果作为模式，其实是被当作构造器模式的op(p,q)形式。

对应这个构造器模式的类是scala.::，它可以创建非空列表的类。还有一个List类的方法::用来实例化scala.::的对象。在将来的“实现列表”章节中会有进一步的描述。

再次用模式匹配的方式来实现前面已经实现过的插入排序法：

  def isort(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case x :: xs1 => insert(x, isort(xs1))
  }

  def insert(x: Int, xs: List[Int]): List[Int] = xs match {
    case List() => List(x)
    case y :: ys => if (x <= y) x :: xs
                    else y :: insert(x, ys)
  }

List类的一阶方法

这里介绍的方法是List类的方法，所以是在独立的对象上被调用。

连接列表

连接两个列表的操作符是:::，例如：

  scala> List(1, 2) ::: List(3, 4, 5)
  res0: List[Int] = List(1, 2, 3, 4, 5)

  scala> List() ::: List(1, 2, 3)
  res1: List[Int] = List(1, 2, 3)

  scala> List(1, 2, 3) ::: List(4)
  res2: List[Int] = List(1, 2, 3, 4)

它也是右结合的：

xs ::: ys ::: zs

相当于：

xs ::: (ys ::: zs)

分治原则

手动实现一个连接列表的append方法。先用模式匹配把输入的列表拆分为更加简单的样本：

  def append[T](xs: List[T], ys: List[T]): List[T] =
    xs match {
      case List() => ys
      case x :: xs1 => x :: append(xs1, ys)
    }

以上代码的让ys操持完整而xs被一步步拆分并放到ys前面，所以把注意集中到xs的模式匹配上。

再通过递归调用层层套用剩下的元素，通过添加单个元素的方法::连接列表。

列表长度

  scala> List(1, 2, 3).length
  res3: Int = 3

length方法要遍历整个列表来取得长度，所以判断是否为空一般用isEmpty而不用length。

取头和尾

head取头，tail取的是除了第一个元素外剩下列表。这两个方法的运行时间是常量。

last取尾，init取最后一个以外的列表。这两个方法会遍历整个列表。

  scala> val abcde = List('a', 'b', 'c', 'd', 'e')
  abcde: List[Char] = List(a, b, c, d, e)

  scala> abcde.last
  res4: Char = e

  scala> abcde.init
  res5: List[Char] = List(a, b, c, d)

对于空列表会抛异常

  scala> List().init
  java.lang.UnsupportedOperationException: Nil.init
   at scala.List.init(List.scala:544)
   at ...

  scala> List().last
  java.util.NoSuchElementException: Nil.last
   at scala.List.last(List.scala:563)
   at ...

反转列表

reverse是创建了一个新列表：

  scala> abcde.reverse
  res6: List[Char] = List(e, d, c, b, a)

  scala> abcde
  res7: List[Char] = List(a, b, c, d, e)

一些简单的规律：

xs.reverse.reverse equals xs

xs.reverse.init equals xs.tail.reverse
xs.reverse.tail equals xs.init.reverse
xs.reverse.head equals xs.last
xs.reverse.last equals xs.head

通过连接操作:::来实现反转，当然这样的效率低得很：

  def rev[T](xs: List[T]): List[T] = xs match {
    case List() => xs
    case x :: xs1 => rev(xs1) ::: List(x)
  }

前缀与后缀

take和drop取得或舍去列表指定长度个元素，长度超过时不会抛异常而是返回整个列表或空列表。

  scala> abcde take 2
  res8: List[Char] = List(a, b)

  scala> abcde drop 2
  res9: List[Char] = List(c, d, e)

splitAt在指定位置拆分列表。

xs splitAt n

// equals

(xs take n, xs drop n)

例：

  scala> abcde splitAt 2
  res10: (List[Char], List[Char]) = (List(a, b),List(c, d, e))

取得指定元素

通过索引取得指定元素：

  scala> abcde apply 2 // rare in Scala
  res11: Char = c

  scala> abcde(2) // rare in Scala
  res12: Char = c

includes方法取得所有的索引列表：

  scala> abcde.indices
  res13: List[Int] = List(0, 1, 2, 3, 4)

zip

把两个列表组成对偶（二元组），如果长度不一样会丢弃长出来的：

  scala> abcde.indices zip abcde
  res14: List[(Int, Char)] = List((0,a), (1,b), (2,c), (3,d),
  (4,e))

  scala> val zipped = abcde zip List(1, 2, 3)
  zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))

如果是为了把元素和索引zip在一起，用zipWithIndex方法更有效：

  scala> abcde.zipWithIndex
  res15: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3), (e,4))

toString 和 mkString

toString简单字符串化列表

  scala> abcde.toString
  res16: String = List(a, b, c, d, e)

mkString通过三个参数来指定前后包列表的字符和分隔列表元素的字符：

xs mkString (pre, sep, post)

还有两个变体：

xs mkString sep
// equals
xs mkString ("", sep, "")

sx mkString
// equals
xs mkString ""

例子：

  scala> abcde mkString ("[", ",", "]")
  res17: String = [a,b,c,d,e]

  scala> abcde mkString ""
  res18: String = abcde

  scala> abcde.mkString
  res19: String = abcde

  scala> abcde mkString ("List(", ", ", ")")
  res20: String = List(a, b, c, d, e)

还有一个addSting变体让结果添加到StringBuilder中，而不是作为结果返回：

  scala> val buf = new StringBuilder
  buf: StringBuilder =

  scala> abcde addString (buf, "(", ";", ")")
  res21: StringBuilder = (a;b;c;d;e)

列表的转换

List类的toArray和Array类的toList，列表和数组转来转去。

  scala> val arr = abcde.toArray
  arr: Array[Char] = Array(a, b, c, d, e)

  scala> arr.toString
  res22: String = Array(a, b, c, d, e)

  scala> arr.toList
  res23: List[Char] = List(a, b, c, d, e)

copyToArray把列表复制到数组中一会连续的空间内：

  xs copyToArray (arr, start)

start为开始的位置。当然还要保证数组中有足够的空间。例子：

  scala> val arr2 = new Array[Int](10)
  arr2: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

  scala> List(1, 2, 3) copyToArray (arr2, 3)

  scala> arr2.toString
  res25: String = Array(0, 0, 0, 1, 2, 3, 0, 0, 0, 0)

elements提供了通过枚举器访问列表元素的方法：

  scala> val it = abcde.elements
  it: Iterator[Char] = non-empty iterator

  scala> it.next
  res26: Char = a

  scala> it.next
  res27: Char = b

例：归并排序

归并排序：如果列表长度为0或是1，就算是已经排序好的，直接返回。长度大于1的列表可以拆成两个长度接近的，每个再递归调用完成排序，再把返回的两个排序好的列表合并。

函数的实现用到了柯里化，接收元素之间的比较大小的函数和要排序的列表：

  def msort[T](less: (T, T) => Boolean)
      (xs: List[T]): List[T] = {

    def merge(xs: List[T], ys: List[T]): List[T] =
      (xs, ys) match {
        case (Nil, _) => ys
        case (_, Nil) => xs
        case (x :: xs1, y :: ys1) =>
          if (less(x, y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }

    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(msort(less)(ys), msort(less)(zs))
    }
  }

使用的方法：

  scala> msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
  res28: List[Int] = List(1, 3, 5, 7)

作为一个柯里化的例子，可以用下划线代表末指定的参数列表：

  scala> val intSort = msort((x: Int, y: Int) => x < y) _
  intSort: (List[Int]) => List[Int] = <function>

如果要改成倒序排序的话，只要换个比较函数：

  scala> val reverseIntSort = msort((x: Int, y: Int) => x > y) _
  reverseIntSort: (List[Int]) => List[Int] = <function>

上面的intSort和reverseIntSort都已经绑定了排序的方法，只要传入待排序的列表：

  scala> val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)
  mixedInts: List[Int] = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)

  scala> intSort(mixedInts)
  res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

  scala> reverseIntSort(mixedInts)
  res1: List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

List类的高阶函数

这里介绍的方法是List类的方法，所以是在独立的对象上被调用。

Scala中以操作符形式出现的高阶函数更加简洁地处理Java中用循环来处理的问题。

列表间映射

xs map fun把列表中每个元素用方法处理过后生成新列表。xs代表List[T]；fun代表T => U的函数。

  scala> List(1, 2, 3) map (_ + 1)
  res29: List[Int] = List(2, 3, 4)

  scala> val words = List("the", "quick", "brown", "fox")
  words: List[java.lang.String] = List(the, quick, brown, fox)
 
  scala> words map (_.length)
  res30: List[Int] = List(3, 5, 5, 3)

  scala> words map (_.toList.reverse.mkString)
  res31: List[String] = List(eht, kciuq, nworb, xof)

flatMap和map类似，但它把所有元素连成一个列表：

  scala> words map (_.toList)
  res32: List[List[Char]] = List(List(t, h, e), List(q, u, i,
      c, k), List(b, r, o, w, n), List(f, o, x))

  scala> words flatMap (_.toList)
  res33: List[Char] = List(t, h, e, q, u, i, c, k, b, r, o, w,
      n, f, o, x)

flatMap和map合作建立出所有1 <= j < i < 5的(i, j)对偶：

  scala> List.range(1, 5) flatMap (
       | i => List.range(1, i) map (j => (i, j))
       | )
  res34: List[(Int, Int)] = List((2,1), (3,1), (3,2), (4,1),
      (4,2), (4,3))

上面的代码List.range(1, 5)产生从1到5的整数列表。对于其中的每项i再产生1到i的列表。map产生(i, j)元组列表，这里的j<i。flatMpa对每个1到5之间的i产列表，并连接所有列表得到结果。

等同于以下循环结构：

  for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)

foreach没有返回结果（或返回Unit）。如下对sum变量累加，但是没有返回值：

  scala> var sum = 0
  sum: Int = 0

  scala> List(1, 2, 3, 4, 5) foreach (sum += _)

  scala> sum
  res36: Int = 15

过滤

xs filter p，xs代表List[T]，p代表T => Boolean形式的函数。返回符合的结果列表：

  scala> List(1, 2, 3, 4, 5) filter (_ % 2 == 0)
  res37: List[Int] = List(2, 4)

  scala> words filter (_.length == 3)
  res38: List[java.lang.String] = List(the, fox)

partition方法返回的是所有符合的元素和所有不符合的元素两个列表对。

xs partition p
// equals
( xs filter p , xs filter (!p(_)) )

例：

  scala> List(1, 2, 3, 4, 5) partition (_ % 2 == 0)
  res39: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

find方法只返回第一个符合的元素，一个都不符合返回None：

  scala> List(1, 2, 3, 4, 5) find (_ % 2 == 0)
  res40: Option[Int] = Some(2)

  scala> List(1, 2, 3, 4, 5) find (_ <= 0)
  res41: Option[Int] = None

takeWhile不断累积符合的结果直到遇到不符合的；dropWhile不断丢弃不符的元素直到遇到符合的。

  scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0)
  res42: List[Int] = List(1, 2, 3)

  scala> words dropWhile (_ startsWith "t")
  res43: List[java.lang.String] = List(quick, brown, fox)

span方法组合了takeWhile和dropWhile返回一对列表，就像是splitAt组合了take和drop一样。

xs span p
// equals
(xs takeWhile p , xs dropWhile p)

和split一样，span避免对列表的二次访问：

  scala> List(1, 2, 3, -4, 5) span (_ > 0)
  res44: (List[Int], List[Int]) = (List(1, 2, 3),List(-4, 5))

列表论断

xs forall p全部符合，xs exits p存在符合的元素。

  scala> def hasZeroRow(m: List[List[Int]]) =
       | m exists (row => row forall (_ == 0))
  hasZeroRow: (List[List[Int]])Boolean

  scala> hasZeroRow(diag3)
  res45: Boolean = false

折叠列表

左折叠操作符/:，格式为：(z /: xs) (op)。其中z为开始值，xs为列表，op为二元操作。

(z /: List(a, b, c)) (op)
// equals
op(op(op(z,a), b), c)

用树表示：

      op
     / \
    op c
   / \
  op b
 / \
z a

举例：

  scala> def sum(xs: List[Int]): Int = (0 /: xs) (_ + _)
  sum: (List[Int])Int
  
  scala> sum(List(1, 2, 3)) // equals 0 + 1 + 2 + 3
  res1: Int = 6

  scala> def product(xs: List[Int]): Int = (1 /: xs) (_ * _)
  product: (List[Int])Int
  
  scala> product(List(1, 2, 3)) // equals 1 * 1 * 2 * 3
  res2: Int = 6

用空格连接所有单词：

  scala> ("" /: words) (_ +" "+ _)
  res46: java.lang.String = the quick brown fox

头上多了一个空格，这样去掉它：

  scala> (words.head /: words.tail) (_ +" "+ _)
  res47: java.lang.String = the quick brown fox

相对的还有右倾斜操作树:\：

(List(a, b, c) :\ z) (op)
// equals
op(a, op(b, op(c, z)))

对于组合操作来说，左右折叠是等价的，但效率上有差异。下面两个把元素连接在一起的方法：

  def flattenLeft[T](xss: List[List[T]]) =
      (List[T]() /: xss) (_ ::: _)

  def flattenRight[T](xss: List[List[T]]) =
      (xss :\ List[T]()) (_ ::: _)

采用右折叠的flattenLeft需要复制第一个元素列表xss.head一共xss.length-1次，所以效率差一些。

注意这里两个版本的实现都要对作为折叠开始值的空列表做类型标注。这是由Scala类型推断的局限性无法推断出正确的类型。不标注的话会有以下错误：

  scala> def flattenRight[T](xss: List[List[T]]) =
       | (xss :\ List()) (_ ::: _)
  <console>:15: error: type mismatch;
   found : List[T]
   required: List[Nothing]
             (xss :\ List()) (_ ::: _)
                                ^

在以后的“实现列表”章节中讨论类型推断失败的原因。

如果觉得/:和:\看起来不清楚，可以用List提供的foldLeft和foldRight方法代替。

例子：使用折叠实现列表反转

def reverseLeft[T](xs: List[T]) = (startvalue /: xs) (operation)

为了写出正确的startvalue和operation，从可以出现的最小的列表List()开始推导：

List()
// equals
reverseLeft(List())
// equals
(startvalue /: List()) (operation)
// equals
startvalue

所以startvalue一定是List()。再代入推导operation：

List(x)
// equals
reverseLeft(List(x))
// equals
(startvalue /: List(x)) (operation)
// equals
operation(List(), x)
// equals
x :: List()

所以具体实现为：

  def reverseLeft[T](xs: List[T]) =
    (List[T]() /: xs) {(ys, y) => y :: ys}

排序

xs sort before，xs是列表，before是比较元素x是否在y前面的方法。

  scala> List(1, -3, 4, 2, 6) sort (_ < _)
  res48: List[Int] = List(-3, 1, 2, 4, 6)

  scala> words sort (_.length > _.length)
  res49: List[java.lang.String] = List(quick, brown, fox, the)

注意前面还提到过一个msort方法，那个是定义在列表外的。sort是List类的方法。

List对象的方法

下面介绍的方法是伴生对象scala.List的，创建列表的工厂方法和特定类型列表的操作。

通过元素创建列表

apply方法：

List(1, 2, 3)
// is actually
List.apply(1, 2, 3)

按数值范围创建列表

range参数可以是：开始、结束、步长：

  scala> List.range(1, 5)
  res51: List[Int] = List(1, 2, 3, 4)

  scala> List.range(1, 9, 2)
  res52: List[Int] = List(1, 3, 5, 7)

  scala> List.range(9, 1, -3)
  res53: List[Int] = List(9, 6, 3)

创建重复元素的列表

make方法：

  scala> List.make(5, 'a')
  res54: List[Char] = List(a, a, a, a, a)

  scala> List.make(3, "hello")
  res55: List[java.lang.String] = List(hello, hello, hello)

解除Zip列表

unzip把二元组列表分成两个列表：

  scala> val zipped = "abcde".toList zip List(1, 2, 3)
  zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))

  scala> List.unzip(zipped)
  res56: (List[Char], List[Int]) = (List(a, b, c),
      List(1, 2, 3))

Scala类型系统要求类方法能处理所有类型，而unzip只处理二元组列表。所以unzip不能像zip方法一样放在类里而只能放在伴生对象里。

连接列表

flatten方法只能处理包含子列表的列表，所以不能放在List类里。只能放在伴生对象中。

  scala> val xss =
       | List(List('a', 'b'), List('c'), List('d', 'e'))
  xss: List[List[Char]] = List(List(a, b), List(c), List(d, e))

  scala> List.flatten(xss)
  res57: List[Char] = List(a, b, c, d, e)

concat方法把多个列表作为可变长参数形式接收：

  scala> List.concat(List('a', 'b'), List('c'))
  res58: List[Char] = List(a, b, c)

  scala> List.concat(List(), List('b'), List('c'))
  res59: List[Char] = List(b, c)
  
  scala> List.concat()
  res60: List[Nothing] = List()

映射与测试配对

map2方法接收两个列表，分别作为方法的两个参数：

  scala> List.map2(List(10, 20), List(3, 4, 5)) (_ * _)
  res61: List[Int] = List(30, 80)

exist2也是接收两个列表，分别作为方法的两个参数：

  scala> List.forall2(List("abc", "de"),
       | List(3, 2)) (_.length == _)
  res62: Boolean = true

  scala> List.exists2(List("abc", "de"),
       | List(3, 2)) (_.length != _)
  res63: Boolean = false

了解Scala的类型推断方法

下面是用占位符_推导出的参数类型：

  scala> abcde sort (_ > _)
  res65: List[Char] = List(e, d, c, b, a)

但是msort方法却不能用占位符：

  scala> msort((x: Char, y: Char) => x > y)(abcde)
  res64: List[Char] = List(e, d, c, b, a)
  
  scala> msort(_ > _)(abcde)
  <console>:12: error: missing parameter type for expanded
  function ((x$1, x$2) => x$1.$greater(x$2))
         msort(_ > _)(abcde)
               ^

因为Scala的类型推导器是基于流的。对于｀func(args)｀这样的方法，先看func是否有已经的类型。如果有的话这个类型就被用来做参数预期类型的推断。

例如对于List[Char]类型的列表abcd，abcd的成员都是Char所以abcd.sort(_ > _)的两个参数也只会是Char。所以：

(_ > _)
// trans to
((x: Char, y: Char) => x > y)

而对于msort(_ > _)(abcde)这个类型是柯里化的、多态的方法类型，参数类型是(T, T) => Boolean，返回类型是从List[T]到List[T]的函数。无法推断第一个参数的类型。所以类型推断器要参数的类型信息。

想要用占位符的话，只能把参数类型传给msort：

  scala> msort[Char](_ > _)(abcde)
  res66: List[Char] = List(e, d, c, b, a)

还有一个方法是交换参数顺序，这样可以用第一个列表的类型来推断比较方法的类型了：

  // same implementation as msort,
  // but with arguments swapped
  def msortSwapped[T](xs: List[T])(less:
      (T, T) => Boolean): List[T] = {
  }
  
  scala> msortSwapped(abcde)(_ > _)
  res67: List[Char] = List(e, d, c, b, a)

需要推断多态方法类型时只会参考第一个参数列表，所以在柯里化方法有两个参数列表时第二个参数不会用来决定方法类型参数。

所以这种方案隐含以下的库方法设计原则：

如果参数包括若干个非函数参数与一个函数参数的组合时，要把函数参数独自放在柯里化参数列表的最后面。这样方法的正确实例类型就可以通过非函数参数推断出来，推断出来的类型还可以转面用来完成函数参数的类型检查。调用函数的时候也可以写出更加简洁的字面量。

再来看更加复杂的折叠操作：

  (xss :\ List[T]()) (_ ::: _)

上面的表达式提供了明确的类型参数的原因是这个右折叠操作的类型取决于两个变量：

  (xs :\ z) (op)

这里把列表xs的类型记为A，如：xs: List[A]；而开始值z有可能是类型B。对应的操作op必须以A和B的值为参数并返回类型B的结果，即：op: (A, B) => B。

从上面的描述可以看出：这里的op方法要知道A与B两个类型。A一定与List有关但是B不一定与List有关，所以推不出来。所以下面的表达式是编译不过的：

  (xss :\ List()) (_ ::: _) // this won't compile

上面表达式中z的类型为List[Nothing]，据此推断器把B的类型定为Nothing：

  (List[T], List[Nothing]) => List[Nothing]

这就意味着输出与输出都是空列表。

就是因为这个问题，所以在柯里化的方法中，方法类型只取决于第一段参数。但是如果不这样做的话，推断器还是没有办法取得op的类型。所以只能程序员明确指定类型。

所以Scala采用的局部的、基于流的类型推断方法还是比较有局限性的；不如ML或是Haskell采用的更加全局化的Hindley-Milner类型推断方式。但是对于面向对象的分支类型处理比Hindley-Mlner更加优雅。由于这些局限性在比较极端的情况下才遇到，所以就在极端情况下明确标类型吧。

另外在遇到多态类型错误时，添加上你认为应该是正确的类型标注也是一种排错方式。

集体类型

概览

scala包中主要特质Iterable，三个子特质：

Seq：有序集合。
Set：对于==方法不可重复的元素集合。
Map：键值映射。

特技Iterable有个抽象方法elements：

  def elements: Iterator[A]

注意返回类型是一个迭代器iterator，不是iterate别看错了！

迭代器用来从头到尾遍历一遍集合。如果要再遍历一遍的话，只能用elements方法再生成一个新的迭代器。。

迭代器Iterator继承自AnyRef。Iterator提供的具体方法都实现了next和hasNext抽象方法实现：

  def hasNext: Boolean
  def next: A

序列

列表

列表不能通过索引直接访问元素，只能遍历；但可以支持在头上快速添加和删除。这点像是链式表。

在头上快速添加和删除元素很好地适合模式匹配。

但是因为只能对列表头快速访问，而尾部不行。所以如果要操作尾部的话可以先建一个反序的列表，再reverse把顺序反过来。

列表缓存

还有一人方式是使用scala.collection.mutable.ListBuffer。

+=在尾部添加元素；+:加在头上；完成之后用toList生成List：

  scala> import scala.collection.mutable.ListBuffer
  import scala.collection.mutable.ListBuffer

  scala> val buf = new ListBuffer[Int]
  buf: scala.collection.mutable.ListBuffer[Int] = ListBuffer()

  scala> buf += 1

  scala> buf += 2

  scala> buf
  res11: scala.collection.mutable.ListBuffer[Int]
    = ListBuffer(1, 2)

  scala> 3 +: buf
  res12: scala.collection.mutable.Buffer[Int]
    = ListBuffer(3, 1, 2)

  scala> buf.toList
  res13: List[Int] = List(3, 1, 2)

List结合前置添加元素和递归算法增长列表时，如果用的递归算法不是尾递归，就有栈溢出的风险；而ListBuffer可以结合循环替代递归。

数组

数组适合按索引快速访问元素。

按长度产数组：

  scala> val fiveInts = new Array[Int](5)
  fiveInts: Array[Int] = Array(0, 0, 0, 0, 0)

按元素产数组：

  scala> val fiveToOne = Array(5, 4, 3, 2, 1)
  fiveToOne: Array[Int] = Array(5, 4, 3, 2, 1)

通过()指定索引：

  scala> fiveInts(0) = fiveToOne(4)

  scala> fiveInts
  res1: Array[Int] = Array(1, 0, 0, 0, 0)

数组缓存

ArrayBuffer可以在头尾添加元素：

  scala> import scala.collection.mutable.ArrayBuffer
  import scala.collection.mutable.ArrayBuffer

  scala> val buf = new ArrayBuffer[Int]()
  buf: scala.collection.mutable.ArrayBuffer[Int] =
    ArrayBuffer()

  scala> buf += 12
  scala> buf += 15

  scala> buf
  res16: scala.collection.mutable.ArrayBuffer[Int] =
    ArrayBuffer(12, 15)

  scala> buf.length
  res17: Int = 2

  scala> buf(0)
  res18: Int = 12

队列

不可变的队列：

  scala> import scala.collection.immutable.Queue
  import scala.collection.immutable.Queue

  scala> val empty = new Queue[Int]
  empty: scala.collection.immutable.Queue[Int] = Queue()

// add one element
  scala> val has1 = empty.enqueue(1)
  has1: scala.collection.immutable.Queue[Int] = Queue(1)

// use collection to add many elements
  scala> val has123 = has1.enqueue(List(2, 3))
  has123: scala.collection.immutable.Queue[Int] = Queue(1,2,3)

  scala> val (element, has23) = has123.dequeue
  element: Int = 1
  has23: scala.collection.immutable.Queue[Int] = Queue(2,3)

注意上面取后一个出队操作dequeue返回的是一个二元组，包括出来的元素和剩下的队列。

可变的队列也差不多，就是用+=和++=添加元素，dequeue方法只返回一个出除的元素。

  scala> import scala.collection.mutable.Queue
  import scala.collection.mutable.Queue

  scala> val queue = new Queue[String]
  queue: scala.collection.mutable.Queue[String] = Queue()

  scala> queue += "a"

  scala> queue ++= List("b", "c")

  scala> queue
  res21: scala.collection.mutable.Queue[String] = Queue(a, b, c)

  scala> queue.dequeue
  res22: String = a

  scala> queue
  res23: scala.collection.mutable.Queue[String] = Queue(b, c)

栈

可变的栈：

  scala> import scala.collection.mutable.Stack
  import scala.collection.mutable.Stack

  scala> val stack = new Stack[Int]
  stack: scala.collection.mutable.Stack[Int] = Stack()

  scala> stack.push(1)

  scala> stack
  res1: scala.collection.mutable.Stack[Int] = Stack(1)

  scala> stack.push(2)

  scala> stack
  res3: scala.collection.mutable.Stack[Int] = Stack(1, 2)

  scala> stack.top
  res8: Int = 2

  scala> stack
  res9: scala.collection.mutable.Stack[Int] = Stack(1, 2)

  scala> stack.pop
  res10: Int = 2

  scala> stack
  res11: scala.collection.mutable.Stack[Int] = Stack(1)

不可变的栈略。

字符串

因为Predef包含了从String到RichString的隐式转换，所以可以把任务字符串当作Seq[Char]。

  scala> def hasUpperCase(s: String) = s.exists(_.isUpperCase)
  hasUpperCase: (String)Boolean

  scala> hasUpperCase("Robert Frost")
  res14: Boolean = true

  scala> hasUpperCase("e e cummings")
  res15: Boolean = false

exists方法不在String里，所以隐匿转换为包含exists方法的RichString类。

Set与Map

因为Predef对象通过type关键字指定默认引用了Set与Map的不可变版本：

  object Predef {
    type Set[T] = scala.collection.immutable.Set[T]
    type Map[K, V] = scala.collection.immutable.Map[K, V]
    val Set = scala.collection.immutable.Set
    val Map = scala.collection.immutable.Map
    // ...
  }

所以可变版的要手动声明：

  scala> import scala.collection.mutable
  import scala.collection.mutable

  scala> val mutaSet = mutable.Set(1, 2, 3)
  mutaSet: scala.collection.mutable.Set[Int] = Set(3, 1, 2)

使用Set

Set的关键在于用对象的==检查唯一性。

例子：统计出现的单词

用正则 [ !,.]+ 分隔成单词:

  scala> val text = "See Spot run. Run, Spot. Run!"
  text: java.lang.String = See Spot run. Run, Spot. Run!

  scala> val wordsArray = text.split("[ !,.]+")
  wordsArray: Array[java.lang.String] =
     Array(See, Spot, run, Run, Spot, Run)

建立Set并存入：

  scala> val words = mutable.Set.empty[String]
  words: scala.collection.mutable.Set[String] = Set()

  scala> for (word <- wordsArray)
       | words += word.toLowerCase

  scala> words
  res25: scala.collection.mutable.Set[String] =
    Set(spot, run, see)

常用方法：

val nums = Set(1, 2, 3)	（返回）
nums + 5	（返回）
nums - 3	（返回）
nums ++ List(5, 6)	（返回）
nums -- List(1, 2)	（返回）
nums ** Set(1, 3, 5, 7)	交集（返回Set(3)）
nums.size	（返回）
nums.contains(3)	（返回）
import scala.collection.mutable	（返回）
val words = mutable.Set.empty[String]	创建空的可变集
words += "the"	（返回）
words -= "the"	（返回）
words ++= List("do", "re", "mi")	（返回）
words --= List("do", "re")	（返回）
words.clear	（返回）

Map

使用可变的Map：

  scala> val map = mutable.Map.empty[String, Int]
  map: scala.collection.mutable.Map[String,Int] = Map()

  scala> val map = mutable.Map.empty[String, Int]
  map: scala.collection.mutable.Map[String,Int] = Map()

  scala> map("hello") = 1

  scala> map("there") = 2

  scala> map
  res28: scala.collection.mutable.Map[String,Int] =
    Map(hello -> 1, there -> 2)

  scala> map("hello")
  res29: Int = 1

统计单词出现次数的例子：

  scala> def countWords(text: String) = {
       | val counts = mutable.Map.empty[String, Int]
       | for (rawWord <- text.split("[ ,!.]+")) {
       | val word = rawWord.toLowerCase
       | val oldCount =
       | if (counts.contains(word)) counts(word)
       | else 0
       | counts += (word -> (oldCount + 1))
       | }
       | counts
       | }
  countWords: (String)scala.collection.mutable.Map[String,Int]
  

  scala> countWords("See Spot run! Run, Spot. Run!")
  res30: scala.collection.mutable.Map[String,Int] =
    Map(see -> 1, run -> 3, spot -> 2)

常用方法：

val nums = Map("i"->1, "ii"->2)	返回
nums + ("vi"->6)	返回
nums - "ii"	返回
nums ++ List("iii"->3, "v"->5)	返回
nums -- List("i", "ii")	返回
nums.size	返回
nums.contains("ii")	返回
nums("ii")	返回
nums.keys	返回迭代器
nums.keySet	返回
nums.values	返回
nums.isEmpty	返回
import scala.collection.mutable	返回
val words = mutalbe.Map.empty[String, Int]	返回
words += ("one"->1)	返回
words -= "one"	返回
words ++= List("one"->1, "two"->2, "three"->3))	返回
words --= List("one", "two")	返回

默认的Set和Map

不可变的类会对数量优化一些工厂方法返回的默认的实现。

不可变的scala.collection.immutable.Set()工厂方法返回：

元素的数量	实现
0	scala.collection.immutable.EmptySet
1	scala.collection.immutable.Set1
2	scala.collection.immutable.Set2
3	scala.collection.immutable.Set3
4	scala.collection.immutable.Set4
>=5	scala.collection.immutable.HashSet

不可变的scala.collection.immutable.Map()工厂方法返回：

元素的数量	实现
0	scala.collection.immutable.EmptyMap
1	scala.collection.immutable.Map1
2	scala.collection.immutable.Map2
3	scala.collection.immutable.Map3
4	scala.collection.immutable.Map4
>=5	scala.collection.immutable.HashMap

有序的集体和映射

TreeSet和TreeMap分别实现了SortedSet和SortedMap特质。都用红黑树保存元素，顺序由Ordered特质决定。这些类只有不可变的版本：

  scala> import scala.collection.immutable.TreeSet
  import scala.collection.immutable.TreeSet

  scala> val ts = TreeSet(9, 3, 1, 8, 0, 2, 7, 4, 6, 5)
  ts: scala.collection.immutable.SortedSet[Int] =
    Set(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

  scala> val cs = TreeSet('f', 'u', 'n')
  cs: scala.collection.immutable.SortedSet[Char] = Set(f, n, u)


  scala> import scala.collection.immutable.TreeMap
  import scala.collection.immutable.TreeMap

  scala> var tm = TreeMap(3 -> 'x', 1 -> 'x', 4 -> 'x')
  tm: scala.collection.immutable.SortedMap[Int,Char] =
    Map(1 -> x, 3 -> x, 4 -> x)

  scala> tm += (2 -> 'x')

  scala> tm
  res38: scala.collection.immutable.SortedMap[Int,Char] =
    Map(1 -> x, 2 -> x, 3 -> x, 4 -> x)

同步的Set和Map

把SynchronizedMap特质混入到实现中。下面单例对象中的makeMap方法：

  import scala.collection.mutable.{Map,
      SynchronizedMap, HashMap}

  object MapMaker {

    def makeMap: Map[String, String] = {

        new HashMap[String, String] with
            SynchronizedMap[String, String] {

          override def default(key: String) =
            "Why do you want to know?"
        }
    }
  }

上面的方法会返回一个HashMap并且重写了default方法在没有对应的key时有默认的返回。

单线程访问的情况如下：

  scala> val capital = MapMaker.makeMap
  capital: scala.collection.mutable.Map[String,String] = Map()

  scala> capital ++ List("US" -> "Washington",
       | "Paris" -> "France", "Japan" -> "Tokyo")
  res0: scala.collection.mutable.Map[String,String] =
    Map(Paris -> France, US -> Washington, Japan -> Tokyo)

  scala> capital("Japan")
  res1: String = Tokyo

  scala> capital("New Zealand")
  res2: String = Why do you want to know?

  scala> capital += ("New Zealand" -> "Wellington")

  scala> capital("New Zealand")
  res3: String = Wellington

类似的同步的Set：

  val synchroSet =
    new mutable.HashSet[Int] with
        mutable.SynchronizedSet[Int]

可变与不可变类型的比较

为了方便在可变与不可变类型之间地转换，Scala提供了一些语法糖。

如，不可变类型不支持+=操作：

  scala> val people = Set("Nancy", "Jane")
  people: scala.collection.immutable.Set[java.lang.String] =
    Set(Nancy, Jane)

  scala> people += "Bob"
  <console>:6: error: reassignment to val
         people += "Bob"
                ^

但是如果把变量从val改成var，Scala还是可以返回一个添加后的新对象来模拟：

  scala> var people = Set("Nancy", "Jane")
  people: scala.collection.immutable.Set[java.lang.String] =
    Set(Nancy, Jane)
 
  scala> people += "Bob"

  scala> people
  res42: scala.collection.immutable.Set[java.lang.String] =
    Set(Nancy, Jane, Bob)

类似的还有其他的操作：

  scala> people -= "Jane"

  scala> people ++= List("Tom", "Harry")

  scala> people
  res45: scala.collection.immutable.Set[java.lang.String] =
    Set(Nancy, Bob, Tom, Harry)

这样的语法糖方便在可变与不可变类型之间转换：

  var capital = Map("US" -> "Washington", "France" -> "Paris")
  capital += ("Japan" -> "Tokyo")
  println(capital("France"))

  import scala.collection.mutable.Map // only change needed!
  var capital = Map("US" -> "Washington", "France" -> "Paris")
  capital += ("Japan" -> "Tokyo")
  println(capital("France"))

这样的语法糖还可以用在其他类型上。如浮点：

  scala> var roughlyPi = 3.0
  roughlyPi: Double = 3.0

  scala> roughlyPi += 0.1

  scala> roughlyPi += 0.04

  scala> roughlyPi
  res48: Double = 3.14

基本上+=、-=、*=这类以=结尾的操作符都可以。

初始化集合

最典型的是用伴生对象的工厂方法：

  scala> List(1, 2, 3)
  res0: List[Int] = List(1, 2, 3)

  scala> Set('a', 'b', 'c')
  res1: scala.collection.immutable.Set[Char] = Set(a, b, c)

  scala> import scala.collection.mutable
  import scala.collection.mutable

  scala> mutable.Map("hi" -> 2, "there" -> 5)
  res2: scala.collection.mutable.Map[java.lang.String,Int] =
    Map(hi -> 2, there -> 5)

  scala> Array(1.0, 2.0, 3.0)
  res3: Array[Double] = Array(1.0, 2.0, 3.0)

会根据工厂方法推断类型：

  scala> import scala.collection.mutable
  import scala.collection.mutable

  scala> val stuff = mutable.Set(42)
  stuff: scala.collection.mutable.Set[Int] = Set(42)

  scala> stuff += "abracadabra"
  <console>:7: error: type mismatch;
   found : java.lang.String("abracadabra")
   required: Int
         stuff += "abracadabra"
                  ^

但是可以手动声明类型：

  scala> val stuff = mutable.Set[Any](42)
  stuff: scala.collection.mutable.Set[Any] = Set(42)

还有一种情况，不能直接把List传递给Set的工厂方法：

  scala> val colors = List("blue", "yellow", "red", "green")
  colors: List[java.lang.String] =
    List(blue, yellow, red, green)


  scala> import scala.collection.immutable.TreeSet
  import scala.collection.immutable.TreeSet

  scala> val treeSet = TreeSet(colors)
  <console>:6: error: no implicit argument matching
    parameter type (List[java.lang.String]) =>
      Ordered[List[java.lang.String]] was found.
         val treeSet = TreeSet(colors)
                       ^

可行的方案是建立空的TreeSet[String]对象并用TreeSet的++操作把元素加进去：

  scala> val treeSet = TreeSet[String]() ++ colors
  treeSet: scala.collection.immutable.SortedSet[String] =
     Set(blue, green, red, yellow)

数组与列表之间转换

  scala> treeSet.toList
  res54: List[String] = List(blue, green, red, yellow)

  scala> treeSet.toArray
  res55: Array[String] = Array(blue, green, red, yellow)

Set与Map的可变与不可变互转

在转为不可变类型时，一般是建一个空的不可变集，再一个一个加上去：

  scala> import scala.collection.mutable
  import scala.collection.mutable

  scala> treeSet
  res5: scala.collection.immutable.SortedSet[String] =
    Set(blue, green, red, yellow)

  scala> val mutaSet = mutable.Set.empty ++ treeSet
  mutaSet: scala.collection.mutable.Set[String] =
    Set(yellow, blue, red, green)

  scala> val immutaSet = Set.empty ++ mutaSet
  immutaSet: scala.collection.immutable.Set[String] =
    Set(yellow, blue, red, green)

  scala> val muta = mutable.Map("i" -> 1, "ii" -> 2)
  muta: scala.collection.mutable.Map[java.lang.String,Int] =
     Map(ii -> 2, i -> 1)

  scala> val immu = Map.empty ++ muta
  immu: scala.collection.immutable.Map[java.lang.String,Int] =
     Map(ii -> 2, i -> 1)

元组

元组可以存放不同的类型：

  (1, "hello", Console)

元组经常被用来返回多个函数结果，如下面的函数要同时返回单词和索引：

  def longestWord(words: Array[String]) = {
    var word = words(0)
    var idx = 0
    for (i <- 1 until words.length)
      if (words(i).length > word.length) {
        word = words(i)
        idx = i
      }
    (word, idx)
  }
  
  scala> val longest =
       | longestWord("The quick brown fox".split(" "))
  longest: (String, Int) = (quick,1)

然后可以访问各个元素：

  scala> longest._1
  res56: String = quick

  scala> longest._2
  res57: Int = 1

还可以赋值给自己的变量（其实就是模式匹配）：

  scala> val (word, idx) = longest
  word: String = quick
  idx: Int = 1

  scala> word
  res58: String = quick

注意括号不能去掉，不然就是给两个变量赋值了两份：

  scala> val word, idx = longest
  word: (String, Int) = (quick,1)
  idx: (String, Int) = (quick,1)

有状态的对象

类似于JavaBean的getter和setter方法，Scala对象的非私有var x有自动生成的访问方法x和设值方法x_=。

对于类中的字段：

var hour = 12

会有额外的getter方法hour和setter方法hour_=。方法的访问性与字段一致。

拿这个例子来说：

  class Time {
    var hour = 12
    var minute = 0
  }

和下面的代码是一样的：

  class Time {

    private[this] var h = 12
    private[this] var m = 0

    def hour: Int = h
    def hour_=(x: Int) { h = x }

    def minute: Int = m
    def minute_=(x: Int) { m = x }
  }

所以可以直接定义getter和setter。

下面的代码在setter前进行检查：

  class Time {

    private[this] var h = 12
    private[this] var m = 12

    def hour: Int = h
    def hour_= (x: Int) {
      require(0 <= x && x < 24)
      h = x
    }

    def minute = m
    def minute_= (x: Int) {
      require(0 <= x && x < 60)
      m = x
    }
  }

再看一个温度的例子：

  class Thermometer {

    var celsius: Float = _

    def fahrenheit = celsius * 9 / 5 + 32
    def fahrenheit_= (f: Float) {
      celsius = (f - 32) * 5 / 9
    }
    override def toString = fahrenheit +"F/"+ celsius +"C"
  }

注意变量celsius的值为_，表示初始化值。对于数值代表0，对于布尔类型代表false，引用类型则代表null。

Scala中的初始化器=_，如果写成：

var celsius

这样就成了抽象变量（以后到了“抽象成员”这一章介绍），而不是一个没有初始化的变量。这个和Java的习惯很不一样。

使用的例子：

  scala> val t = new Thermometer
  t: Thermometer = 32.0F/0.0C

  scala> t.celsius = 100

  scala> t
  res3: Thermometer = 212.0F/100.0C

  scala> t.fahrenheit = -40

  scala> t
  res4: Thermometer = -40.0F/-40.0C

案例：离散事件模拟

来个SICP（Structure and Interpretation of Computer Programs，计算机程序的构造与解释）里的例子。

为数字电路定制语言

为了实现这三种基本的门，我们建立一个Wire类代表线路。可以这样构造线路：

val a = new Wire
val b = new Wire
val c = new Wire

或简洁地写成：

val a, b, c = new Wire

三个基本的门电路由以下三个过程模拟：

  def inverter(input: Wire, output: Wire)
  def andGate(a1: Wire, a2: Wire, output: Wire)
  def orGate(o1: Wire, o2: Wire, output: Wire)

注意这里的过程都没有返回值。按照函数式的思想，应该是返回构造好的门对象。但是在这里我们选择了没有返回值，而是通过副作用来模拟门电路。

在这副作用让一步步渐进地构造复杂的电路更加容易，如inverter(a,b)在a与b之间放置反转电路。

还有这里的方法名没有用动词而是用了名词，这是为了方便说明制造的是哪个门电路。这反映了DSL说明的本质：应该描述电路，而不是如何制造它。

下面是一个半加法器（half-adder）。它根据两个输入a和b产生累加和s。

累加的定义为：s= (a+b)%2及进位c，其中的c = (a+b)/2。

半加法器电路图：

用我们的代码描述：

  def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
    val d, e = new Wire
    orGate(a, b, d)
    andGate(a, b, c)
    inverter(c, e)
    andGate(d, e, s)
  }

接下来是一个全加法器，定义为根据参数a和b还有进位cin得到两个输出。一个是和sum = (a+b+cin)%2，另一个是进位输出count = (a+b+cin)/2：

代码为：

  def fullAdder(a: Wire, b: Wire, cin: Wire,
      sum: Wire, cout: Wire) {

    val s, c1, c2 = new Wire
    halfAdder(a, cin, s, c1)
    halfAdder(b, s, sum, c2)
    orGate(c1, c2, cout)
  }

这是内部DSL很好的例子：通过宿主语言将特定的语言定义为库面不是完全实现这种语言。

Simulation API

在我们的例子中，把参数列表和返回都为空的过程() => Unit作为基本的动作。给这样类型的过程起个别名叫Action：

type Action = () => Unit

私有变量保存时间，但提供对时间的公开访问：

  private var curtime: Int = 0

  def currentTime: Int = curtime

在特定时间执行的的操作定义为工作项目（work item）：

  case class WorkItem(time: Int, action: Action)

注意这里用的是样本类，所以用工厂方法创建实例就可以自动获得访问构造器参数time和action的方法。

还有一个类来保存末执行工作条目的排程表（agenda），它是按时间排序的：

  private var agenda: List[WorkItem] = List()

提供在一定时延后加入新的工作条目的方法，加入操作也要排序：

  def afterDelay(delay: Int)(block: => Unit) {
    val item = WorkItem(currentTime + delay, () => block)
    agenda = insert(agenda, item)
  }

  private def insert(ag: List[WorkItem],
      item: WorkItem): List[WorkItem] = {

    if (ag.isEmpty || item.time < ag.head.time) item :: ag
    else ag.head :: insert(ag.tail, item)
  }

核心是run方法：

  def run() {
    afterDelay(0) {
      println("*** simulation started, time = "+
          currentTime +" ***")
    }
    while (!agenda.isEmpty) next()
  }
  
  private def next() {
    (agenda: @unchecked) match {
      case item :: rest =>
        agenda = rest
        curtime = item.time
        item.action()
    }
  }

注意这里为了方便去掉了空列表的情况。为了防止编译器警告我们在模式匹配里故意漏掉了列表为空的情况，在这里使用了(agenda: @unchecked) match而不是agenda match。

完整的代码在包org.stairwaybook.simulation里：

  abstract class Simulation {

    type Action = () => Unit

    case class WorkItem(time: Int, action: Action)

    private var curtime = 0
    def currentTime: Int = curtime

    private var agenda: List[WorkItem] = List()

    private def insert(ag: List[WorkItem],
        item: WorkItem): List[WorkItem] = {

      if (ag.isEmpty || item.time < ag.head.time) item :: ag
      else ag.head :: insert(ag.tail, item)
    }

    def afterDelay(delay: Int)(block: => Unit) {
      val item = WorkItem(currentTime + delay, () => block)
      agenda = insert(agenda, item)
    }

    private def next() {
      (agenda: @unchecked) match {
        case item :: rest =>
          agenda = rest
          curtime = item.time
          item.action()
      }
    }

    def run() {
      afterDelay(0) {
        println("*** simulation started, time = "+
            currentTime +" ***")
      }
      while (!agenda.isEmpty) next()
    }
  }

电路模拟

这里创建了BasicCircuitSiomulation来模拟电路。

为了模拟电路和延迟声明了三个方法：InverterDelay、AndGateDelay、OrGateDelay。由于不同模拟电路的技术参数不同，所以这三个方法是抽象方法。

Wire类

需要支持的三种基本动作：

getSignal: Boolean：返回当前线路上的信号。

setSignal(sig: Boolean)：设置线路信号。

addAction(p: Action)：添加动作到线路上。基本思想是所有附加在某线路上的动作过程在每次信号改变时被执行。通过连接组件可以为线路添加该组件的功能。加上的动作会在被加到线路时以及每次线路信号改变时被执行。

实现代码sigVal代表当前信号，actions是附加的动作过程。需要注意的是setSignal方法，当信号改变时，新的信号首先被保存在变量sigVal中，然后执行所有线路附加动作：

  class Wire {
    private var sigVal = false
    private var actions: List[Action] = List()

    def getSignal = sigVal

    def setSignal(s: Boolean) =
      if (s != sigVal) {
        sigVal = s
        actions foreach (_ ())
      }

    def addAction(a: Action) = {
      actions = a :: actions
      a()
    }
  }

注意上面的缩写格式：actions forearch(_())代表对每个元素执行_()。在“函数和装饰”这一章的“占位符”部分说明过，函数_()是f => f()的缩写，代表空参数函数。

反转操作

inverter方法会在安装之后以及每次线路信号变化时被调用。它通过setSignal把输出设为输入的反值。

另外，由于还要模拟电路的响应时间，所以输入值改变以后，还要等InverterDelay单位的模拟时间后，才发生改变：

  def inverter(input: Wire, output: Wire) = {
    def invertAction() {
      val inputSig = input.getSignal
      afterDelay(InverterDelay) {
        output setSignal !inputSig
      }
    }
    input addAction invertAction
  }

注意这里的afterDelay方法是把这个操作加到队列的最后面。

与门和或门操作

大致思想和上面类似：

  def andGate(a1: Wire, a2: Wire, output: Wire) = {
    def andAction() = {
      val a1Sig = a1.getSignal
      val a2Sig = a2.getSignal
      afterDelay(AndGateDelay) {
        output setSignal (a1Sig & a2Sig)
      }
    }
    a1 addAction andAction
    a2 addAction andAction
  }

  def orGate(o1: Wire, o2: Wire, output: Wire) {
    def orAction() {
      val o1Sig = o1.getSignal
      val o2Sig = o2.getSignal
      afterDelay(OrGateDelay) {
        output setSignal (o1Sig | o2Sig)
      }
    }
    o1 addAction orAction
    o2 addAction orAction
  }

模拟输出

通过探针（probe）观察线路上信号的改变。

还是在信号改变时被调用，显示输出线路的名称、模拟时间、信号值：

  def probe(name: String, wire: Wire) {
    def probeAction() {
      println(name +" "+ currentTime +
          " new-value = "+ wire.getSignal)
    }
    wire addAction probeAction
  }

运行模拟器

BasicCircuitSimulation继承了CircuitSimulation

  package org.stairwaybook.simulation

  abstract class CircuitSimulation
    extends BasicCircuitSimulation {

    def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
      val d, e = new Wire
      orGate(a, b, d)
      andGate(a, b, c)
      inverter(c, e)
      andGate(d, e, s)
    }

    def fullAdder(a: Wire, b: Wire, cin: Wire,
        sum: Wire, cout: Wire) {

      val s, c1, c2 = new Wire
      halfAdder(a, cin, s, c1)
      halfAdder(b, s, sum, c2)
      orGate(c1, c2, cout)
    }
  }

剩下的电路延迟时间和定义被模拟的电路都留在Scala交互Shell中实现：

  scala> import org.stairwaybook.simulation._
  import org.stairwaybook.simulation._

定义延迟时间：

  scala> object MySimulation extends CircuitSimulation {
       | def InverterDelay = 1
       | def AndGateDelay = 3
       | def OrGateDelay = 5
       | }
  defined module MySimulation

定义一下简化以后对MySimulation的引用：

  scala> import MySimulation._
  import MySimulation._

定义线路的部分。先定义四根线路，再把探针放在其中的两根上。探针会立即输出结果：

  scala> val input1, input2, sum, carry = new Wire
  input1: MySimulation.Wire =
      simulator.BasicCircuitSimulation$Wire@111089b
  input2: MySimulation.Wire =
      simulator.BasicCircuitSimulation$Wire@14c352e
  sum: MySimulation.Wire =
      simulator.BasicCircuitSimulation$Wire@37a04c
  carry: MySimulation.Wire =
      simulator.BasicCircuitSimulation$Wire@1fd10fa

  scala> probe("sum", sum)
  sum 0 new-value = false

  scala> probe("carry", carry)
  carry 0 new-value = false

加上半加法器：

  scala> halfAdder(input1, input2, sum, carry)

逐次把两根输入线信号设为true，并执行模拟过程：

  scala> input1 setSignal true

  scala> run()
  *** simulation started, time = 0 ***
  sum 8 new-value = true

  scala> input2 setSignal true

  scala> run()
  *** simulation started, time = 8 ***
  carry 11 new-value = true
  sum 15 new-value = false

全部代码如下：

package org.stairwaybook.simulation

abstract class BasicCircuitSimulation extends Simulation {

  def InverterDelay: Int
  def AndGateDelay: Int
  def OrGateDelay: Int

  class Wire {

    private var sigVal = false
    private var actions: List[Action] = List()

    def getSignal = sigVal

    def setSignal(s: Boolean) =
      if (s != sigVal) {
        sigVal = s
        actions foreach (_ ())
      }

    def addAction(a: Action) = {
      actions = a :: actions
      a()
    }
  }

  def inverter(input: Wire, output: Wire) = {
    def invertAction() {
      val inputSig = input.getSignal
      afterDelay(InverterDelay) {
        output setSignal !inputSig
      }
    }
    input addAction invertAction
  }

  // continued in Listing 18.10...
  // ...continued from Listing 18.9
  def andGate(a1: Wire, a2: Wire, output: Wire) = {
    def andAction() = {
      val a1Sig = a1.getSignal
      val a2Sig = a2.getSignal
      afterDelay(AndGateDelay) {
        output setSignal (a1Sig & a2Sig)
      }
    }
    a1 addAction andAction
    a2 addAction andAction
  }

  def orGate(o1: Wire, o2: Wire, output: Wire) {
    def orAction() {
      val o1Sig = o1.getSignal
      val o2Sig = o2.getSignal
      afterDelay(OrGateDelay) {
        output setSignal (o1Sig | o2Sig)
      }
    }
    o1 addAction orAction
    o2 addAction orAction
  }

  def probe(name: String, wire: Wire) {
    def probeAction() {
      println(name +" "+ currentTime +
          " new-value = "+ wire.getSignal)
    }
    wire addAction probeAction
  }
}

abstract class Simulation {

  type Action = () => Unit

  case class WorkItem(time: Int, action: Action)

  private var curtime = 0
  def currentTime: Int = curtime

  private var agenda: List[WorkItem] = List()

  private def insert(ag: List[WorkItem],
      item: WorkItem): List[WorkItem] = {

    if (ag.isEmpty || item.time < ag.head.time) item :: ag
    else ag.head :: insert(ag.tail, item)
  }

  def afterDelay(delay: Int)(block: => Unit) {
    val item = WorkItem(currentTime + delay, () => block)
    agenda = insert(agenda, item)
  }

  private def next() {
    (agenda: @unchecked) match {
      case item :: rest =>
        agenda = rest
        curtime = item.time
        item.action()
    }
  }

  def run() {
    afterDelay(0) {
      println("*** simulation started, time = "+
          currentTime +" ***")
    }
    while (!agenda.isEmpty) next()
  }
}


abstract class CircuitSimulation
  extends BasicCircuitSimulation {

  def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
    val d, e = new Wire
    orGate(a, b, d)
    andGate(a, b, c)
    inverter(c, e)
    andGate(d, e, s)
  }

  def fullAdder(a: Wire, b: Wire, cin: Wire,
      sum: Wire, cout: Wire) {

    val s, c1, c2 = new Wire
    halfAdder(a, cin, s, c1)
    halfAdder(b, s, sum, c2)
    orGate(c1, c2, cout)
  }
}

 object MySimulation extends CircuitSimulation {
           def InverterDelay = 1
           def AndGateDelay = 3
           def OrGateDelay = 5

  def main(args: Array[String]) {
    val input1, input2, sum, carry = new Wire

    probe("sum", sum)
    probe("carry", carry)
    halfAdder(input1, input2, sum, carry)

    input1 setSignal true
    run()

    input2 setSignal true
    run()
  }
}

Category: scala | Tags: scala | Read Count: 5911

[回复]

civaget 说:
2023年12月19日 17:56

sdsdsdsdsdd

温其如玉

Jade's Dungeon

Scala学习笔记-Part.02

样本类和模式匹配

简单的例子

样本类

模式的种类

通配模式

常量模式

变量模式

变量模式与常量模式的区别

构造器模式

序列模式

元组模式

类型模式

类型擦除

变量绑定

守卫模式

模式重叠

封闭类

Option类型

模式无处不在

变量定义

偏函数的样本序列

for表达式

大型的例子

使用列表

列表字面量

列表类型

构造列表

列表的基本操作

列表模式

List类的一阶方法

连接列表

分治原则

列表长度

取头和尾

反转列表

前缀与后缀

取得指定元素

zip

toString 和 mkString

列表的转换

例：归并排序

List类的高阶函数

列表间映射

过滤

列表论断

折叠列表

例子：使用折叠实现列表反转

排序

List对象的方法

通过元素创建列表

按数值范围创建列表

创建重复元素的列表

解除Zip列表

连接列表

映射与测试配对

了解Scala的类型推断方法

集体类型

概览

序列

列表

列表缓存

数组

数组缓存

队列

栈

字符串

Set与Map

使用Set

Map

默认的Set和Map

有序的集体和映射

同步的Set和Map

可变与不可变类型的比较

初始化集合

数组与列表之间转换

Set与Map的可变与不可变互转

元组