Jade Dungeon

Scala函数式编程

纯函数

副作用

「副作用」（side effect）是指对相关环境产生的改变： 

val s  = "hello, world"               //> s  : String = hello, world
val s1 = s.reverse                    //> s1 : String = dlrow ,olleh
val s2 = s.reverse                    //> s2 : String = dlrow ,olleh

val x  = new StringBuilder("hello")   //> x  : StringBuilder = hello
val r1 = x.append(", world").toString //> r1 : String = hello, world
val r2 = x.append(", world").toString //> r2 : String = hello, world, world

引用透明

可以使用「引用透明」（referential transparency）的概念对纯函数进行形式化：

  • 2 + 3是一个表达式。
  • 2和3也可以视为表达式。
  • 2 + 3的值只会是5，而且没有副作用，所以可以用5替换掉程序中所有的2 + 3。

所有程序中所有符合引用透明的表达式都可以由它的结果来取代， 而不改变程序的含意。当调用一个函数时所传入的参数是引用透明的， 并且函数的调用也是引用引用透明的，那么这个函数就是一个纯函数。

有副作用的例子，不是引用透明： 

// 信用卡 id 信用卡的卡号
class CreditCard(val id: String)

// 咖啡 price 咖啡的价格
class Coffee(val price: Double)

def buyCoffee(cc: creditCard): Coffee = {
	val cup = new Coffee(5.5)
	cc.sentChargeInfo(cup.price) // 发送消费记录给信用卡公司，有副作用
	cup
}

既然付费操作是副作用，那么就把它放到其它的地方。 在当前的函数中只记录下消费的金额。没有副作用，是引用透明的： 

// 买咖啡 cc 信用卡 return (咖啡,信用卡消费记录)
def byCoffee(cc: CreditCard): (Coffee, Charge) = {
	val cup = new Coffee(5.5)
	val charge = Charge(cc, cup.price)
	(cup, charge)
}

消费记录可以单独抽象出来，还有一个好处，就是同一张信用卡的消费金额还可以加起来： 

// 消费记录，指定一张信用卡与这张信用卡消息的金额
// param  cc 信用卡 param  amount 金额
case class Charge(val cc: CreditCard, val amount: Double) {

	// 同一张信用卡的金额加起来 
	def combine(other: Charge): Charge = {
		if (cc == other.cc)
			Charge(cc, amount + other.amount)
		else // 不同信用卡上的消息不能合并
			throw new Exception("Not same Credit Card")
	}

}

有了合并金额功能，可以不带副作用地买多杯咖啡： 

// param cc 信用卡 param count 要买的咖啡的数量 
// return (多杯咖啡列表,信用卡消费金额)
def byCoffees(cc: CreditCard, count: Int): (List[Coffee], Charge) = {
	val puschases: List[(Coffee, Charge)] = List.fill(count)(byCoffee(cc))
	val (coffees, charges) = puschases.unzip // 咖啡与金额分成两个列表 
	(coffees, charges.reduce((c1, c2) => c1.combine(c2)))
}

多个信用卡消费还可以按每张卡汇总到一起： 

def coalsece(charges: List[Charge]): List[Charge] = {
	charges.groupBy(_.cc).values.map(_.reduce(_ combine _)).toList
}

// 上面的相当于：

def coalsece2(charges: List[Charge]): List[Charge] = {
	// 按卡号相同分组
	val chargeGroup: Map[CreditCard, List[Charge]] = charges.groupBy(_.cc)
	// 同一组内把金额加起来
	val chargeListGrp: Iterable[Charge] = chargeGroup.values.map(
			                                             _.reduce(_ combine _))
	// 把集合容器转为列表
	chargeListGrp.toList
}

代换模型

引用透明要求函数的任何操作都可以用它的返回值（value）代替， 这种形式称为「代换模型」（subsitution model）。 所以引用透明使得程序具备了「等式推理」（equational reasoning）能力。

代换模型因为没有副作用，所以只要进行局部的推理就可以得到结果， 不用跟踪函数执行过程中其他局部状态或是全局状态的变化。

高阶函数

函数也是值，可以像变量一样赋值、存储在数据结构中、或是作为参数传递给另一个函数。

把函数作为参数传递给别一个函数，被称为「高阶函数」（higher-order function， 缩写为HOF）。 

def abs(n: Int): Int = if (n < 0) -n else n
                         //> abs: (n: Int)Int

def formatFunc(x: Int, func: Int => Int) = {
	val msg = "The absolute value of %d is %d"
	msg.format(x, func(x))
}                        //> formatFunc: (x: Int, func: Int => Int)String

formatFunc(-5, abs)      //> res0: String = The absolute value of -5 is 5

一般函数参数都用func、func1、func2或是f、g、h等命名， 因为只确定函数参数类型和返回值类型，具体逻辑是末定的，所以不用特别描述。

高阶函数的缺点：

高阶函数把函数作为参数，这在很多情况很难用参数名来描述作为参数的函数的功能与特性 。所以在找不到能恰当描述的参数名字的时候就干脆用比较短的参数名， 这样至少看起来比较整齐。

尾递归优化

递归调用发生于最后一个操作时，可以进行优化为循环： 

def factorial(n: Int): Int = {
	@annotation.tailrec // 注释强制对尾递归调用进行优化
	def go(n: Int, acc: Int): Int = {
		if (n <= 0) acc else go(n - 1, n * acc)
	}
	go(n, 1)
}

多态函数：函数的泛型

单态（monomorphic）函数的例子，查找数组中的第一个符合的元素，元素的类型待定： 

def findFirst[A](as: Array[A], p: A => Boolean): Int = {
	@annotation.tailrec
	def loop(n: Int): Int = {
		if (n >= as.length) -1
		else if (p(as(n))) n
		else loop(n + 1)
	}
	loop(0)
}

部分应用函数

部分应用函数（partial application）也叫偏函数： 

def partialFunction[A, B, C](a: A, f: (A, B) => C): B => C =
		(b: B) => f(a, b)

帮助理解： 

def partialFunction[A, B, C](a: A, f: (A, B) => C): B => C = {

	def func2(b: B): C = { // 包装成新的函数，缺少的参数`b`
		f(a, b)              // 已经有的参数`a`
	}

	func2
}

应用： 

def f002(a: Int, b: Double): String = {
	s"${a}-${b}"
}                              //> f002: (a: Int, b: Double)String

f002(3, 0.2)                   //> res0: String = 3-0.2

// 部分应用函数返回的结果是一个函数
def f003 = partialFunction(3, f002) //> f003: => Double => String

val v3 = f003(0.2)             //> v3  : String = 3-0.2

柯里化与反柯里化

柯里化（currying）把带有两个参数的函数func(a:A, b:B): C 转换为只有一个一个参数的偏应用函数partialFunc(a: A): B => C：

注意A => B => C按Scala语法来说相当于A => (B => C)： 

def curry[A, B, C](f: (A, B) => C): A => (B => C) = {
	(a: A) => {
		(b: B) => {
			f(a, b)
		}
	}
}

简写为： 

def curry[A, B, C](f: (A, B) => C): A => B => C =
	a => b => f(a, b)

反柯里化： 

def uncurry[A, B, C](f: A => B => C): (A, B) => C =
	(a, b) => f(a)(b)

应用： 

def f002(a: Int, b: Double): String = {
	s"${a}-${b}"
}                          //> f002: (a: Int, b: Double)String

// 测试柯里化
val f005 = curry(f002)     //> f005  : Int => (Double => String)
val f006 = f005(3)         //> f006  : Double => String 
val f007 = f006(0.2)       //> f007  : String = 3-0.2

// 测试反柯里化
val f008 = uncurry(f005)   //> f008  : (Int, Double) => String
val v7 = f008(3, 0.2)      //> v7  : String = 3-0.2

组合函数

组合compose(f, g)相当于f(g())： 

def compose[A, B, C](f: B => C, g: A => B): A => C =
	a => f(g(a))

Scala为只有一个参数的函数提供了现在的抽象Function1， 它自带compose()方法，compose(f,g)可以表现为f.compose(g)并简写为 f compose g。

功能类似的还有andThan()函数。f andThan g等价于g compose f。 

def andThen[A, B, C](g: A => B, f: B => C): A => C =
	a => g(f(a))

通过部分应用函数强化类型推导

@annotation.tailrec
def foldLeft[A, B](l: List[A], z: B, f: (B, A) => B): B = l match {
	case Nil => z
	case Cons(h, t) => foldLeft(t, f(z, h), f)
}
//> foldLeft: [A, B](l: List[A], z: B, f: (B, A) => B)B

foldLeft(List(1, 2, 3), "", (a: String, b: Int) => { b + ("" + a) })
//> res0: String = 321

通过柯里化把参数列表拆分成两个偏函数，scala编译器可以通过传入的第一个参数列表 的实参List(1, 2, 3), ""推导出[A, B]是[Int, String]，这样第二个参数f 的类型就一定是f:(String, Int) => String。不用手动指定了： 

@annotation.tailrec
def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match {
	case Nil => z
	case Cons(h, t) => foldLeft(t, f(z, h))(f)
}
//> foldLeft: [A, B](l: List[A], z: B)(f: (B, A) => B)B

foldLeft(List(1, 2, 3), "")((a, b) => { b + ("" + a) })
//> res0: String = 321
© 2015 jade-dungeon.net. Valid CSS & XHTML
Website template by Arcsin