函数式数据结构（1）

函数式数据结构只能被纯函数操作，纯函数一定不能修改原始数据结构或者产生副作用。
函数式数据结构被定义为不可变的。
模式匹配有点像一个别致的switch声明，它可以侵入到表达式的数据结构内部，对这个结构进行检验和提取子表达式。
单向链表：

sealed trait List[+A]

case object Nil extends List[Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def apply[A](as: A*): List[A] =
    if(as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))
}

练习 3.1
求下面模式匹配的结果是什么？
分析：分析列表匹配表达式3和4，但是匹配了3之后直接求值不会再匹配4，结果为1 + 2 = 3

  def sum(li: List[Int): Int = li match {
    case Nil => 0
    case Cons(h, t) => h + sum(t)  
  }
  
  val x = List(1, 2, 3, 4, 5) match {
    case Cons(x, Cons(2, Cons(4, _))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + sum(t)
    case _ => 101  
  }

练习 3.2
实现tail函数，删除一个List的第一个元素。
分析：利用模式匹配提取列表的第一个元数据和子列表，然后返回子列表。

   def tail[A](li: List[A]): List[A] = li match {
    case Nil => Nil
    case Cons(h, t) => t  
  }

练习 3.3
实现函数setHead用一个不同的值代替列表中的第一个元素。
分析：利用模式匹配提取第一个元素和子列表，用新的值和子列表组成一个新的列表并返回。

  def setHead[A](li: List[A], a: A): List[A] = li match {
    case Nil => Nil
    case Cons(h, t) => Cons(a, t)  
  }

练习 3.4
实现函数drop用于从列表中删除前n个元素。
分析：利用模式匹配提取列表头部和尾部；利用递归完成元素的删除。

  def drop[A](li: List[A], n: Int): List[A] = n match {
    case m if m <= 0 => li
    case _ => li match {
      case Nil => Nil
      case Cons(h, t) => drop(t, n - 1)
    }
  }

练习 3.5
实现dropWhile函数，删除列表中前缀全部符合判定的元素。
分析：利用模式匹配提取列表的头部元素和尾部列表，对头部元素进行判断，满足条件剔除元素；利用递归不断提取子列表的头部元素和其子元素完成列表的遍历。

  def dropWhile[A](li: List[A], f: A => Boolean): List[A] = li match {
    case Nil => Nil
    case Cons(h, t) =>
      if (f(h)) dropWhile(t, f)
      else Cons(h, dropWhile(t, f))
  }

练习 3.6
实现init函数，返回一个列表，它包含原列表除最后一个元素之外的所有的元素。
分析：init函数实现困难些，递归的取列表的中的头元素，将取出的头元素组成新的列表，取到倒数第二个元素后，返回组成的新的列表。使用length函数获取列表的长度；使用append函数拼接列表以组成新的列表。

  def length[A](li: List[A]): Int = {
    def loop(li: List[A], acc: Int): Int = li match {
      case Nil => acc
      case Cons(_, t) => loop(t, acc + 1)
    }
    loop(li, 0)
  }

  def append[A](l1: List[A], l2: List[A]): List[A] = l1 match {
    case Nil => l2
    case Cons(h, t) => Cons(h, append(t, l2))
  }

  def init[A](li: List[A]): List[A] = {
    def loop(n: Int, li: List[A], res: List[A]): List[A] = n match {
      case m if m <= 1 => res
      case _ => li match {
        case Nil => Nil
        case Cons(h, t) => loop(n - 1, t, append(res, List(h)))
      }
    }
    loop(length(li), li, Nil)
  }

练习 3.7

  def foldRight[A, B](li: List[A], b: B)(f: (A, B) => B): B = li match {
    case Nil => b
    case Cons(h, t) => f(h, foldRight(t, b)(f))  
  }
  
  def product(li: List[Double]): Double =
    foldRight(li, 1.0)(_ * _)

1. 在入参是0.0时调用foldRight实现的product是否可以立即停止递归并返回0.0？为什么不可以或者为什么可以？
   分析：可以，foldRight是右折叠
2. 对一个大的列表调用foldRight的时候会有什么问题发生？
   分析：性能问题，使用惰性列表来避免

练习 3.8
foldRight和List之间的关系，你有什么想法？
分析：foldRight以递归的方式遍历List的每个元素，并将所有的元素进行聚合。

练习 3.9
使用foldRight实现计算List的长度。

  def length1[A](li: List[A]): Int =
    foldRight(li, 0){(_, b) =>
      b + 1
    }

练习 3.10
使用尾递归实现foldLeft

   def foldLeft[A, B](li: List[A], b: B)(f: (B, A) => B): B = li match {
    case Nil => b
    case Cons(h, t) => foldLeft(t, f(b, h))(f)
  }

练习 3.11
写下sum和product函数，和一个用foldLeft计算列表长度的函数

   def sum1(li: List[Int]): Int =
    foldLeft(li, 0)(_ + _)

  def product1(li: List[Double]): Double =
    foldLeft(li, 1.0)(_ * _)

  def length2[A](li: List[A]) =
    foldLeft(li, 0){(b, _) =>
      b + 1
    }

练习 3.12
写一个对原列表元素颠倒顺序的函数，看下是否可以用折叠实现。

  def reverse[A](li: List[A]): List[A] =
    foldLeft(li, Nil: List[A]){(b, a) =>
      Cons(a, b)
    }

练习 3.13
能否根据foldRight来实现foldLeft ？

  def foldLeft1[A, B](li: List[A], b: B)(f: (B, A) => B): B =
    foldRight(li, b){(a, b) =>
      f(b, a)
    }

练习 3.14
根据foldLeft或者foldRight实现append函数。

  def append1[A](l1: List[A], l2: List[A]): List[A] =
    foldLeft(l2, l1){(b, a) =>
      Cons(a, b)
    }

练习 3.15
写一个函数将一组列表连接成一个单个列表

  def union[A](li: List[List[A]]): List[A] =
    foldLeft(li, Nil: List[A]){(b, a) =>
      append(b, a)
    }

练习 3.16

  def ++(li: List[Int]): List[Int] = li match {
    case Nil => Nil
    case Cons(h, t) => Cons(h + 1, ++(t))  
  }

练习 3.17
写一个函数，将List[Double]中的每个值转化成String

  def toString(li: List[Double]): List[String] =
    foldLeft(li, Nil: List[String]){(b, a) =>
      Cons(a.toString, b)
    }

练习 3.18
写一个泛化的map函数，对列表中每一个元素进行修改，并维持列表的结构。

 def map[A, B](li: List[A])(f: A => B): List[B] = li match {
   case Nil => Nil
   case Cons(h, t) => Cons(f(h), map(t)(f))
 }
 
 def map1[A, B](li: List[A])(f: A => B): List[B] =
   foldLeft(li, Nil: List[B]){(b, a) =>
     Cons(f(a), b)
   }

练习 3.19
写一个泛化的filter函数，从列表中删除所有不满足条件的元素。

  def filter[A](li: List[A])(f: A => Boolean): List[A] = li match {
    case Nil => Nil
    case Cons(h, t) =>
      if (f(h)) Cons(h, filter(t)(f))
      else filter(t)(f)
  }

  def filter1[A](li: List[A])(f: A => Boolean): List[A] =
    foldLeft(li, Nil: List[A]){(b, a) =>
      if (f(a)) Cons(a, b)
      else b
    }

练习3.20

  def flatMap[A, B](li: List[A])(f: A => List[B]): List[B] = li match {
    case Nil => Nil
    case Cons(h, t) => append(f(h), flatMap(t)(f))
  }

  def flatMap1[A, B](li: List[A])(f: A => List[B]): List[B] =
    foldLeft(li, Nil: List[B]){(b, a) =>
      append(b, f(a))
    }

练习 3.21
用flatMap实现filter。

  def filter1[A](li: List[A])(f: A => Boolean): List[A] =
    flatMap(li){a =>
      if (f(a)) List(a)
      else Nil
    }

练习 3.22
写一个函数，接受两个列表，通过对应的元素相加构造出一个新的列表。

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

练习 3.23
对刚才的函数泛化，不知针对整型和相加操作。

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

练习 3.24

  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = ???