Functional Programming 笔记(6)

前面介绍了 List,这部分涉及一些其他的 collection。

Vector 是一个使用上类似 vector 但实现上接近一棵树的 immutable 容器,很多操作和 List 类似,同时支持添加元素的 +: 和 :+ 操作(前后)。要了解这些容器的关系就得看看继承,List 和 Vector 都是 Seq 的子类,而 Seq 和 Set、Map 都是 Iterable 的子类。另有一个 Seq 是 Range,常见的 to/until/by 都是产生 Range 的操作。对于 Seq 来说,List 大部分 higher order 操作都是支持的。

在 imperative programming 里面的 nested loop 通常可以通过 Seq 类的类似 flatMap 等 higher order function 通过嵌套来实现,但是这个看起来有点乱,于是一个 grammar sugar 就是将这种结构通过 for-expression 写出来,for 的本质就是将内容替换成为一个一个的 withFilter + flatMap,

(1 to 4) map (i =>
  (1 to i).map (j => (i, j))
)

类似这段代码产生的结构却不是我们希望的 Pair 的 Seq,事实上,我们知道 map 本身会产生一个 Seq,因此这必然是 Seq of Seq,问题是结果里面出现的是

res1: scala.collection.immutable.IndexedSeq[scala.collection.immutable.IndexedSeq[(Int, Int)]] = 
Vector(Vector((1,1)), Vector((2,1), (2,2)), Vector((3,1), (3,2), (3,3)), Vector((4,1), (4,2), (4,3), (4,4)))

其中 IndexedSeq 是 Range 和 Vector 的公共父类,那么 IndexedSeq 如何找到 Vector 来返回这个结果的呢?

如果我们希望去掉这个嵌套,外层的 map 就得换成 flatMap,但是这样一来势必没有 for 看得清楚,可以比较下面两段代码

(1 to 4) flatMap (i =>
  (1 to i).map (j => (i, j))
)
for (i <- 1 to 4; j <- 1 to i) yield (i, j)

其实类似 Set/Map 也支持类似的操作(Iterable),只是 Set 的结果仍然是 Set,

val s = (1 to 5).toSet
s map (i => i % 3)

合理的利用这个规则可以简化不少问题,课程中 8 皇后的解是一个比较典型的例子。for 的表达其实和 map/reduce、数据操作有着极为密切的联系,我们知道通过 map/reduce 可以实现数据库里面的各类操作,如 PIG/HIVE 就是提供了从类 SQL 到 map/reduce job 的 planning,因此通过这些 higher order functions 比较容易实现对 memory 里面的数据的这类操作。另一点就是 cascading 的 scala binding,scalding 其实也是这类概念了。灵活使用 for 实现各类操作算是学习 scala 一个比较常用的 practice 了。

scala 的 Map 是比较奇葩的,他可以当 function 来用,对于不在 Map 里面的 key 我们甚至可以设默认值。同时通过 get 我们可以获得 Option,这样就可以处理不存在的情况(Option 有 None 和 Some 两种实现)。另一种是通过 withDefaultValue 来引入默认值。

通过参数类型加 * 可以让这个参数重复任意多次,这个在创建 List、Set、Map 等对象的函数里面比较有用。

最后一个练习也很有意思,将一个给定的电话号码翻译成单词,这个类似的东西在 007 系列里面见过,Mr. Bond 的某个密码设置成了他某个 gf 的名字,实际上是数字密码了,这个就是按照手机、电话键盘上面的编排将字母翻译到数字的,这样某些电话号码就被赋予了某些隐藏的意义,我们常见的什么 206-1CALLME 啥的就是这样来的,那么假设你有一个单词的列表,给你一个数字串如何尝试获得所有可行的分词组合呢?

从规则上来想这个问题大约这样:

  • 去前面 k 个字符看看能不能得到单词,如果不 okay,就试试 k + 1 直到号码结束;
  • 如果是一个单词(若干个单词),就将这个结果和剩下部分的结果做 Descartes 积(与空集乘结果为空集)拼接在一起。

有了这两条我们就可以想想怎么组织,因为结果是 List[String],我们的递归调用也会产生这样的一组,这和当前的结果拼接无非可以用一个 for expression 将拼接后的 yield 出去即可。如何检查一个号码是否对应一组单词呢?其实通过单词到数字的变换以后通过数字进行 groupBy 就能得到一个我们需要的 map 来检查了。这个过程反而是最简单的。当然要注意大小写问题,我们的单词需要先 normalize 一下。

但是如果你希望通过 C++ 来做,尽管有标准库,到了最后 parsing 阶段,如果不写 recursion,就得来 back tracing 了。

——————
And when Esau heard the words of his father, he cried with a great and exceeding bitter cry, and said unto his father, Bless me, even me also, O my father.

Advertisements
Functional Programming 笔记(6)

发表评论

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