Scala 中的函数式编程基础
主要來自 Scala 語言發(fā)明人 Martin Odersky 教授的 Coursera 課程?《Functional Programming Principles in Scala》。
------------------------------部分一---------------------------------------
很久以前寫過一個非常簡單的?python lambda 函數(shù)博客，里頭有 filter，map，reduce等，是python中很有意思的部分，可以先看看。
另外酷殼網(wǎng)陳皓寫了一篇介紹函數(shù)式編程的博客，言簡意賅，對理解函數(shù)式編程很有幫助，非常值得一看。
Scala 本意是可伸展。它的設(shè)計(jì)哲學(xué)是：允許用戶通過定義感覺像原生語言支持一樣的易用庫去在他們需要的方向上改進(jìn)和發(fā)展語言——Scala allows users to grow and adapt the language in the directions they need by defining easy-to-use libraries that feel like native language support.。Scala 運(yùn)行在 Java 平臺上，可以與所有的 Java 庫無縫交互。
1. Function evaluations
Scala 是純粹的面向?qū)ο笫降木幊?#xff0c;所有的 value 都是一個對象。
Scala 是函數(shù)式的編程，它把每一個函數(shù)看做一個 value，函數(shù)即對象。
1.1 函數(shù)的副作用
純函數(shù)（Pure Function）是這樣一種函數(shù)——輸入輸出數(shù)據(jù)流全是顯式（Explicit）的。
顯式（Explicit）的意思是，函數(shù)與外界交換數(shù)據(jù)只有一個唯一渠道——參數(shù)和返回值；函數(shù)從函數(shù)外部接受的所有輸入信息都通過參數(shù)傳遞到該函數(shù)內(nèi)部；函數(shù)輸出到函數(shù)外部的所有信息都通過返回值傳遞到該函數(shù)外部。
隱式（Implicit）的意思是，函數(shù)通過參數(shù)和返回值以外的渠道，和外界進(jìn)行數(shù)據(jù)交換。比如，讀取全局變量，修改全局變量，都叫作以隱式的方式和外界進(jìn)行數(shù)據(jù)交換；比如，利用I/O API（輸入輸出系統(tǒng)函數(shù)庫）讀取配置文件，或者輸出到文件，打印到屏幕，都叫做隱式的方式和外界進(jìn)行數(shù)據(jù)交換。
Pure Function的好處主要有幾點(diǎn)：
以上關(guān)于 pure function 的描述引用這篇博客。
另外一篇博客也介紹函數(shù)的副作用，推薦看看！
在函數(shù)式編程語言里面，函數(shù)是一等公民，這意味著：
- 像其他 value，可以在任何地方定義函數(shù)，包括函數(shù)內(nèi)部
- 像其他 value，函數(shù)可以作為其他函數(shù)的輸入?yún)?shù)或者返回值
- 像其他 value，函數(shù)也有自己的操作符進(jìn)行組合等操作
1.2 參數(shù)調(diào)用的區(qū)別
scala 函數(shù)定義格式如下：
- call by value
遇到表達(dá)式就計(jì)算，scala 函數(shù)參數(shù)默認(rèn)進(jìn)入函數(shù)內(nèi)部之前計(jì)算出 value，再傳進(jìn)內(nèi)部，關(guān)鍵字?val?也是立即計(jì)算模式 - call by name
惰性求值，這是函數(shù)式編程里面一個非常重要的概念。要用到的時候才計(jì)算，可以用def fun(x:Int, y: => Int) = ...?中的?=>顯式調(diào)用。關(guān)鍵字?def?也是這種模式
舉個例子：
def loop: Int = loop // 定義一個死循環(huán)，def 可以，val 不行 def constOne(x: Int, y: => Int) = 1 // 第一個參數(shù)x: call by value, 第二個參數(shù)y: call by name constOne(1+2, loop) // loop一直沒用，所以沒有計(jì)算，輸出1 constOne(loop, 1+2) // 遇到loop立即計(jì)算，陷入死循環(huán)1.3 牛頓法求平方根
- Scala 中遞歸函數(shù)需要寫返回值類型，非遞歸不一定要寫。
- 函數(shù)定義可以放在函數(shù)內(nèi)部，防止命名污染。
牛頓法的基本思路是遞歸，首先猜測為 1.0，如果誤差過大，則猜測值改為 guess 與 x / guess 的平均值。
object session {def abs(x: Double) = if (x>=0) x else (-x) def sqrt(x: Double) = {def sqrtIter(guess: Double): Double =if (isGoodEnough(guess)) guesselse sqrtIter(improve(guess))def isGoodEnough(guess: Double) =abs(guess * guess - x) / x < 0.001def improve(guess: Double) =(guess + x / guess) / 2sqrtIter(1.0)} sqrt(2.0) }1.4 尾遞歸
這篇博客推薦看看——遞歸與尾遞歸總結(jié)。
遞歸相對常用的算法如普通循環(huán)等，運(yùn)行效率較低。在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲，因此遞歸次數(shù)過多容易造成棧溢出。
尾遞歸對應(yīng) imperative program（如c++）中的循環(huán)。?函數(shù)調(diào)用出現(xiàn)在調(diào)用者函數(shù)的尾部, 因?yàn)槭俏膊? 所以根本沒有必要去保存任何局部變量（需要保存的變量可以放在函數(shù)參數(shù)列表里）。它的棧是常數(shù)，可復(fù)用，與循環(huán)一樣高效。
遞歸：
// 階乘函數(shù) def factorial(n: Int): Int =if (n == 0) 1 else n * factotial(n - 1)尾遞歸：
// 階乘函數(shù) def factorial(n: Int) = {def loop(acc: Int, n: Int): Int=if (n == 0) accelse loop(acc * n, n - 1)loop(1, n)} ------------------------------部分二---------------------------------------2. Higher Order Functions
把其他函數(shù)作為參數(shù)或者作為返回值，就是?higher order functions，python 里面也可以看到這樣使用的情形。在酷殼上的博客有一個例子就是將函數(shù)作為返回值。
2.1 匿名函數(shù)
在 python 里邊叫 lambda 函數(shù)，常常與 map(), filter(), reduce() 聯(lián)合使用，前面也寫過一篇這樣的博客。
舉一個 scala 的 reduce 的例子，f: Int => Int?表示 f 是一個整數(shù)映射到整數(shù)的函數(shù)，計(jì)算下面公式：
∑bn=af(n)def sum(f: Int => Int, a: Int, b: Int): Int = {def loop(a: Int, acc: Int): Int =if (a > b) accelse loop(a + 1, f(a) + acc)loop(a, 0) } def sumInts(a: Int, b: Int) = sum(x => x, a, b) // f(n)=n def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b) // f(n)=n*n*n println(sumInts(2, 7)) //求和 println(sumCubes(3, 10)) //求立方和2.2 currying
把一個函數(shù)的多個參數(shù)分解成多個函數(shù)， 然后把函數(shù)多層封裝起來，每層函數(shù)都返回一個函數(shù)去接收下一個參數(shù)這樣，可以簡化函數(shù)的多個參數(shù)。
// sum 返回函數(shù) sumF，風(fēng)格與 python 相似def sum(f: Int => Int): (Int, Int) => Int = {def sumF(a: Int, b:Int): Int =if (a > b) 0 else f(a) + sumF(a + 1, b)sumF} def sumInts = sum(x => x) def sumCubes = sum(x => x * x * x) sumInts(1, 5) //> res0: Int = 15sumCubes(1, 5) //> res1: Int = 225sum(x=>x)(1, 5) //> res2: Int = 15(sum(x=>x))(1, 5) //> res3: Int = 15更為簡短的寫法：
def sum(f: Int => Int)(a: Int, b: Int): Int =if (a > b) 0 else f(a) + sum(f)(a + 1, b)sum(x => x)(1, 5) // 第一個()相當(dāng)于創(chuàng)建了一個匿名函數(shù)mapReduce 實(shí)現(xiàn)過程包括 map 一一映射函數(shù)和 reduce 函數(shù)及單位元素 zero（乘為1，加為0），參數(shù)包括序列區(qū)間 [a, b] 兩個參數(shù)，假設(shè)我們求 [a, b] 區(qū)間上所有元素的平方和：
def mapReduce(map: Int => Int, reduce: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int = if (a > b) zeroelse reduce(map(a), mapReduce(map, reduce, zero)(a + 1, b)) def sumOfSquare(a: Int, b: Int) = mapReduce(x => x*x, (x, y) => x + y, 0)(a, b) //這里確定了三個，留下參數(shù)a，b比如求立方和，四次方和等，更靈活的用法是 map 和 reduce 可以先指定一個reduce（都是sum），使用時再指定另一個（map），代碼就不貼了。總之，所有mapreduce設(shè)置，包括map，reduce, zero, a, b都可以無序設(shè)置，替換組合成包含不同參數(shù)列表的新函數(shù)。
2.3 類
構(gòu)造一個分?jǐn)?shù)（rational）類，實(shí)現(xiàn)加減、比大小等基本功能。
object rationals {val x = new Rational(1, 3) //> x : week3.Rational = 1/3val y = new Rational(5, 7) //> y : week3.Rational = 5/7val z = new Rational(3) //> z : week3.Rational = 3/1x.numer //> res0: Int = 1x.sub(y).sub(z) //> res1: week3.Rational = 71/-21y.add(y) //> res2: week3.Rational = 10/7x.less(y) //> res3: Boolean = truex.max(y) //> res4: week3.Rational = 5/7 }class Rational(x: Int, y: Int) {require(y != 0, "denomitor must be nonzero")// scala 的構(gòu)造函數(shù)就是執(zhí)行bodydef this(x: Int) = this(x, 1) // 第二種構(gòu)造函數(shù), 補(bǔ)全到第一種private def gcd(a: Int, b: Int): Int =if (b==0) a else gcd(b, a % b) //private函數(shù)，求最大公約數(shù)val numer = x / gcd(x, y) // 每次構(gòu)造新類，都化簡val denom = y / gcd(x, y) // val，gcd函數(shù)只計(jì)算一次def add(that: Rational) =new Rational(numer * that.denom + denom * that.numer, // 交叉相乘相加denom * that.denom)def neg: Rational = new Rational(-numer, denom)def sub(that: Rational) = add(that.neg)def less(that: Rational) = numer * that.denom < that.numer * denomdef max(that: Rational) = if (this.less(that)) that else this // this 關(guān)鍵字，表示使用該method的objectoverride def toString = numer + "/" + denom // 每次打印類的格式 }2.4 操作符
c++里面有操作符的重載，在scala里面技術(shù)層面上來說沒有操作符這個概念。比如?1 + 2?實(shí)際是?1.+(2)。 + 是對象 1 的一種方法。Scala 實(shí)現(xiàn)?1 + 2?這種寫法需要兩種技術(shù)，以上面的例子來分析：
實(shí)現(xiàn)與整數(shù)加法風(fēng)格一致的分?jǐn)?shù)運(yùn)算，代碼如下：
package week3object rationals {val x = new Rational(1, 3) //> x : week3.Rational = 1/3val y = new Rational(5, 7) //> y : week3.Rational = 5/7val z = new Rational(3) //> z : week3.Rational = 3/1-x //> res0: week3.Rational = 1/-3x - y - z //> res1: week3.Rational = 71/-21y + y //> res2: week3.Rational = 10/7x < y //> res3: Boolean = truex * x + z * z //> res4: week3.Rational = 82/9 }class Rational(x: Int, y: Int) {require(y != 0, "denomitor must be nonzero")def this(x: Int) = this(x, 1)private def gcd(a: Int, b: Int): Int =if (b==0) a else gcd(b, a % b)val numer = x / gcd(x, y)val denom = y / gcd(x, y)def + (that: Rational) =new Rational(numer * that.denom + denom * that.numer,denom * that.denom)def unary_- : Rational = new Rational(-numer, denom) // unary_：一元運(yùn)算符和二元運(yùn)算符不同，一元要特地指出def - (that: Rational) = this + -thatdef < (that: Rational) = numer * that.denom < that.numer * denomdef * (that: Rational) = new Rational(numer * that.numer, denom * that.denom)override def toString = numer + "/" + denom // 打印類的格式 }注意到上面代碼中?x*x + z*z?沒用括號也能計(jì)算出準(zhǔn)確的結(jié)果，這是因?yàn)?scala 通用一套根據(jù)標(biāo)識符確定運(yùn)算優(yōu)先級的規(guī)則表。
------------------------------部分三---------------------------------------
3. Data and Abstraction
3.1 Class Hierarchies
這一集字幕不同步-,-，聽得有點(diǎn)費(fèi)力！
類的概念和其他語言里面很相似，基類，子類，父類啥的叫法差不多。在 Scala 中，所有用戶自定義的類都是另外一個類的子類，如果沒有顯式給定父類，java 里面默認(rèn)繼承 java.lang，scala 里面是 Object。無論基類中的方法有沒有具體實(shí)現(xiàn)，子類都可以用?override?重新定義，回想起之前強(qiáng)大的?toString?了嗎？
舉一個二叉樹的例子：
package week3object insets {val t1 = new NonEmpty(3, Empty, Empty) //> t1 : week3.NonEmpty = {.3.}val t2 = t1 incl 4 //> t2 : week3.IntSet = {.3{.4.}}val t3 = new NonEmpty(5, Empty, Empty) //> t3 : week3.NonEmpty = {.5.}t2 union t3 //> res0: week3.IntSet = {{{.3.}4.}5.} }abstract class IntSet { // 抽象類作為基類，無法實(shí)例化，定義了三個接口def contains(x: Int): Boolean // 查找是否包含 xdef incl(x: Int): IntSet // 如果 x 不存在，將 x 放入二叉樹中def union(x: IntSet): IntSet // 兩棵樹融合}object Empty extends IntSet { // Empty 是 IntSet 的 subclass，`object` 表示單例模式，所有空節(jié)點(diǎn)都可以用一個對象來表示def contains(x: Int): Boolean = falsedef incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)def union(other: IntSet): IntSet = otheroverride def toString = "." // 空節(jié)點(diǎn)打印"." }class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {def contains(x: Int): Boolean =if (x < elem) left contains xelse if (x > elem) right contains xelse truedef incl(x: Int): IntSet =// 實(shí)際上創(chuàng)建了一個新樹，新樹和舊樹共用未改變的子樹// 這個叫 persistent data structure,是把函數(shù)式編程擴(kuò)展到 collections 的關(guān)鍵之一// 反正他是這么說的 `-,-`if (x < elem) new NonEmpty(elem, left incl x, right) // 一重一重地復(fù)制節(jié)點(diǎn)else if (x > elem) new NonEmpty(elem, left, right incl x)else thisdef union(other: IntSet): IntSet =((left union right) union other) incl elem // override def toString = "{" + left + elem + right + "}" //強(qiáng)大的遞歸啊 }3.2 How Classes Are Organized
沒學(xué)過 java，估計(jì)和 java 中 package 管理一樣。
在源碼最頂端寫上?package week3?表示這個文件的 object 或者 class 屬于這個包。要使用某一個類，可以在源碼中用全名?week3.classA，也可以像 python 一樣在最開始 import，源碼中間用類名：
- import week3.classA：導(dǎo)入類 classA
- import week3.{classA, classB}：導(dǎo)入兩個類
- import week3._ ：導(dǎo)入包所有（通配符導(dǎo)入方法）
除了從包導(dǎo)入，還可以從 object 導(dǎo)入。所有 Scala 程序默認(rèn)導(dǎo)入一些 entities，比如 scala 中的 Int，java.lang 中的 Object，scala.Predef 中的斷言等。更多信息可以查看 scala 的標(biāo)準(zhǔn)庫。
在 java 和 scala 中，一個類只能有一個父類（單繼承），如何實(shí)現(xiàn)多繼承，scala 中采用 traits。trait 像 java 里面的接口，偏抽象，但是更強(qiáng)大，可以包含 field 和具體方法，但是不能有value參數(shù)。子類可只能繼承一個父類，但是可以繼承任意多個 traits，例如：class Square extends Shape with Planar with Moveble。
scala 類型結(jié)構(gòu)如下，實(shí)線表示繼承，虛線表示隱式轉(zhuǎn)化。
- Any是所有類型的基本類，包含的方法有：‘==’，‘!=’，‘equals’，‘hashCode’，‘toString’
- AnyVal是數(shù)值類型的基本類。
- AnyRef是所有引用類型的基本類，也是 java.lang.Object 的別名。
- Nothing是所有類的子類型。主要作用是異常類與collection中的一個空元素。
- Null?是所有類的子類型。但是與 AnyVal 的子類型不兼容。
Q：if (true) 1 else False?的返回類型是什么？
A：int 和 boolean 類型，返回父類 AnyVal。
3.3 Polymorphism
Polymorphism 意味著函數(shù)可以以多種類型出現(xiàn)。一張 PPT 總結(jié) Polymorphism：
假設(shè)我們要建立一個 list 類，它可能包含了不同的數(shù)據(jù)類型（整數(shù)，布爾，list自身類型等），例子如下：
這時需要用泛型來表示。新建一個package叫week4,在其中新建一個 trait。它的兩個‘子類’分別為 Cons 和 Nil，分別表示含有元素的節(jié)點(diǎn)和空節(jié)點(diǎn)。
package week4// [T] 是類型參數(shù)，比如int，double之類。是泛型編程的基礎(chǔ) trait List[T] {def isEmpty: Booleandef head: Tdef tail: List[T] }class Cons[T](val head: T, val tail: List[T]) extends List[T] {def isEmpty = false// head 和 tail 已經(jīng)在初始化中實(shí)現(xiàn) }class Nil[T] extends List[T] {def isEmpty = truedef head: Nothing = throw new NoSuchElementException("Nil.head")// Nothing 是任何類型的子類，所以也是 T 的子類def tail: Nothing = throw new NoSuchElementException("Nil.tail") }在 week4 中新建一個 scala worksheet，測試一下上述代碼：
package week4import week4._object nth {// 創(chuàng)建一個含有一個元素的 listdef singleton[T](elem: T) = new Cons(elem, new Nil)//> singleton: [T](elem: T)week4.Cons[T]singleton[Int](3) //> res0: week4.Cons[Int] = week4.Cons@71be98f5singleton(3) // 編譯器可以從 3 推到出 T 是 Int // 尋找 list 中的第 n 個元素def nth[T](n: Int, xs: List[T]): T =if (xs.isEmpty) throw new IndexOutOfBoundsExceptionelse if (n == 0) xs.headelse nth(n - 1, xs.tail) //> nth: [T](n: Int, xs: week4.List[T])T// 創(chuàng)建一個 list = [1, 2, 3]val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))nth(2, list) //> res2: Int = 3 }小記
這里是課程前四次的大概內(nèi)容，因?yàn)榈谝淮握n是教你怎么安裝，所以實(shí)際內(nèi)容只有三次課，后面還有四次課。總體來說，函數(shù)式編程給人很多啟發(fā)，但是如果不是真正需要用，也不宜占用太多時間去學(xué)習(xí)。暑假要去實(shí)習(xí)了，等下學(xué)期再學(xué)吧。
from：http://www.cnblogs.com/daniel-D/?
總結(jié)
以上是生活随笔為你收集整理的Scala 中的函数式编程基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 机器学习中导数最优化方法(基础篇)
- 下一篇： 支持向量机SVM 简要推导过程