Scala 函数式编程 https://github.com/fpinscala/fpinscala](https://github.com/fpinscala/fpinscala)

函数式数据结构:

• 只能被纯函数操作?
• 不可变, 操作只会产生新对象, 不会改变原对象
• 不是用复制实现

单向列表(原理像标准库中的List)

以下都定义在 文件 List.scala 里面

sealed trait List[+A]
case object Nil extends List[Nothing] 
case class Cons[+A](head: A, tail: List[A]) extends List[A]

通常用trait引入数据类型, sealed表示不可在其他地方再实现List, 只能就这2个实现, 这2种形式

• Nil 空列表, 就这么一个单例对象, 注意它继承 List[Nothing] 是所有列表的子类, 所以所有list都可以用
• Cons 类, 由第一个元素 head 和 后续 名为tail的 List 组成 构造器入参是 (head: A, tail: List[A])

以下 object List 是List class的伴生对象, 相当于java里的工具类

object List {
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0 
    case Cons(x,xs) => x + sum(xs) // 递归
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.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: _*))
    }
  }//apply end
//....

// 去掉满足f的前缀
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] ={
    l match {
      case Cons(h,t) if f(h) => dropWhile(t, f)
      case _ => l
    }
  }
}

apply 函数 使List 可以List(1,4,5) 这样来方便地构造
(as: A*)这样的可变参数, 是一个语法糖, 其实内部是 Seq[A]

参数分组 帮助类型推导

如上的dropWhile函数

  val xs:List[Int]=List(1,23,34,0)
  val exl=dropWhile(xs,x=>x<4)

这样调用会红, 必须x:Int=>x<4 这样声明类型,因为scala不能推导x的类型是Int,
(l: List[A], f: A => Boolean) 改成
(l: List[A])( f: A => Boolean) 这样参数分组, 就可以帮助类型推导了

fold

这2个函数,

  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0 
    case Cons(x,xs) => x + sum(xs) // 不同
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(x,xs) => x * product(xs)// 不同
  }

其实只有子表达式不用,可以泛化

// 抽出来公共部分
  /**
    * 
    * @param as 原列表
    * @param z 积累的第一个值
    * @param f 
    * @tparam A 列表元素类型
    * @tparam B 返回值类型
    * @return 一个值
    */
  def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = // Utility functions
    as match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))// 递归
    }

  def sum(ns: List[Int]) = foldRight(ns, 0)((x,y) => x + y)

  def product(ns: List[Double]) =  foldRight(ns, 1.0)(_ * _)

注意抽出来的函数的foldRight 的返回值类是B ,list的元素类型是'A', 不一定要有关系

ADT

代数 数据类型

This is a type where we specify the shape of each of the elements. Wikipedia has a thorough discussion. "Algebraic" refers to the property that an Algebraic Data Type is created by "algebraic" operations. The "algebra" here is "sums" and "products":

• "sum" is alternation (A | B, meaning A or B but not both)
• "product" is combination (A B, meaning A and B together)
  Sums and products can be repeatedly combined into an arbitrarily large structures.

除了之前的 单向列表List 外, 还有树 Tree

sealed trait Tree[+A]

case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]sealed trait Tree[+A]

Branch就是 Leaf累加而来

List 常用方法
https://www.runoob.com/scala/scala-lists.html