Function Programming in Scala

book notebook : function programming in scala

Basic

函数中定义函数, 尾递归注解

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)
}
factorial(10)

寻找数组中第一次出现的元素的下标

def findFirst(ss: Array[String], key: String): Int = {
    @annotation.tailrec
    def loop(n: Int): Int = {
        if(n >= ss.length) -1       //数组找完一遍都没有找到,表示key不在数组中
        else if(ss(n) == key) n     //在数组中,返回数组下标索引
        else loop(n+1)              //继续找数组的下一个元素
    }
    loop(0)                         //从数组第一个元素开始寻找
}

使用类型参数和高阶函数

def findFirst[A](ss: Array[A], p: A => Boolean): Int = {
    def loop(n: Int): Int = {
        if(n >= ss.length) -1       //数组找完一遍都没有找到,表示key不在数组中
        else if(p(ss(n))) n         //在数组中,返回数组下标索引
        else loop(n+1)              //继续找数组的下一个元素
    }
    loop(0)
}
def eqX(x: String) = x == "a"
findFirst(Array("a","b","c"), eqX)
findFirst(Array("a","b","c"), (x: String) => x == "a")

二分查找的普通版本和多态实现:

def binarySearch(ds: Array[Double], key: Double): Int = {
  def go(low: Int, mid: Int, high: Int): Int = {
    if (low > high) -mid - 1                    //没在这里
    else {
      val mid2 = (low + high) / 2
      val d = ds(mid2) 
      if (d == key) mid2                        //就是你了
      else if (d > key) go(low, mid2, mid2-1)   //右边找找
      else go(mid2 + 1, mid2, high)             //在左边哦
    }
  }
  go(0, 0, ds.length - 1)
}

def binarySearch[A](as: Array[A], key: A, gt: (A,A) => Boolean): Int = {
  def go(low: Int, mid: Int, high: Int): Int = {
    if (low > high) -mid - 1
    else {
      val mid2 = (low + high) / 2
      val a = as(mid2)
      val greater = gt(a, key)
      if (!greater && !gt(key,a)) mid2
      else if (greater) go(low, mid2, mid2-1)
      else go(mid2 + 1, mid2, high)
    }
  }
  go(0, 0, as.length - 1)
}

exercise2.2,判断数组是否根据某个条件有序

def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = {
    //as.reduce(ordered(_, _))
    def loop(n: Int): Boolean = {
        if(n >= as.length - 1) true
        else if(n == as.length - 2) ordered(as(n), as(n+1))
        else if(ordered(as(n), as(n+1)) == false) false
        else loop(n+1)
    }
    loop(0)
}
def myOrder(x: Int, y: Int) = x <= y
isSorted(Array(1,2,3,4,5), myOrder)

函数式数据结构

sealed trait List[+A]                                       //trait表示一种数据类型,可以有members
case object Nil extends List[Nothing]                       //构造一个空的List
case class Cons[+A](head: A, tail: List[A]) extends List[A] //非空List

object List {
  def sum(ints: List[Int]): Int = ints match { 
    case Nil => 0                           //空的List的和是0
    case Cons(x,xs) => x + sum(xs)          //非空List的和是第一个元素和后面的List的和,递归调用
  }
  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)
  }
  def apply[A](as: A*): List[A] =           //可变参数
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))  //将as List拆分成单一的head和tail List, tail继续递归调用apply
}

val example = Cons(1, Cons(2, Cons(3, Nil)))  //构造List的方式 
val example2 = List(1,2,3)                    //这种方式会调用apply
val total = sum(example)

把子表达式概括为函数作为参数: 如果子表达式引用了任何局部变量,那么就将子表达式转化为接收这些变量作为参数的函数
sum和product不同的处理逻辑在子表达式中: x + sum(xs), x * product(xs), 可以把+和*抽象为一个函数f
A是List中元素的类型, B是初始值. x是List l的第一个元素,所以也是类型A, 满足f: (A,B)中的A.
foldRight的第一个参数l是List, 而xs是除了head外的List, 所以可以递归调用
由于foldRight有两个参数组, 第二个参数组是一个函数. 这个函数不仅作为子表达式的函数,也要作为递归调用的函数.
所以完整的子表达式不仅要在当前调用f, 也要将f传递给下一次的递归调用: f(x, foldRight(xs, z)(f))

def foldRight[A,B](l: List[A], z: B)(f: (A, B) => B): B = 
  l match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

def sum2(l: List[Int]) = foldRight(l, 0.0)(_ + _)
def product2(l: List[Double]) = foldRight(l, 1.0)(_ * _)

foldRight(Cons(a, Nil), z)(f) = f(a, z)
foldRight(Cons(a, Cons(b, Nil)), z)(f) = f(a, f(b, z))

(_ + _)是一个求和的函数, f(a, b) = a + b
所以下面第一次的计算结果是1和右边的Cons运用求和函数.右边的Cons继续递归求和…

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)(_ + _)
1 + foldRight(Cons(2, Cons(3, Nil)), 0)(_ + _)
1 + (2 + foldRight(Cons(3, Nil), 0)(_ + _))
1 + (2 + (3 + (foldRight(Nil, 0)(_ + _))))
1 + (2 + (3 + (0)))
6

Option

import java.util.regex._

//pattern返回Pattern的Option包装, 可以看做是只有一个Pattern的List, 所以可以用map或者for循环来访问其中的元素
def pattern(s: String): Option[Pattern] =
  try {
    Some(Pattern.compile(s))
  } catch {
    case e: PatternSyntaxException => None
  }

//map访问Option[Pattern], p表示List的每个元素,因为Option[Pattern]只有一个Pattern的List, 所以p也能表示Pattern
def mkMatcher(pat: String): Option[String => Boolean] =
  //这里的s是客户端传递的字符串, 要判断是否匹配Pattern模式
  pattern(pat) map (p => (s: String) => p.matcher(s).matches)

//for循环访问Option[Pattern], 和map访问一样
def mkMatcher_1(pat: String): Option[String => Boolean] =
  for (p <- pattern(pat)) yield ((s: String) => p.matcher(s).matches)

//最终还是要提供一个字符串. 即判断字符串s是否符合模式pat 
def doesMatch(pat: String, s: String): Option[Boolean] =
  for (p <- mkMatcher_1(pat)) yield p(s)  

//一个字符串匹配两种模式
def bothMatch(pat: String, pat2: String, s: String): Option[Boolean] =  
  for {
    f <- mkMatcher(pat)
    g <- mkMatcher(pat2)
  } yield f(s) && g(s)

//使用map和flatMap方式实现匹配两个模式, 与for相比,需要嵌套,看起来比较复杂. 实际上for也是双层循环
def bothMatch_1(pat: String, pat2: String, s: String): Option[Boolean] =
  mkMatcher(pat) flatMap (
    f => mkMatcher(pat2) map (
      g => f(s) && g(s)
    )
  )