关键词：
前情提要
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测试下，编程功底就是这样一步一步打下的。
3.小结
函数式的数据结构篇到此就结束，希望在这里，你能明白函数式的数据结构与我们最开始接触到的数据结构的实现有哪些不同，又为何要大费周章用函数式的方式实现！！
很多scala的教程介绍到这里就一句话，scala的默认数据结构是不可变的，如果可变的要怎样巴拉巴拉，这样容易让人陷入知其然不知其所以然的地步。
同时我也一直决定，学习语言的话，语法知识最表层的东西。真正深入学习一门语言，你需要逐渐知道这门语言在设计上的取舍，甚至是设计上的哲学，比如python的至简哲学。
而在深入这些东西的过程中，语法自然而然就掌握了，比如较为晦涩的隐式转换。在这里就会知道隐式转换是这样用的，原来spark里面一直都有这个东西参与！！！
接下来一篇将介绍scala中的错误处理方式，依旧是函数式的处理方式，像java中的trycatch肯定是非函数式的，那么scala是怎么实现的呢，下一篇就来介绍:)
如果有什么疑问，也欢迎留言。
以上~
scala函数式编程(代码片段)
Scala函数式编程什么是函数式编程？1、函数式编程将计算视为数学上的函数计算2、函数成为了和普通的值一样的"头等公民"，可以像任何其他数据类型的值一样被传递和操作函数式编程成为越来越流行的编程范式1... 查看详情
《java8实战》读书笔记12：函数式编程(代码片段)
《Java8实战》读书笔记12：函数式编程第13章函数式的思考13.1实现和维护系统13.1.1共享的可变数据13.1.2声明式编程13.2什么是函数式编程13.2.1函数式Java编程13.2.2引用透明性13.2.3面向对象的编程和函数式编程的对比13.2.4函数式编... 查看详情
scala学习（函数式编程面向对象编程）(代码片段)
文章目录函数式编程基础函数编程函数定义函数参数函数至简原则高阶函数编程面向对象编程基础面向对象编程高阶面向对象编程函数式编程基础函数编程函数定义packagelearn03objectdemo01defmain(args:Array[String]):Unit=//无参、无返回... 查看详情
scala学习（函数式编程面向对象编程）(代码片段)
文章目录函数式编程基础函数编程函数定义函数参数函数至简原则高阶函数编程面向对象编程基础面向对象编程高阶面向对象编程函数式编程基础函数编程函数定义packagelearn03objectdemo01defmain(args:Array[String]):Unit=//无参、无返回... 查看详情
《java8实战》读书笔记12：函数式编程(代码片段)
...阶函数（higher-orderfunction）14.1.2科里化14.2持久化数据结构14.3Stream的延迟计算14.4模式匹配14.5杂项14.5.1缓存或记忆表14.5.2“返回同样的对象”意味着什么14.5.3结合器14.6小结读书总结第13章函数式的思考本章内容为什么要... 查看详情
scala笔记整理：函数式编程(代码片段)
[TOC]作为值传递的函数测试代码如下：packagecn.xpleaf.bigdata.p4.function/***scala中关于函数的操作*/object_01FunctionOpsdefmain(args:Array[String]):Unit=functionOps1/***作为值传递的函数*将一个函数作为值传递给另外一个函数变量的时候，约定需要在... 查看详情
scala学习之函数式风格编程(代码片段)
...unctional-programming.htmlScala允许您以面向对象编程(OOP)风格、函数式编程(FP)风格甚至混合风格编写代码，结合使用这两种方法。本书假设您是从Java、C++或C#等OOP语言来到Scala的& 查看详情
scala函数式编程初步（高阶函数）(代码片段)
参数式函数定义一个参数是函数的函数。(完整定义=>匿名函数)objecthelloWorlddefmain(args:Array[String]):Unit=defaddxy(x:Int,y:Int):Int=x+ydefmulxy(x:Int,y:Int):Int=x*ydeffunc1(a:Int,b:Int,f:(Int,Int)=> 查看详情
scala中的控制结构(代码片段)
...一些代码控制语法，如Scala中的if,while,for,try,match,以及函数调用等。需要注意的是，Scala几乎所有的内建控制结构都会返回一个值，这是由于函数式编程语言被认为是计算值的过程，所以作为函数式编程语言的一个... 查看详情
scala的函数式编程(代码片段)
Scala的函数式编程 Scala的函数式编程的特点 -高阶函数 -闭包 -模式匹配可参考：http://blog.51cto.com/14048416/2337136 -单一赋值 -延迟计算 -类型推导 -尾部调用优化 &e... 查看详情
scala学习函数式编程续case类(代码片段)
文章目录CASECLASSESWith`apply`youdon’tneed`new`NomutatormethodsAn`unapply`method`copy`method`equals`and`hashCode`methods`toString`methodsThebiggesta 查看详情
scala基础(代码片段)
...是一门类似Java的多范式语言，集合了面向对象编程和函数式编程的特性。使用Scala语言编写Spark应用程序的考虑：1）Scala具有强大的并发性，支持函数式编程，可以更好的支持分布式系统。在大数据时代，... 查看详情
swift函数式编程九（图表）(代码片段)
代码地址一种描述图表的函数式方式，并利用CoreGraphics来绘制它们。通过对CoreGraphic进行一层函数式的封装，可以得到一个更简单且易于组合的API。绘制正方形和圆首先通过如下代码可以绘制下面的图表：letbound=CGR... 查看详情
swift函数式编程九（图表）(代码片段)
代码地址一种描述图表的函数式方式，并利用CoreGraphics来绘制它们。通过对CoreGraphic进行一层函数式的封装，可以得到一个更简单且易于组合的API。绘制正方形和圆首先通过如下代码可以绘制下面的图表：letbound=CGR... 查看详情
理解函数式编程
相信大家平时或多或少听过不少关于“函数式编程”（FP）相关的词语，有些Geek经常吹捧函数式的优点或者特性比如：纯函数无副作用、不变的数据、高阶函数、流计算模式、尾递归、柯里化等等，再加上目前的函数式理论越来... 查看详情
scala编程之惰性函数(代码片段)
一、为什么需要惰性函数惰性计算(尽可能延迟表达式求值)是许多函数式编程语言的特性。惰性集合在需要时提供其元素,无需预先计算它们,这带来了一些好处。首先,您可以将耗时的计算推迟到绝对需要的时候。其次,您可以创造... 查看详情
函数式编程(代码片段)
WhatFunctionalProgramming(函数式编程)在概念上和ObjectOrientedProgramming(面向对象编程),ProceduralProgramming(过程化编程)类似,是一种编程范式。与OOP以对象为中心的理念不同，FP将所有计算机的操作视为函数运算，函数是操作的基本单位。函... 查看详情
函数式编程简介-附入门方法(代码片段)
WHAT?什么是函数式编程？函数式编程是一种编程范式。编程范式又是什么？编程范式是一种解决问题的思路。我们熟悉的命令式编程把程序看作一系列改变状态的指令；而函数式编程把程序看作一系列数学函数映射的组合。编程... 查看详情