函数式编程中的数据结构

在函数式编程中，往往大量使用一些核心的数据结构和算法。相比于面向对象编程利用代码复用来减少冗余，函数式编程更倾向于编写简洁易复用的代码，因为语言将重点放在使用核心数据结构和算法实现业务逻辑上。

函数式语言中每种集合类型都支持同一批无副作用的高阶函数，称为组合器（combinator），如map、filter、fold等。一旦你了解了这些组合器，你就可以根据自身对数据访问的需求及性能要求，选用合适的集合类型，用同样的组合器函数去操作数据。在所有的软件开发工作中，这些集合类型是代码复用与组合的最有效工具。

1 序列

序列的元素时可以按特定的顺序访问的，scala.collection.Seq是一个trait，是所有可变或不可变序列类型的抽象，其子trait对应scala.collection.mutable.Seq和scala.collection.immutable.Seq。

推荐将Seq作为序列型数据结构的参数或作为返回值，因为这样，Seq的任何子类型都可以使用。Seq使用+:方法来构造新的序列，使用++连接两个序列。



In [2]:

    
val seq1 = Seq("Programming", "Scala")
val seq2 = "People" +: "should" +: "read" +: Seq.empty
val seq3 = seq2 ++ seq1









    





seq1: Seq[String] = List("Programming", "Scala")
seq2: Seq[String] = List("People", "should", "read")
seq3: Seq[String] = List(
  "People",
  "should",
  "read",
  "Programming",
  "Scala"
)

可以考虑用immutable.Vector代替List，因为不可变Vector的所有操作都是O(1)，而List对于那些需要访问头部以外元素的操作，都需要O(n)操作。

有关预定义的讨论

为了鼓励程序员使用不可变的集合类型，Predef在暴露不可变集合类型时，不需要显示导入或使用全路径导入。但是Predef还将scala.collection.Seq导入到了当前作用域，该类型是可变集合类型和不可变集合类型共同的抽象特质，这使得传入的Seq类型实例可能是可变的，所以线程是不安全的。

1.1 运用包对象为Seq定义别名，覆盖原有别名定义

为了使用scala.collection.immutable.Seq代替默认的scala.collection.Seq，使用包对象来解决：

package fp
package object datastructs {
  type Seq[+A] = scala.collection.immutable.Seq[A]
  val Seq = scala.collection.immutable.Seq
}

package关键字也是包对象定义的一部分，在一个包中只能有一个包对象。最后，该文件的路径是src/main/scala/fp/datastructs/package.scala，这是一种常用的命名习惯。

在包对象中，我们声明了一个类型别名和一个val变量。类型声明导入之后，使用Seq声明一个实例时，就需要使用scala.collection.immutable.Seq；val Seq的声明语句将伴随对象引入作用域，于是类似Seq(1,2,3,4)的语句就会触发scala.collection.immutable.Seq.apply方法的调用。

2 映射表

映射表用来存储键值对，但不应将其余很多数据结构的map方法混淆。映射表与map方法有一定程度的相似，前者每个键都对应一个值，后者每个输入元素都产生一个输出元素。



In [3]:

    
val stateCapitals = Map(
    "Alabama" -> "Montgomery",
    "Alaska" -> "Juneau",
    "Wyoming" -> "Cheyenne"
)









    





stateCapitals: Map[String, String] = Map(
  "Alabama" -> "Montgomery",
  "Alaska" -> "Juneau",
  "Wyoming" -> "Cheyenne"
)



In [4]:

    
val lengths = stateCapitals map {
    kv => (kv._1, kv._2.length)
}









    





lengths: Map[String, Int] = Map(
  "Alabama" -> 10,
  "Alaska" -> 6,
  "Wyoming" -> 8
)



In [5]:

    
val caps = stateCapitals map {
    case (k, v) => (k, v.toUpperCase)
}









    





caps: Map[String, String] = Map(
  "Alabama" -> "MONTGOMERY",
  "Alaska" -> "JUNEAU",
  "Wyoming" -> "CHEYENNE"
)



In [6]:

    
val stateCapitals2 = stateCapitals + ("Virginia" -> "Richmond")









    





stateCapitals2: Map[String, String] = Map(
  "Alabama" -> "Montgomery",
  "Alaska" -> "Juneau",
  "Wyoming" -> "Cheyenne",
  "Virginia" -> "Richmond"
)

key -> value的语法形式实际上用库中的隐式转换实现的，实际调用了Map.apply方法。Map.apply方法的参数为一个两元素的元组（键值对）。

3 集合

集合是无序集合类型的一个例子，所以集合不是序列。集合要求元素具有唯一性。



In [7]:

    
val states = Set("Alabama", "Alaska", "Wyoming")









    





states: Set[String] = Set("Alabama", "Alaska", "Wyoming")



In [8]:

    
val lengths = states map (st => st.length)









    





lengths: Set[Int] = Set(7, 6)



In [9]:

    
val states2 = states + ("New York", "Illinois")









    





states2: Set[String] = Set(
  "Alaska",
  "Alabama",
  "New York",
  "Illinois",
  "Wyoming"
)