⼀篇⽂章看懂函数式编程与命令式编程
⽂章⽬录
1 历史来源
在计算机的世界中，有两位巨擘对问题的可计算性做了模型化描述
⼀位是阿兰.图灵（Alan Turing），他提出的图灵机。计算机系的各种学科中都充斥着这个概念，假设有⼀个纸带和⼀个打孔机，然后有⼀套指令，能够控制打孔机在纸带上移动、能够读取当前位置是否打了孔、能够在当前位置打⼀个孔，这就是⼀个图灵机，假设⼀个问题能够靠这个纸带+打孔机+指令的⽅式解决，那就说明这个问题是“可计算的”。
另外⼀个位巨擘，是阿隆佐·邱奇（Alonzo Church）。邱奇是个数学家，他提出了Lambda演算(Lambda Calculus)的概念，⽤函数组合的⽅式来描述计算过程，换句话来说，如果⼀个问题能够⽤⼀套函数组合的算法来表达，那就说明这个问题是可计算的。
我个⼈对这两种计算过程的模型是这样理解的，不⼀定对：
图灵机是通过⼀系列指令和状态来完成某种过程的
Lambda演算是通过⼀系列函数来描述问题并求解的
当然世上没有两全其美的东西上⾯两种模型肯定都有⾃⼰的局限性，并不是所有的问题都是可以⽤函数式模型解决
2 编程范式
编程语⾔主要有三种类型：
声明式编程：专注于”做什么”⽽不是”如何去做”。在更⾼层⾯写代码，更关⼼的是⽬标，⽽不是底层算法实现的过程。
如：css, 正则表达式，sql 语句，html, xml…
命令式编程(过程式编程) : 专注于”如何去做”，这样不管”做什么”，都会按照你的命令去做。解决某⼀问题的具体算法实现。
函数式编程：把运算过程尽量写成⼀系列嵌套的函数调⽤。
命令式编程
命令式编程是通过赋值（由表达式和变量组成）以及控制结构（如，条件分⽀、循环语句等）来修改可修改的变量。
它的运作⽅式具有图灵机特性，且和冯诺依曼体系的对应关系⾮常密切。甚⾄可以说，命令式程序就是⼀个冯诺依曼机的指令序列：
变量→
内存
变量引⽤→
输⼊设备
变量赋值→
输出设备
控制结构→
跳转操作
我们知道的，冯诺依曼结构需要⽤总线来传输数据，我们只能⼀个字节⼀个字节处理。
这也就形成了运⾏的瓶颈。程序执⾏的效率取决于执⾏命令的数量，因此才会出现⼤O表⽰法等等表⽰时间空间复杂度的符号。
3 函数式编程的崛起
⼀直以来，作为函数式编程代表的Lisp，还是Haskell，更多地都是在⼤学中，在实验室中应⽤，⽽很少真的应⽤到真实的⽣产环境。
先让我们再来回顾⼀下伟⼤的摩尔定律：
1、集成电路芯⽚上所集成的电路的数⽬，每隔18个⽉就翻⼀番。
2、微处理器的性能每隔18个⽉提⾼⼀倍，⽽价格下降⼀半。
3、⽤⼀个美元所能买到的电脑性能，每隔18个⽉翻两番。
⼀如摩尔的预测，整个信息产业就这样飞速地向前发展着，但是在近年，我们却可以发现摩尔定律逐渐地失效了，芯⽚上元件的尺⼨是不可能⽆限地缩⼩的，这就意味着芯⽚上所能集成的电⼦元件的数
量⼀定会在某个时刻达到⼀个极限。那么当技术达到这个极限时，我们⼜该如何适应⽇益增长的计算需求，电⼦元件⼚商给出了答案，就是多核。
多核并⾏程序设计就这样被推到了前线，⽽命令式编程天⽣的缺陷却使并⾏编程模型变得⾮常复杂，⽆论是信号量，还是锁的概念，都使程序员不堪其重。
就这样，函数式编程终于在数⼗年后，终于⾛出实验室，来到了真实的⽣产环境中，⽆论是冷门的Haskell，Erlang，还是Scala，F#，都是函数式编程成功的典型。
4 函数式编程
相⽐于命令式编程关⼼解决问题的步骤，函数式编程是⾯向数学的抽象，关⼼数据（代数结构）之间的映射关系。函数式编程将计算描述为⼀种表达式求值。
在狭义上，函数式编程意味着没有可变变量，赋值，循环和其他的命令式控制结构。即，纯函数式编程语⾔。
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
4.1 函数
函数式编程中的函数，这个术语不是指命令式编程中的函数（我们可以认为C++程序中的函数本质是⼀段⼦程序Subroutine），⽽是指数学中的函数，即⾃变量的映射（⼀种东西和另⼀种东西之间的对应关系）。也就是说，⼀个函数的值仅决定于函数参数的值，不依赖其他状态。
在函数式语⾔中，函数被称为⼀等函数（First-class function），与其他数据类型⼀样，作为⼀等公民，处于平等地位，可以在任何地⽅定义，在函数内或函数外；可以赋值给其他变量；可以作为参数，传⼊另⼀个函数，或者作为别的函数的返回值。
4.2 纯函数
纯函数是⼀种函数特殊的函数，即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)
4.3 变量与表达式
纯函数式编程语⾔中的变量也不是命令式编程语⾔中的变量（存储状态的内存单元），⽽是数学代数中的变量，即⼀个值的名称。
变量的值是不可变的（immutable），也就是说不允许像命令式编程语⾔中那样能够多次给⼀个变量赋值。⽐如说在命令式编程语⾔我们写x = x + 1。
函数式语⾔中的条件语句，循环语句等也不是命令式编程语⾔中的控制语句，⽽是⼀种表达式。
“表达式”（expression）是⼀个单纯的运算过程，总是有返回值；
“语句”（statement）是执⾏某种操作(更多的是逻辑语句。)，没有返回值。
函数式编程要求，只使⽤表达式，不使⽤语句。也就是说，每⼀步都是单纯的运算，⽽且都有返回值。⽐如在Scala语⾔中，if else不是语句⽽是三元运算符，是有返回值的。
严格意义上的函数式编程意味着不使⽤可变的变量，赋值，循环和其他命令式控制结构进⾏编程。 当然，很多所谓的函数式编程语⾔并没有严格遵循这⼀类的准则，只有某些纯函数式编程语⾔，如Haskell等才是完完全全地依照这种准则设计的。
4.5 函数与⽅法
当然在现在很多（⾮纯）函数式编程语⾔中也有⽅法和函数的区别。⽐如
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  it as a partially applied function
m
^
scala>val f =(x:Int)=>2*x  //定义⼀个函数
f:Int=>Int=<function1>
scala> f    //函数可以作为最终表达式出现
res9:Int=>Int=<function1>
⽅法就是命令式编程中的函数，⽽函数则是函数式编程中的函数。
4.6 状态
⾸先要意识到，我们的程序是拥有“状态”的。 想⼀想我们调试C++程序的时候，经常会在某处设置⼀个断点。程序执⾏断点就暂停了，也就是说程序停留在了某⼀个状态上。
这个状态包括了当前定义的全部变量，以及⼀些当前系统的状态，⽐如打开的⽂件、⽹络的连接、申请的内存等等。具体保存的信息和语⾔有关系。
⽐如使⽤过Matlab、R之类的科学计算语⾔的朋友会知道，在退出程序的时候它会让你选择是否要保存当前的session，如果保存了，下次打开时候它会从这个session开始继续执⾏，⽽不是清空⼀切重来。你之前定义了⼀个变量x = 1，现在这个x还在那⾥，值也没变。
这个状态就是图灵机的纸带。有了状态，我们的程序才能不断往前推进，⼀步步向⽬标靠拢的。
函数式编程不⼀样。函数式编程强调⽆状态，不是不保存状态，⽽是强调将状态锁定在函数的内部，不依赖于外部的任何状态。更准确⼀点，它是通过函数创建新的参数或返回值来保存程序的状态的。
我们都知道函数的状态是完全存在栈上，函数执⾏完后就会从栈中弹出函数内部的状态也就会消失，这时候就可以使⽤递归来维持这个状态，函数⼀层层的叠加起来，其中每个函数的参数（是参数，不是变量）或返回结果来代表了程序的⼀个中间状态。
⽤斐波那契数函数举个例⼦
def Fib(a):
if a==0or a==1:
return1
else:
return Fib(a-2)+Fib(a-1)
//执⾏的时候每个步骤的状态都储存栈上知道a==0or 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
4.7 函数式编程的特性
⾼阶函数（Higher-order function）
偏应⽤函数（Partially Applied Functions）
柯⾥化（Currying）
闭包（Closure）
⾼阶函数
4.7.1 ⾼阶函数
⾼阶函数就是参数为函数或返回值为函数的函数，可以理解为函数的抽象
有了⾼阶函数，就可以将复⽤的粒度降低到函数级别。相对于⾯向对象语⾔中的抽象类，⾼阶函数的复⽤粒度更低
举例：
scala不是内部或外部命令def id(x:Int):Int= x
def cube(x:Int):Int= x * x * x
def fact(x:Int):Int=if(x ==0)1else fact(x -1)
//计算a~b之间整数的和
def sumInts(a:Int, b:Int):Int=
if(a > b)0else a + sumInts(a +1, b)
//计算a~b之间⽴⽅和
def sumCubes(a:Int, b:Int):Int=
if(a > b)0else cube(a)+ sumCubes(a +1, b)
//计算a~b之间阶乘和
def sumFactorials(a:Int, b:Int):Int=
if(a > b)0else 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 = File("hdfs://...")val counts = file.flatMap(line => line.split(" ")).map(word =>(word,1)).reduceByKey(_ + _) counts.saveAsTextFile("hdfs:/ /...")
4.7.2 偏应⽤函数（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
}
4.7.3 柯⾥化
curry 的概念很简单：把接受多个参数的函数变换成接受⼀个单⼀参数（最初函数的第⼀个参数）的函数，并且返回接受余下的参数⽽且返回结果的新函数

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。