速记表

函数

高阶函数

部分应用函数

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

柯里化与反柯里化

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

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

反柯里化：

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

组合函数

组合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。

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

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

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

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

函数式数据结构

常用高阶函数

折叠操作

def foldRight2[A, B](l: List[A], z: B)(f: (A, B) => B): B = l match {
	case Nil => z
	case Cons(x, xs) => f(x, foldRight2(xs, z)(f)) // 无法尾递归优化
}

@annotation.tailrec // 尾递归优化
def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match {
	case Nil => z
	case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
}

// 通过`foldLeft`来实现`foldRight`
def foldRight1[A, B](l: List[A], z: B)(f: (A, B) => B): B =
	foldLeft(reverse(l), z)((b, a) => f(a, b))

// 通过`foldLeft`来实现`foldRight`
def foldRight[A, B](l: List[A], z: B)(f: (A, B) => B): B =
	foldLeft(l, (b: B) => b)((g, a) => b => g(f(a, b)))(z)

// 通过`foldRight`来实现`foldLeft`
def foldLeft2[A, B](l: List[A], z: B)(f: (B, A) => B): B =
	foldRight(l, (b: B) => b)((a, g) => b => g(f(b, a)))(z)

映身操作

// 列表中的每个元素值加1
def add1(l: List[Int]): List[Int] =
	foldRight(l, Nil: List[Int])((h, t) => Cons(h + 1, t))

// 列表中double转为字符串
def doubleToString(l: List[Double]): List[String] =
	foldRight(l, Nil: List[String])((h, t) => Cons(h.toString, t))

def map[A, B](l: List[A])(f: A => B): List[B] =
	foldRight(l, Nil: List[B])((h, t) => Cons(f(h), t))

def map_2[A, B](l: List[A])(f: A => B): List[B] = {
	val buf = new collection.mutable.ListBuffer[B]
	def go(l: List[A]): Unit = l match {
		case Nil => ()
		case Cons(h, t) => buf += f(h); go(t)
	}
	go(l)
	List(buf.toList: _*) // 从Scala内部的List转为我们自己实现的List
}

过滤操作

def filter[A](l: List[A])(f: A => Boolean): List[A] =
	foldRight(l, Nil: List[A])((h, t) => if (f(h)) Cons(h, t) else t)

def filter_1[A](l: List[A])(f: A => Boolean): List[A] =
	foldRightViaFoldLeft(l, Nil: List[A])((h, t) => if (f(h)) Cons(h, t) else t)

def filter_2[A](l: List[A])(f: A => Boolean): List[A] = {
	val buf = new collection.mutable.ListBuffer[A]
	def go(l: List[A]): Unit = l match {
		case Nil => ()
		case Cons(h, t) => if (f(h)) buf += h; go(t)
	}
	go(l)
	List(buf.toList: _*) // 从Scala内部的List转为我们自己实现的List
}

flatMap

flatMap与映射很像，区别是函数f返回的是列表而不是单个结果

def flatMap[A, B](l: List[A])(f: A => List[B]): List[B] =
	concat(map(l)(f))

调用：

flatMap(List(1, 2, 3))(i => List(i, i))
// > List(1, 1, 2, 2, 3, 3)

用flatMap实现Filter

def filterViaFlatMap[A](l: List[A])(f: A => Boolean): List[A] =
	flatMap(l)(a => if (f(a)) List(a) else Nil)

zip操作

把两个列表按索引相同的值加加起来，形成一个新的列表：

def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a, b) match {
	case (Nil, _) => Nil
	case (_, Nil) => Nil
	case (Cons(h1, t1), Cons(h2, t2)) => Cons(h1 + h2, addPairwise(t1, t2))
}

addPairwise(List(1, 2, 3), List(4, 5, 6))
// > List(5, 7, 9)

def zipWith[A, B, C](a: List[A], b: List[B])(f: (A, B) => C): List[C] = (a, b) match {
	case (Nil, _) => Nil
	case (_, Nil) => Nil
	case (Cons(h1, t1), Cons(h2, t2)) => Cons(f(h1, h2), zipWith(t1, t2)(f))
}

Option

seald trait Option[+A] {

	def map[B](f: A => B): Option[B] = this match {
	  case None => None
	  case Some(a) => Some(f(a))
	}

	def flatMap[B](f: A => Option[B]): Option[B] =
	  map(f) getOrElse None


	// Of course, we can also implement `flatMap` 
	// with explicit pattern matching.
	def flatMap_1[B](f: A => Option[B]): Option[B] = this match {
	  case None => None
	  case Some(a) => f(a)
	}

}

提升参数与返回值为Option

返回一个新的函数作为返回值，这个新函数以Option[A]为参数， 这样Option[A].map(f)的返回值类型就是Option[B]：

def lift2[A, B](f: A => B): Option[A] => Option[B] = {
	val newFunction = (t: Option[A]) => { t map f }
	newFunction
}                         //> lift2: [A, B](f: A => B)Option[A] => Option[B]

简写一下：

def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f
                          //> lift: [A, B](f: A => B)Option[A] => Option[B]

例子：

val absO = lift(math.abs) //> absO  : Option[Int] => Option[Int] 

因为提升非常常见，所以scala自带的for推导已经自带提升效果：

def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
	a flatMap (aa => 
			b map (bb => 
				f(aa, bb)))

任何的map与flatMap操作都可以替换为for推导：

def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
	for {
		aa <- a
		bb <- b
	} yield f(aa, bb)

yield关键字可以使用<-符号左边绑定的值，编译器会把这些绑定操作的语法糖 转换为map调用。

合并多个Option为单个Option的列表

sequence函数把含有多个Option的列表List[Option[A]]结合为一个Option[List[A]] 如果原来的列表里有一个为None，那么sequence函数返回的结果也是None：

def sequence[A](lst: List[Option[A]]): Option[List[A]] = lst match {
	case Nil => Some(Nil)
	case h :: t => h flatMap (hh => sequence(t) map (hh :: _))
}     
//> sequence: [A](lst: List[Option[A]])Option[List[A]]

//还可以通过 `foldRight` 和 `map2`来实现`sequence` ，
//在`foldRight`里要注明类型为`[Option[List[A]]]`
//不然会被类型推导错误地推导为`Some[Nil.type]`
def sequence_1[A](a: List[Option[A]]): Option[List[A]] =
	a.foldRight[Option[List[A]]](Some(Nil))((x, y) => map2(x, y)(_ :: _))
//> sequence_1: [A](a: List[Option[A]])Option[List[A]]

//`sequence`仅仅只适合用来合并列表为单个option，如果涉及到map操作，就要遍历两次，
//例如下面的字符串转整数，map的时候遍历一遍`lst`，合并Option时又要遍历一遍：

def parseInts(lst: List[String]): Option[List[Int]] = 
		sequence(lst map (i => Try(i.toInt)))

定义新的工具traverse直接在一个遍历过程中map并合并Option：

def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match {
		case Nil => Some(Nil)
		case h :: t => map2(f(h), traverse(t)(f))(_ :: _)
}                                 
//> traverse: [A, B](a: List[A])(f: A => Option[B])Option[List[B]]

def traverse_1[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = {
	a.foldRight[Option[List[B]]](Some(Nil))((h, t) => map2(f(h), t)(_ :: _))
}
//> traverse_1: [A, B](a: List[A])(f: A => Option[B])Option[List[B]]

def sequenceViaTraverse[A](a: List[Option[A]]): Option[List[A]] = {
	traverse(a)(x => x)               
}
//> sequenceViaTraverse: [A](a: List[Option[A]])Option[List[A]]

Either

sealed trait Either[+E, +A] {

	def map[B](f: A => B): Either[E, B] = this match {
			case Right(a) => Right(f(a))
			case Left(e) => Left(e)
		}

	// 对Right进行映射时，必须把Left的类型提升为父类型以满足`E+`的型变
	def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] =
		this match {
			case Right(a) => f(a)
			case Left(e) => Left(e)
		}
		
	// 对Right进行映射时，必须把Left的类型提升为父类型以满足`E+`的型变
	def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] =
		this match {
			case Right(a) => Right(a)
			case Left(_) => b
		}
		
	def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = 
		for { a <- this; b1 <- b } yield f(a, b1)
	
}

非严格求值

实现非严格求值

手动实现非严格示值的方式是把函数作为参数传进去，只有符合条件时才对函数示值。 比如下面的例子就是把需要非严格示值的参数以一个没有参数的函数字面量的形式作为参数 ：

def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A = {
	if (cond) onTrue() else onFalse() 
}
         //> if2: [A](cond: Boolean, onTrue: () => A, onFalse: () => A)A

if2(true, () => println("a"), () => println("b"))                  //> a

可以发现Scala自带的语法用=> A作为语法糖，不用手动写为无参数的函数字面量， 也不用在用到时求值：

def if3[A](cond: Boolean, onTrue: => A, onFalse: => A): A = {
	if (cond) onTrue else onFalse
}
                //> if3: [A](cond: Boolean, onTrue: => A, onFalse: => A)A

if3(true, println("a"), println("b"))                              //> a

非严格求值与流的应用

实现一个惰性的Stream：

import Stream._    // 隐藏scala版本的steam实现

trait Stream[+A] { /* ... */ }

case object Empty extends Stream[Nothing]

// 惰性流的head和tail都是非严格求值的thunk
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

缓存Stream中的元素

缓存Stream中的元素，避免重复计算。

object Stream {

	def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
		lazy val head = hd // 缓存head
		lazy val tail = tl // 缓存tail
		Cons(() => head, () => tail)
	}

	def empty[A]: Stream[A] = Empty

	def apply[A](as: A*): Stream[A] =
		if (as.isEmpty) empty
		else cons(as.head, apply(as.tail: _*))
}

Scala负责包装thunk中传给cons()的参数，所以as.head和apply(as.tail: _*) 这两个表达式在被Steam中强制求值之前不会被求值。

惰情求值流的常用工具函数

把Steam转为列表的toList：

trait Stream[+A] {

	// 有缺陷的版本，会爆栈
	def toListRecursive: List[A] = this match {
		case Cons(h, t) => h() :: t().toListRecursive
		case _ => List()
	}

	/* 尾递归优化 */
	def toList: List[A] = {
		@annotation.tailrec
		def go(s: Stream[A], acc: List[A]): List[A] = s match {
			case Cons(h, t) => go(t(), h() :: acc)
			case _ => acc
		}
		go(this, List()).reverse
	}

	/* 内部用可变类型存储，不会影响外部调用时的函数式风格。 */
	def toListFast: List[A] = {
		val buf = new collection.mutable.ListBuffer[A]
		@annotation.tailrec
		def go(s: Stream[A]): List[A] = s match {
			case Cons(h, t) =>
				buf += h()
				go(t())
			case _ => buf.toList
		}
		go(this)
	}

    // `take(n)`取得前`n`个元素，`drop(n)`得到`n+1`开始的所有元素：
	/* 当`n<1`时返回空 */
	def take(n: Int): Stream[A] = this match {
		case Cons(h, t) if n > 1  => cons(h(), t().take(n - 1))
		case Cons(h, _) if n == 1 => cons(h(), empty)
		case _ => empty
	}

	/* */
	@annotation.tailrec
	final def drop(n: Int): Stream[A] = this match {
		case Cons(_, t) if n > 0 => t().drop(n - 1)
		case _ => this
	}

	// `takeWhile(f: A => boolean)`返回开头连续符合条件的元素：
	/* `t() takeWhile f`是函数语法糖，相当于：`t().takeWhile(f)`  */
	def takeWhile(f: A => Boolean): Stream[A] = this match {
		case Cons(h, t) if f(h()) => cons(h(), t() takeWhile f)
		case _ => empty
	}

}