历史来源
在计算机的世界中，有两位巨擘对问题的可计算性做了模型化描述
一位是阿兰.图灵（Alan Turing），他提出的图灵机。计算机系的各种学科中都充斥着这个概念，假设有一个纸带和一个打孔机，然后有一套指令，能够控制打孔机在纸带上移动、能够读取当前位置是否打了孔、能够在当前位置打一个孔，这就是一个图灵机，假设一个问题能够靠这个纸带+打孔机+指令的方式解决，那就说明这个问题是“可计算的”。
另外一个位巨擘，是阿隆佐·邱奇（Alonzo Church）。邱奇是个数学家，他提出了Lambda演算(Lambda Calculus)的概念，用函数组合的方式来描述计算过程，换句话来说，如果一个问题能够用一套函数组合的算法来表达，那就说明这个问题是可计算的。
我个人对这两种计算过程的模型是这样理解的，不一定对：
图灵机是通过一系列指令和状态来完成某种过程的
Lambda演算是通过一系列函数来描述问题并求解的
当然世上没有两全其美的东西上面两种模型肯定都有自己的局限性，并不是所有的问题都是可以用函数式模型解决
编程范式
编程语言主要有三种类型：
声明式编程：专注于”做什么”而不是”如何去做”。在更高层面写代码，更关心的是目标，而不是底层算法实现的过程。
如：css,正则表达式，sql语句，html,xml…命令式编程(过程式编程) : 专注于”如何去做”，这样不管”做什么”，都会按照你的命令去做。解决某一问题的具体算法实现。
函数式编程：把运算过程尽量写成一系列嵌套的函数调用。
命令式编程
命令式编程是通过赋值（由表达式和变量组成）以及控制结构（如，条件分支、循环语句等）来修改可修改的变量。
它的运作方式具有图灵机特性，且和冯诺依曼体系的对应关系非常密切。甚至可以说，命令式程序就是一个冯诺依曼机的指令序列：
变量 →
内存
变量引用 →
输入设备
变量赋值 →
输出设备
控制结构 →
跳转操作
我们知道的，冯诺依曼结构需要用总线来传输数据，我们只能一个字节一个字节处理。
这也就形成了运行的瓶颈。程序执行的效率取决于执行命令的数量，因此才会出现大O表示法等等表示时间空间复杂度的符号。
函数式编程的崛起
一直以来，作为函数式编程代表的Lisp，还是Haskell，更多地都是在大学中，在实验室中应用，而很少真的应用到真实的生产环境。
先让我们再来回顾一下伟大的摩尔定律：
1、集成电路芯片上所集成的电路的数目，每隔18个月就翻一番。
2、微处理器的性能每隔18个月提高一倍，而价格下降一半。
3、用一个美元所能买到的电脑性能，每隔18个月翻两番。
一如摩尔的预测，整个信息产业就这样飞速地向前发展着，但是在近年，我们却可以发现摩尔定律逐渐地失效了，芯片上元件的尺寸是不可能无限地缩小的，这就意味着芯片上所能集成的电子元件的数量一定会在某个时刻达到一个极限。那么当技术达到这个极限时，我们又该如何适应日益增长的计算需求，电子元件厂商给出了答案，就是多核。
多核并行程序设计就这样被推到了前线，而命令式编程天生的缺陷却使并行编程模型变得非常复杂，无论是信号量，还是锁的概念，都使程序员不堪其重。
就这样，函数式编程终于在数十年后，终于走出实验室，来到了真实的生产环境中，无论是冷门的Haskell，Erlang，还是Scala，F#，都是函数式编程成功的典型。
函数式编程
相比于命令式编程关心解决问题的步骤，函数式编程是面向数学的抽象，关心数据（代数结构）之间的映射关系。函数式编程将计算描述为一种表达式求值。
在狭义上，函数式编程意味着没有可变变量，赋值，循环和其他的命令式控制结构。即，纯函数式编程语言。
Pure Lisp, XSLT, XPath, XQuery, FP
Haskell (without I/O Monad or UnsafPerformIO)
在广义上，函数式编程意味着专注于函数
Lisp, Scheme, Racket, Clojure
SML, Ocaml, F#
Haskell (full language)
Scala
Smalltalk, Ruby
函数
函数式编程中的函数，这个术语不是指命令式编程中的函数（我们可以认为C++程序中的函数本质是一段子程序Subroutine），而是指数学中的函数，即自变量的映射（一种东西和另一种东西之间的对应关系）。也就是说，一个函数的值仅决定于函数参数的值，不依赖其他状态。
在函数式语言中，函数被称为一等函数（First-class function），与其他数据类型一样，作为一等公民，处于平等地位，可以在任何地方定义，在函数内或函数外；可以赋值给其他变量；可以作为参数，传入另一个函数，或者作为别的函数的返回值。
纯函数
纯函数是一种函数特殊的函数，即xtong相同的输入永远会得到相同的输出，而且没有任何可观察的副作用。
即：不依赖外部状态,不改变外部状态
这里用JavaScript举例
//不纯的函数
var num = 2;
function add(a){
return a+ num;
}
var arr = [1,2,3];
function myPush(arr){
return arr.push(4)
}
//num arr 都被函数改变了
//纯的函数
function add(a,b){
return a+b;
}
//add 函数没有改变外部变量 同时相同的输入永远会得到相同的输出
// 比如 add(1,2)=add(1,2)
变量与表达式
纯函数式编程语言中的变量也不是命令式编程语言中的变量（存储状态的内存单元），而是数学代数中的变量，即一个值的名称。
变量的值是不可变的（immutable），也就是说不允许像命令式编程语言中那样能够多次给一个变量赋值。比如说在命令式编程语言我们写x = x + 1。
函数式语言中的条件语句，循环语句等也不是命令式编程语言中的控制语句，而是一种表达式。
“表达式”（expression）是一个单纯的运算过程，总是有返回值；
“语句”（statement）是执行某种操作(更多的是逻辑语句。)，没有返回值。
函数式编程要求，只使用表达式，不使用语句。也就是说，每一步都是单纯的运算，而且都有返回值。比如在Scala语言中，if else不是语句而是三元运算符，是有返回值的。
严格意义上的函数式编程意味着不使用可变的变量，赋值，循环和其他命令式控制结构进行编程。 当然，很多所谓的函数式编程语言并没有严格遵循这一类的准则，只有某些纯函数式编程语言，如Haskell等才是完完全全地依照这种准则设计的。
函数与方法
当然在现在很多（非纯）函数式编程语言中也有方法和函数的区别。比如scala
scala> def m(x:Int) = 2*x //定义一个方法
m: (x: Int)Int
scala> m //方法不能作为最终表达式出现
<console>:9: error: missing arguments for method m;
follow this method with '_' if you want to treat it as a partially applied function
m
^
scala> val f = (x:Int) => 2*x //定义一个函数
f: Int => Int = <function1>
scala> f //函数可以作为最终表达式出现
res9: Int => Int = <function1>
方法就是命令式编程中的函数，而函数则是函数式编程中的函数。
状态
首先要意识到，我们的程序是拥有“状态”的。 想一想我们调试C++程序的时候，经常会在某处设置一个断点。程序执行断点就暂停了，也就是说程序停留在了某一个状态上。
这个状态包括了当前定义的全部变量，以及一些当前系统的状态，比如打开的文件、网络的连接、申请的内存等等。具体保存的信息和语言有关系。
比如使用过Matlab、R之类的科学计算语言的朋友会知道，在退出程序的时候它会让你选择是否要保存当前的session，如果保存了，下次打开时候它会从这个session开始继续执行，而不是清空一切重来。你之前定义了一个变量x = 1，现在这个x还在那里，值也没变。
这个状态就是图灵机的纸带。有了状态，我们的程序才能不断往前推进，一步步向目标靠拢的。
函数式编程不一样。函数式编程强调无状态，不是不保存状态，而是强调将状态锁定在函数的内部，不依赖于外部的任何状态。更准确一点，它是通过函数创建新的参数或返回值来保存程序的状态的。
我们都知道函数的状态是完全存在栈上，函数执行完后就会从栈中弹出函数内部的状态也就会消失，这时候就可以使用递归来维持这个状态，函数一层层的叠加起来，其中每个函数的参数（是参数，不是变量）或返回结果来代表了程序的一个中间状态。
用斐波那契数函数举个例子
def Fib(a):
if a==0 or a==1:
return 1
else:
return Fib(a-2)+Fib(a-1)
//执行的时候每个步骤的状态都储存栈上知道a==0 or a==1的时候在归纳从栈中一个个弹出
//命令编程模式的写法
def Fib(n):
a=1
b=1
n = n - 1
while n>0:
temp=a
a=a+b
b=temp
n = n-1
return b
函数式编程的特性
- 高阶函数（Higher-order function）
- 偏应用函数（Partially Applied Functions）
- 柯里化（Currying）
- 闭包（Closure）
高阶函数
高阶函数就是参数为函数或返回值为函数的函数，可以理解为函数的抽象
有了高阶函数，就可以将复用的粒度降低到函数级别。相对于面向对象语言中的抽象类，高阶函数的复用粒度更低
举个栗子
def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x == 0) 1 else fact(x - 1)
//计算a~b之间整数的和
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)
//计算a~b之间立方和
def sumCubes(a: Int, b: Int): Int =
if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
//计算a~b之间阶乘和
def sumFactorials(a: Int, b: Int): Int =
if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)
上面三个函数参数相同计算的形状都式求和但是计算的方式不同，这时候就可以把这三个函数抽象一下
//在函数式编程模式里函数式一等公民可以和变量一样传入另一个函数中
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0
else f(a) + sum(f, a + 1, b)
def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubs(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)
高阶函数提供了一种函数级别上的依赖注入（或反转控制）机制，在上面的例子里，sum函数的逻辑依赖于注入进来的函数的逻辑。很多GoF设计模式都可以用高阶函数来实现，如Visitor(访问者模式)，Strategy(策略模式)，Decorator(装饰模式)等。比如Visitor模式就可以用集合类的map()或foreach()高阶函数来替代。
函数式语言通常提供非常强大的集合类（Collection），提供很多高阶函数，因此使用非常方便。
比如说，我们想对一个列表中的每个整数乘2，在命令式编程中需要通过循环，然后对每一个元素乘2，但是在函数式编程中，我们不需要使用循环，只需要使用如下代码：
scala> val numbers = List(1, 2, 3, 4)
numbers: List[Int] = List(1, 2, 3, 4)
scala> numbers.map(x=>x*2)
res3: List[Int] = List(2, 4, 6, 8)
在大数据处理框架Spark中，一个RDD就是一个集合。以词频统计的为例代码如下：
val file = spark.textFile("hdfs://...") val counts = file.flatMap(line => line.split(" ")) .map(word => (word, 1)) .reduceByKey(_ + _) counts.saveAsTextFile("hdfs://...")
偏应用函数（Partially Applied Functions）
偏函数，也叫部分应用函数，就是固化函数的一个或一些参数，只传入函数的部分参数，从而产生一个新的函数
举个例子
object PartialAppliedFunction {
def main(args: Array[String]): Unit = {
val part_sum = sum(1,_:Int,3)
//这里只想要传入要_代表的那一部分参数就行了
println(part_sum(2))
}
def sum(a:Int,b:Int,c:Int)=a+b+c
}
柯里化
curry 的概念很简单：把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数
举个例子
//柯里化前
function add(a, b, c) { return a + b + c;}
//柯里化后
function _add(a) {
return function(b) {
return function(c) {
return a + b + c;
}
}
}
console.log(add(1)(2)(3)) // 6
//进阶版 可以无限调用
function add(){
var args = [].slice.call(arguments);
var fn = function(){
var newArgs = args.concat([].slice.call(arguments));
return add.apply(null,newArgs);
}
fn.toString = function(){
return args.reduce(function(a, b) { return a + b; })
}
return fn ;
}
console.log(add(1)(2)(3));
闭包
闭包的基础是一等函数（First-class function）。
闭包在形式上就是一个函数内部定义另一个函数，函数的堆栈在在函数返回后并不释放
举个栗子
function outer() {
var n = 2;
function inner() { return n; };
return inner();
}
var result = outer();
console.log(result); // 2 行数中的n并没有在执行后释放
函数式编程的好处
由于命令式编程语言也可以通过类似函数指针的方式来实现高阶函数，函数式的最主要的好处主要是不变性带来的。
引用透明（Referential transparency）
引用透明（Referential transparency），指的是函数的运行不依赖于外部变量或”状态”，只依赖于输入的参数，任何时候只要参数相同，引用函数所得到的返回值总是相同的。
其他类型的语言，函数的返回值往往与系统状态有关，不同的状态之下，返回值是不一样的。这就叫”引用不透明”，很不利于观察和理解程序的行为。
没有可变的状态，函数就是引用透明（Referential transparency）
没有副作用（No Side Effect）。
副作用（side effect），指的是函数内部与外部互动（最典型的情况，就是修改全局变量的值），产生运算以外的其他结果。
函数式编程强调没有”副作用”，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。
函数即不依赖外部的状态也不修改外部的状态，函数调用的结果不依赖调用的时间和位置，这样写的代码容易进行推理，不容易出错。这使得单元测试和调试都更容易。
还有一个好处是，由于函数式语言是面向数学的抽象，更接近人的语言，而不是机器语言，代码会比较简洁，也更容易被理解。
优化处理
由以上两点，由衍生出了更多的特性。
无锁并发
没有副作用使得函数式编程各个独立的部分的执行顺序可以随意打乱，（多个线程之间）不共享状态，不会造成资源争用(Race condition)，也就不需要用锁来保护可变状态，也就不会出现死锁，这样可以更好地进行无锁（lock-free）的并发操作。
尤其是在对称多处理器（SMP）架构下能够更好地利用多个处理器（核）提供的并行处理能力。
惰性求值
惰性求值[7]（lazy evaluation，也称作call-by-need）是这样一种技术：是在将表达式赋值给变量（或称作绑定）时并不计算表达式的值，而在变量第一次被使用时才进行计算。
这样就可以通过避免不必要的求值提升性能。
在Scala里，通过lazy val来指定一个变量是惰性求值的，如下面的示例所示：
scala> val x = { println("x"); 15 }
x
x: Int = 15
scala> lazy val y = { println("y"); 13 }
y: Int = <lazy>
scala> y
y
res3: Int = 13
scala> y
res4: Int = 13
可以看到，在Scala的解释器中，当定义了x变量时就打印出了“x”，而定义变量y时并没有打印出”y“，而是在第一次引用变量y时才打印出来。
函数式编程总览
看完了函数式编程的特点，我们想想函数式编程的应用场合。
数学推理
并行程序
其实函数式编程最适合地还是解决局部性的数学小问题，要让函数式编程来做CRUD，来做我们传统的逻辑性很强的Web编程，就有些免为其难了，现在Java8中也引入了lambda表达式来支持函数式编程
参考文章
https://www.cnblogs.com/feng9exe/p/9167737.html
https://blog.csdn.net/u013007900/article/details/79104110
https://blog.csdn.net/jiajiayouba/article/details/49983325?utm_source=blogxgwz0
https://blog.csdn.net/LeeSirbupt/article/details/80834700?utm_source=blogxgwz0
https://www.ibm.com/developerworks/cn/java/j-lo-java8streamapi/
https://www.jb51.net/article/73208.htm
