首页 > > 程序设计 > Java技术 >

Scala函数式编程（四）函数式的数据结构下

2019-12-19 16:05:37来源：博客园阅读 ()

Scala函数式编程（四）函数式的数据结构下

前情提要

Scala函数式编程指南（一）函数式思想介绍

scala函数式编程（二） scala基础语法介绍

Scala函数式编程（三） scala集合和函数

Scala函数式编程（四）函数式的数据结构上

1.List代码解析

今天介绍的内容，主要是对上一篇介绍的scala函数式数据结构补充，主要讲代码。可以先看看上一节，主要讲的是函数式的list，Scala函数式编程（四）函数式的数据结构上。这些代码我都放在我的公众号里面，包括函数式的List以及一个函数式的二叉搜索树，关注公众号：哈尔的数据城堡，回复“scala树数据结构”就能直接获得（写文章不容易，大哥大姐关注下吧 :) ）。

话说回来，上一篇中，主要介绍了List的一些基础用法，包括定义基础的结构，节点Cons和结尾的Nil。以及使用一个object List来定义基础的List操作。

//定义List为特质，Nil和Cons为结尾和中间的Node
sealed trait List[+A]

case object Nil extends List[Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A] {
  override def toString: String = s"$head :: ${tail.toString}"
}


//Listc操作的定义方法，object相当于java中的静态类，里面的方法可以直接调用
object List {

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

  def map[A,B](l: List[A],f: A => B): List[B] =l match {
    case Nil              => Nil
    case Cons(head, tail) =>Cons(f(head), map(tail,f))
  }
  def apply[A](a: A*): List[A] =
    if (a.isEmpty) Nil
    else Cons(a.head, apply(a.tail: _*))

  def empty[A]: List[A] = Nil


  object ops {
    //定义隐式转换，这个是为了扩充List的操作而准备的，可以看看最下面是如果使用的
    implicit def listOps[A](list: List[A]): ListOps[A] = new ListOps(list)
  }
}

关于节点Cons和Nil的定义和上一节一样，只是Cons多了个重写的toString方法。

简单再说下，这里呢，在object List里面，在里面我们定义了apply方法，可以初始化生成一个List。以及上一节提到的sum和map方法。如果对这些看不明白可以看看上一节的内容。

但这样的话当我们要调用sum方法的时候，只能通过object List来调用，类似下面这样：

//使用object List里面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil

//使用object List里面的sum方法
scala> List.sum(numList)
res0: Int = 10

但是呢，我们日常使用的时候可不是这样呀，我们更熟悉的应该是要这样：

//使用object List里面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil

//直接使用numList内置的方法来处理
scala> numList.sum()
res0: Int = 10

更加通用的做法，应该是通过List本身，来调用方法，就像上面看到的那样。通常的做法，是直接加在Cons里面，但由于Cons是继承自trait List[+A]，所以大家（包括）Nil里面都需要定义那一堆方法了，有没有别的办法呢？

有的，scala的又一个语法糖，隐式转换，就是上面object List里面的ops。

  object ops {
    //定义隐式转换，这个是为了扩充List的操作而准备的，可以看看最下面是如果使用的
    implicit def listOps[A](list: List[A]): ListOps[A] = new ListOps(list)
  }

隐式转换主要是通过implicit这个关键字定义的，当然隐式转换还有其他用法，不管这里的用法算是最常见的用法了。

隐式转换函数，看的主要是参数，以及返回，函数名字（这里名字是listOps）是不重要的，起什么都没关系。

隐式转换的作用这里不多解释，可以百度看看，简单说就是在需要的时候，将一个类型转换成另一种类型。这里的作用，是在特定的情况下将我们定义的List转成ListOps类型，而ListOps类，则在下面给出。

//扩充List的操作
private[list] final class ListOps[A](list: List[A]) {
//导入隐式转换函数，因为下面的处理也是需要隐式转换
  import List.ops._

  //使用递归实现，foldRight的实现就是调用了这个函数，这么做是为了复用
  //代码复用是函数式中很重要的一个特性，看下面append方法就可以明白
  def foldRightAsPrimary[B](z: B)(f: (A, B) => B): B = list match {
    case Nil              => z
    case Cons(head, tail) => f(head, tail.foldRightAsPrimary(z)(f))
  }

  def foldRight[B](z: B)(f: (A, B) => B): B = foldRightViaFoldLeft(z)(f)

  def map[B](f: A=> B): List[B] = list match {
    case Nil              => Nil
    case Cons(head, tail) => Cons(f(head), tail.map(f))
  }

}

有了这段代码后，当我们需要使用map的时候，就可以不用再借助object List代劳，而可以直接使用，就像这样：

//使用object List里面的apply方法初始化，生成List
scala> val numList = List(1,2,3,4)
numList: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil

//直接使用numList内置的方法来处理，而不是List.map(numList,function)
scala> numList.map(function)

当代码检测到List调用map方法，但List内部并没有map方法，就会触发隐式转换，转换成ListOps类型，调用ListOps类型里面的map方法，然后返回一个List作为结果。虽然经过了诸多波折，但调用者是感受不到的，反而感觉就像是List里面本身的map方法一样。在Spark里面就有很多这样的操作。

如上面的代码，现在我们可以直接使用numList.map(function)这样的方式，就像List里面本身就有map函数一样来使用了。

2.二叉搜索树

在上一篇末尾，给出了一份还未完成的数据结构，二叉搜索树当作练习。这一节就来讲讲这个。

其实如果把之前的List都看懂的话，其实二叉搜索树并没有什么难点。

二叉搜索树，是树，自然就有叶节点和叶子节点（就是末尾）。不过这次和List不一样的是，没有使用隐式转换，所以我们定义的就不是特质了，而是先定义一个抽象类。然后让叶节点和叶子节点继承它。

  //定义一个二叉树的抽象类
  sealed abstract class TreeMap[+A] extends AbstractMap[Int, A] {

    def add[B >: A](kv: (Int, B)): TreeMap[B] = ???
    def deleteMin: ((Int, A), TreeMap[A]) = ???
    def delete(key: Int): TreeMap[A] = ???
    def get(key: Int): Option[A] = ???
    def +[A1 >: A](kv: (Int, A1)): TreeMap[A1] =  ???
    def -(k: Int): TreeMap[A] = ???
    override def toList: List[(Int, A)] = ???
    def iterator: Iterator[(Int, A)] =???
  }
  
  //叶子节点，也就是每个分支的末尾，继承了上面的抽象类
  case class Leaf() extends TreeMap[Nothing]
  //叶节点，包含左右和内容，继承了上面的抽象类
  case class Node[+A](key: Int, value: A,
                      left: TreeMap[A], right: TreeMap[A]) extends TreeMap[A]

二叉树中有有基础的增删查操作，还重载了两个符号，+和-分别代表增加和删除。对了，这里的???，其实和python里面的pass是一样的，就充当个占位符，告诉编译器这里会有东西的，先别报错。

然后主要就是要实现二叉树里面空缺的代码，其实熟悉树结构的同学应该都知道，递归是树天生的基因。所以这里自然都是要通过递归实现的。不过在编写前，还是要提一下，一般函数式编程里面，不会使用可变变量（var），也不会使用可变的数据结构（ListBuff）。

实现过程也没什么好解释的，其实就是通过递归，以及scala的模式匹配，如果碰到叶子节点就挂掉，不是就递归去进行。直接看代码。这里主要介绍add方法，其他的基本都是类似的：


  sealed abstract class TreeMap[+A] extends AbstractMap[Int, A] {
    ......
    //使用模式匹配，实现递归操作，主要是找到对应的位置，插入数据
    def add[B >: A](kv: (Int, B)): TreeMap[B] = {

      val (key, value) = kv
      //this就是当前的类型，可能是叶节点，也可能是叶子节点
      this match {
        case Node(nodeKey, nodeValue, left, right) => {
          //按照二叉搜索树的规则，进行递归
          if(nodeKey > key)
            Node(nodeKey, nodeValue, left.add((key,value)), right)
          else if(nodeKey < key)
            Node(nodeKey, nodeValue, left, right.add((key,value)))
          else
            Node(nodeKey, value, left, right)
        }
        //如果是叶子节点，则新生成一个叶节点，返回
        case Leaf() => {
          Node(key, value, Leaf(), Leaf())
        }
      }

      ......
    }

根据二叉搜索树的规则，新键大于节点的键的时候，插入右边，小于节点的键的时候，插入到左边。然后约定好结束条件，也就是碰到叶子节点的时候返回。这样一来就完成了插入的操作。后面无论是删除，还是查找，都是同样的思路。

而重载运算符方法，比如重载+方法，就是直接调用上面的add方法，即直接复用。然后看看object TreeMap。

  object TreeMap {

    def empty[A]: TreeMap[A] = Leaf()

    def apply[A](kvs: (Int, A)*): TreeMap[A] = {
      kvs.toSeq.foldLeft(empty[A])(_ + _)
    }
  }

这个object主要作用有两个，一个是生成叶子节点，一个是初始化一棵树（注意是apply方法）。和List一样，这里也是用多参数的输入方式，不同的是这里没有用递归，而是直接把多个参数转化成一个序列，然后用foldLeft，逐个累加。从而实现初始化树。

OK，到这里就结束了，最后还是希望你能够自己试着写下tree的代码，写完再用test case测试下，编程功底就是这样一步一步打下的。