Functional Programming 笔记(1)

这个是学习 coursera 上 scala 课程的一些笔记。

环境 setup

sbt 在这里下载。课程上神奇的 eclipse 的确令人艳羡,我这里列出另外两个方案。

  • emacs 自己的 scala-mode2,用 emacs 24 自己的 package.el 方便许多呀(repos 见这里
  • 通过 eclipse 的插件将 emacs 挂上去,这样的话你需要 eclipse + eclim + emacs-eclim,debian 下面的 eclipse 是 3.8,这样只能装 eclim 1.7.13,之后同样通过 package.el 装 emacs-eclim。装 eclim 的时候加上 scala 的插件。

不过后者似乎现在还没琢磨清楚怎么 work,eclim 直接有 vim 的集成,emacs 悲催一点。

tail recursion

记得前面讨论 functional programming 的时候通过 factorial 解释了 imperative programming 的区别。那里的递归调用并不是一个标准的 tail recursion,写出来大概是这样的展开 facortial (n) = n * ((n-1) * factorial (n – 2)) 下去,这个问题在于括号的顺序是嵌套进去的,意味着每个递归调用结束后你还要干点事情(* n),所以不好,因此要弄成尾递归必须改变括号的顺序,比如弄成 1 * n * (n-1) * … 就比较好,我们就能一词乘了,但是我们不能用 mutable 的变量存放中间值(那就是 imperative programming 了),那其实好办,因为无非多用一个参数传递当前的乘积咯

def fac (n : Int) : Int = {
  def facIter (n: Int, prod: Int) : Int =
    if (n == 0) prod else facIter (n - 1, n*prod)
  facIter (n, 1)
}

不知道更一般的 tail recursion 构造是否也可以 follow 类似的逻辑?

替换与 lambda calculus

前文也讲过 lambda calculus 与替换的关系,其实对于 scala 来说本质上就是在不断的替换当前的 expression,通过 reduction 将其最终弄成一个“值”。因此通过 scala 这类语言求解问题更接近于“寻找替换规则”的过程。每一个规则对应于一个 def,这和 C/C++ 等 imperative programming 里面的“函数”并不是一个意思。

一个简单的求平方根的例子,我们需要构造方程 x^2 - a = 0,这样可以得到 Newton 法更新的“规则”如下 x_{t+1} = \frac{1}{2}(x_t + \frac{a}{x_t})。因此我们可以想象如何将这个过程通过规则描述出来:

  • 更新的规则,Newton 法已经告诉我们了
  • 判断是否终止的规则,如绝对误差、相对误差
  • 还需要一条规则,如果终止规则不成立,就根据更新规则返回的值继续尝试

这样一来就有下面的代码(课程里面已经介绍了)

object demo {
  def sqrt (x : Double) : Double = {
    def abs (z : Double) : Double =
      if (z < 0) -z else z

    def isGoodEnough (guess:Double) : Boolean =
      abs (guess * guess - x) / x < 1e-5

    def improve (guess:Double) : Double =
      (guess + x / guess) / 2

    def sqrtIter (guess: Double): Double = {
      if (isGoodEnough (guess))
        guess
      else
        sqrtIter (improve (guess))
      }

    sqrtIter (1.0)
  }

  def main (arg:Array [String]) = {
    println (sqrt (arg(0).toDouble))
  }
}

尽管这里通过 scope 简化了内部那些函数的书写,其实通过 scala 编译还是产生了独立的 def 语句,并将缺失的参数加入了,从这个角度来看,和 this 指针不必“显式传递”给成员函数类似(这是很多 OO 语言的特点),通过 scope 减少需要书写的变量个数也是一种类似的 grammar sugar。

并不强调循环

一般 imperative programming 讲控制结构除了 if-then-else 之外就是各种循环,但是 functional programming 往往只是象征性的提供了一个循环的 expression,更多的它将循环通过递归来进行描述。可以认为循环是递归的一个简单产物,因为递归可以实现远远不止是循环那么简单的结构。

通过思考“规则”而不是具体去操纵变量,如何存储这些东西,程序员求解的思路往往会很不一样,这也就是 functional programming 带来的新的思维方式。

——————
And Jacob said to Rebekah his mother, Behold, Esau my brother is a hairy man, and I am a smooth man:

Advertisements
Functional Programming 笔记(1)

一个有关“Functional Programming 笔记(1)”的想法

  1. […] 模拟 recursion 从某个角度来说可以从最基本的地方开始,顺着推到更复杂的情况,直到达到问题求解的要求,不少 dynamic programming 的问题本质上是这样的过程;另一种就是将 stack 搬到堆上去做,用户自己创建自己的 stack,就不那么容易 overflow 了。另一个策略就是转换到 tail recursion 的表述形式上。经典的例子仍然是 factorial(参考这里和这里): […]

发表评论

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