《Functional Programming Principles in Scala》

    #scala

    最近借着几个周末在 Coursera 上完成了 《Functional Programming Principles in Scala 》,算是终于把之前立的上一门 Coursera 课程的 flag 给做到了。

    1. 课程之外

    这门课是 Scala 的作者 Martin Odersky, Professor 开的,相比看书,从中能看到更多原汁原味的设计思想,例如为什么会有 Call-By-Name 和 Call-By-Value、Curring 函数等。

    学习这门课的时候我脑海里不断的浮现出这条曲线

    Dunning-Kruger Effect

    感觉自己刚看了一个月 scala,就敢写《scala 30分钟极简入门》也是自信心爆棚了。

    严格来讲,这门课程不算难,看过《Scala 编程》这本书的话,估计会觉得更轻松一些。不过我之前看的是《Scala 实用指南》,系统知识不全,按照规定时间差不多刚好能做完。几个编程作业都是 100%,最近每个周六日都熬到凌晨三点多也算是值了。

    Coursera 上相关课程很多,单独通关或者组队一块上一门课程,都是不错的选择。

    2. 课程笔记

    由于是笔记,记录的比较杂。课件及作业我上传到了这里

    2.1. Week1:Getting Started + Functions & Evaluation

    • Call-By-Name Call-By-Value 会带来计算次数的不同,但不是绝对的哪个更加节省计算。If CBV evaluation of an expression e terminates, then CBN evaluation of an expression e terminates, too.The other direction is not true.
    • def loop: Boolean = loop, A defination def x = loop is OK, but a defination val x = loop will lead to an infinite loop.
    • def and(x: Boolean, y: Boolean) = if (x) y else false;def or(x: Boolean, y: Boolean) = if (!x) y else true
    • @tailrec 可以帮我们验证是否是尾递归
    • Exercise 1: Pascal’s Triangle,两种方式,一种是pascal(r, c) = pascal(r - 1, c - 1) + pascal(r, c - 1),还有一种是pascal(r, c) = C(c, r) = factorial(c) / (factorial(r) * factorial(c -r))。第一种好处是不容易越界,但是重复计算多,递归层数较多。第二种恰好相反,比如 factorial(13)就已经比 INT32_MAX 更大了,容易越界。
    • Exercise 2: Parentheses Balancing,对()计数,类似于栈的操作
    • Exercise 3: Counting Change:https://stackoverflow.com/questions/12629721/coin-change-algorithm-in-scala-using-recursion,自己最开始只按照coins有序来写的代码,没有通过,思路是一致的。

    2.2. Week2:Higher Order Functions

    • Functions that take other functions as parameters or that return functions as results is called higher order functions.
    • Currying: def f(args1)...(argsn−1)(argsn) = E is equivalent to def f = (args1 ⇒ (args2 ⇒ ...(argsn ⇒ E)…))
    • 构造函数里可以调用 require,require is a predefined function: require(y != 0, ”denominator must be nonzero”)

    2.3. Week3:Data and Abstraction

    • 如果 class 有未定义的 method,那么必须在class前增加 abstract
    • Any => the base type of all types
    • AnyRef => the base type of all reference types, Alias of ‘java.lang.object’
    • AnyVal => the base type of all primitive types.
    • Nothing is at the bottom of Scala’s type hierarchy.It’s a subtype of every other type.There is no value of type Nothing. Null is a subtype of every class that inherits from Object;it’s incompatible with subtypes of AnyVal.
    • if (true) 1 else false 的返回值是 AnyVal

    2.4. Week4:Types and Pattern Matching

    • S <: T means: S is a subtype of T.S >: T means: S is a supertype of T, or T is a subtype of S.
    Say C[T] is a parameterized type and A, B are types such that A <: B.
    In general, there are three possible relationships between C[A] and C[B]
    C[A] <: C[B] => C is convariant
    C[A] >: C[B] => C is contravariant
    neither C[A] nor C[B] is a subtype of the other => C is nonvariant
    

    2.5. Week5:Lists

    • Difference between FoldLeft and FoldRight: For operators that are associaive and commutative, foldLeft and foldRight are equivalent(event through there may be a difference in efficiency).

    2.6. Week6:Collections

    //N-Queens
    def isSafe(col: Int, queens: List[Int]): Boolean = {
      val row = queens.length
      val queensWithRow =
        (row - 1 to 0 by -1) zip queens
      //println(s"col:$col queensWithRow:${queensWithRow}")
      queensWithRow forall {
        case (r, c) => col != c && math.abs(col - c) != row - r
      }
    }
    def nqueens(n: Int): Set[List[Int]] = {
      def placeQueens(k: Int): Set[List[Int]] = {
        if (k == 0) Set(List())
        else {
          for {
            queens <- placeQueens(k - 1)
            col <- 0 until n
            if (isSafe(col, queens))
          } yield col :: queens
        }
      }
      placeQueens(n)
    }
    
    

    3. 杂想

    编程语言其实是个挺神奇的东西,可以基础到某些设计思想或者趋势,比如越来越多的语言把类型放到了变量名后面,Types are moving to the right

    函数式编程语言特别像大学里 函数空间 这个概念,大学时最开始学习实数、复数空间时感觉难度不大,到了函数空间,复杂度就一下变高了,天书一样根本听不懂。从对象编程、过程式编程到函数式编程的过程,跟这个非常像,函数变成了一等公民,基于函数的各种组合,我们可以构造出更简洁、高效的模块。

    函数式编程给我的最大的感觉是注重函数以及不变量,由于没有可变变量,并发变得比较容易。这门课整体来讲属于入门课程,作者如果开一门 Scala 语言设计思想的课,我应该会第一时间去听吧。

    万事开头难,找到知乎的一篇总结帖,准备用业务时间刷下一节课,欢迎组团。

    课程里一些简洁同时非常有用的链接:

    1. https://www.coursera.org/learn/progfun1/supplement/Sauv3/cheat-sheet
    2. https://www.coursera.org/learn/progfun1/supplement/D9pm0/learning-resources
    3. https://www.coursera.org/learn/progfun1/supplement/KPiGt/scala-style-guide
    4. https://www.scala-lang.org/api/current/index.html
    5. http://twitter.github.io/scala_school/