Functional Programming 笔记(4)

容器从 List 开始(scala.collections.immutable.List)。

其实做法很直接,很重要的一点是 immutable,任何改动都会产生一个新的 List,基本结构就是 Nil 和 Cons,简化拼接操作为 ::,同时可以利用这个获得 match 的 pattern。注意 : 结尾的运算符是右结合。基本操作有 head、tail、isEmpty,length、last(最后一个元素,线性时间),init(除掉最后一个其余的,线性时间),take/drop 取第 n 个之前/后,() 表示第 n 个。通过 ++ 拼接 List,reverse 反转,updated 将第 n 个位置的元素更新为给定的,这样也会产生新的 List。indexOf 找到某个元素,返回 index,没有返回 -1,contains 判断是否含有给定元素。splitAt、removeAt 可以将给定位置的元素切分 List 或者去掉。

所谓的 Pair、Tuple 是类似 C++ 概念的两个玩意,但是是 immutable 的,一般用 () 表示。不过似乎对应的是一堆 Tuplen 的类? 使用 generic type 放参数的位置比 java 自然一点,同时支持 covariant/contravariant。这个和 C++ 的不大一样的在于 implicit 关键字,C++ 通过 default value 可以剩掉很多麻烦(traits 类就是一个重要的用法),这也就是说你知道默认值是谁,但是 scala 编译时选择默认的原则并不是通过声明的默认值,比如下面课程里面的例子

def msort [T](a : List[T]) (implicit ord : Ordering[T]): List[T] = {
  def merge (a: List[T], b: List[T]) : List[T] = (a, b) match {
    case (Nil, b) => b
    case (a, Nil) => a
    case (x :: xs, y :: ys) =>
      if (ord.lt (x, y)) x :: merge (xs, b)
      else y :: merge (a, ys)
  }

  val n = a.length / 2
  if (n == 0) a
  else {
    val (former, latter) = a splitAt n
    merge (msort (former), msort (latter))
  }
}

这里的 Ordering[T] 会被转换成 Ordering[Int],这其实是个 trait class,但是谁提供了 Ordering[Int] 的实现(注意这里面有个 abstract 函数)呢?比较奇怪的是这个实现在 Ordering.Int,有点晕?其实 Ordering 也是个 object(我真的没搞明白 scala 这么做到底有啥好处,这一个 import 进来的似乎不仅是 trait class 还有 object),那为啥 Ordering[Int] 一定要被翻译到 Ordering[Int] 而不是我自己定义的某个实现呢?某课上说这是 companion object associated with T。看起来这玩意比 C++ 的 ADL 还要令人费解。

后面自然是 List 最常见的一些 pattern(更多参见这里

  • map 将 List 映射成为另一个 List,提供一个 mapping function
  • filtering,提供一个 predicate,类似的有 filterNot、partition(将 list 分为两部分一个是满足条件的一个是不满足的)、takeWhile(取满足条件的最长前缀)、dropWhile(取后缀)、span(takeWhile 和 dropWhile 两部分)、
  • reduceLeft,从左边开始 reduce,即左结合下的 reduce。
  • foldLeft 是更广义的 reduceLeft,后者要求函数的 signature 为 (T, T) => T,而前者是 (U, T) => U
  • 对应的有 reduceRight 和 foldRight,但是由于 List 的结构,这两个明显效率低于 left 版本
  • 逻辑操作有 forall、exists
  • foreach 对每个元素作用一个函数
  • groupBy,提供一个映射到 key 的函数,得到一个 Map

这也能看出来 C++ 的原则是不是最合适的操作我宁可不写出来,避免被 abuse,而 scala 图方便什么都有,代价是什么用户得看文档。 比较有意思的就是 recursion 和 mathematical induction 之间的关系,这能方便我们确认一个算法是不是正确。不过有时候 recursion 有点让人迷惑,某人最喜欢问的面试题就是给你一个 binary tree,然后你如何确认它是 search tree,很自然但错误的想法就是每个节点满足 left child < value < right child,这个局部性质并不能保证全局正确。

—————–
Therefore God give thee of the dew of heaven, and the fatness of the earth, and plenty of corn and wine:

Advertisements
Functional Programming 笔记(4)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s