泛函编程（14）－try to map them all

  虽然明白泛函编程风格中最重要的就是对一个管子里的元素进行操作。这个管子就是这么一个东西：F[A]，我们说F是一个针对元素A的高阶类型，其实F就是一个装载A类型元素的管子，A类型是相对低阶，或者说是基础的类型。泛函编程风格就是在F内部用对付A类的函数对里面的元素进行操作。但在之前现实编程中确总是没能真正体会这种编程模式畅顺的用法：到底应该在哪里用？怎么用？可能内心里还是没能摆脱OOP的思维方式吧。在前面Stream设计章节里，我们采用了封装形式的数据结构设计，把数据结构uncons放进了特质申明里：

 1 trait Stream[+A] {

 2 def uncons: Option[(A, Stream[A])]

 3 def isEmpty: Boolean = uncons.isEmpty

 5 object Stream {

 6 def empty[A]: Stream[A] = new Stream[A] {

 7 def uncons = None

 9 def cons[A](h: = A, t: = Stream[A]): Stream[A] = new Stream[A] {

10 def uncons = Some((h,t))

12 def apply[A](as: A*): Stream[A] = {

13 if (as.isEmpty) empty

14 else cons(as.head, apply(as.tail: _*))

17 }

我们用tuple(A, Stream[A])来代表一个完整的Stream并把它放进一个Option里，本意是空的Stream就可以用None来表示。这个Option就像是那个附加的套子把我们的目标类型(A, Stream[A])套成了F[A]类型。其实我们的目的是对管子里的A类型进行操作，特别是对A类型元素进行模式匹配。但是在之前的设计里我们却对F[A]这个戴着套子的类型进行了模式匹配。静下来回顾一下觉着还是必须想办法尽量多用些泛函的方式来做。

先看看这个map函数，我们在前面曾经为Option编写了这个函数：(oa:Option[A]).map[B](f: A = B): Option[B]。我们可以向map传入一个操作A级别类型的函数，比如一段A级别类型的模式匹配方式代码。Option map返回的结果是Option[B]，是一个高阶类型，但我们可以很方便的用getOrElse来取得这个返回Option里面的元素。看个例子比较一下：

1 //戴着套子进行模式匹配

2 def toList: List[A] = uncons match {

3 case None = Nil

4 case Some((h,t)) = h :: t.toList

6 //用map操作

7 def toList: List[A] = uncons.map {

8 case (h,t) = h :: t.toList

9 } getOrElse(Nil)

从以上例子可以看出：通过使用map，用元素类型级别模式匹配，然后用getOrElse取出。Stream为空时采用getOrElse默认值。可以让代码更简洁易名。
看多几个例子：

 1 //戴着套子

 2 def take(n: Int): Stream[A] = {

 3 if ( n == 0 ) empty

 4 else

 5 uncons match {

 6 case None = empty

 7 case Some((h,t)) = cons(h,t.take(n-1))

10 //用map操作

11 def take(n: Int): Stream[A] = {

12 if ( n == 0 ) empty

13 else

14 uncons map {

15 case (h,t) = cons(h,t.take(n-1))

16 } getOrElse(empty)

18 //戴着套子

19 def takeWhile(f: A = Boolean): Stream[A] = {

20 uncons match {

21 case None = empty

22 case Some((h,t)) = if ( f(h) ) cons(h,t.takeWhile(f)) else empty

25 //用map操作

26 def takeWhile(f: A = Boolean): Stream[A] = {

27 uncons map {

28 case (h,t) = if ( f(h) ) cons(h,t.takeWhile(f)) else empty

29 } getOrElse empty

31 //高阶类型操作

32 def foldRight[B](z: B)(op: (A, = B) = B): B = {

33 uncons match {

34 case None = z

35 case Some((h,t)) = op(h,t.foldRight(z)(op))

38 //monadic style

39 def foldRight[B](z: B)(op: (A, = B) = B): B = {

40 uncons map {

41 case (h,t) = op(h,t.foldRight(z)(op))

42 } getOrElse z

43 }

嗯，改变操作方式时共性很明显。
再看看下面的例子，如果不用map的话会是多么的混乱：

1 //没用map方式

 2 def unfold[A,S](z: S)(f: S = Option[(A,S)]): Stream[A] ={

 3 f(z) match {

 4 case None = empty

 5 case Some((a,s)) = cons(a,unfold(s)(f))

 8 def mapByUnfold[B](f: A = B): Stream[B] = {

 9 unfold(uncons) {

10 case Some((h,t)) = Some((f(h),Some((t.headOption.getOrElse(h), t.tail.tailOption.getOrElse(empty)))))

11 case _ = None

14 def zipWithByUnfold[B,C](b: Stream[B])(f: (A,B) = C): Stream[C] = {

15 unfold((uncons,b.uncons)) {

16 case (Some((ha,ta)),Some((hb,tb))) = Some(f(ha,hb),(Some((ta.head,ta.tail)),Some((tb.head,tb.tail))))

17 case _ = None

19 }

看上面这些代码,由于传入unfold的函数f的返回结果是个高阶类型Option，这使得整体表达形式不但臃肿，更乱还很难看得懂。试着用map改写这些函数：

 1 def unfoldWithMap[A,S](z: S)(f: S = Option[(A,S)]): Stream[A] ={

 2 f(z) map {

 3 case (a,s) = cons(a,unfold(s)(f))

 4 } getOrElse empty

 6 def mapByUnfoldWithMap[B](f: A = B): Stream[B] = {

 7 unfold(this) { s = 

 8 this.uncons map {

 9 case (h,t) = (f(h),t)

12 }

看起来简洁多了。另外一个用了flatMap:

 1 def zipWithByUnfoldWithMap[B,C](b: Stream[B])(f: (A,B) = C): Stream[C] = {

 2 //起始状态是tuple(Stream[A],Stream[B])，状态转换函数 （s1,s2) = Option(a, (s1,s2))

 3 unfold((this,b)) { s = {

 4 for {

 5 a - s._1.uncons //用flatMap从Option[(A,Stream[A])]取出元素 (A,Stream[A])

 6 b - s._2.uncons //用flatMap从Option[(B,Stream[B])]取出元素 (B,Stream[B])

 7 } yield {

 8 ( f(a._1, b._1), (a._2, b._2) ) //返回新的状态：C (f(a,b),(ta,tb))

12 }

乍看起来好像挺复杂，但尝试去理解代码的意义，上面一段代码会更容易理解一点。
中间插播了一段map,flatMap的示范，目的是希望在后面的设计思考中向泛函编程风格更靠近一点。

 

再谈HashMap：使用map优化代码，你得学我这样做 我并没有和HashMap杠上，想着重新开始写点技术的东西，就拿HashMap开头了。最近开始重新学习数据结构和算法，其中有些东西学完之后，对于HashMap的理解和运用又有新的认识。虽然之前运用HashMap也有这样用过，但是知道了方法论，才发现这样使用的好处。 上一期我写过HashMap，写的是JDK8之前的Hash，现在都JDK15了，大家有兴趣可以去看一下源计划之从HashMap认识数据结构