函数式编程范式(2):特点

函数式编程的特点

1 函数是一等公民

在函数式编程中,函数而是指数学中的函数,即自变量的映射,其输出仅取决于输入的参数,而和调用函数的次序无关。在函数式语言中,函数作为一等公民,可以在任何地方定义,在函数内或函数外,可以作为函数的参数和返回值,可以对函数进行组合。为了和命令式编程中的函数区分开来,通常这种函数通常称为纯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def pure_function(x):
'''
纯函数,输入只和输出有关
'''
return x+2
y=2
def usual_function(x):
return x+y
print u'纯函数的输出 %s,%s' %(pure_function(0),pure_function(0))
print u'有副作用的函数 %s' %usual_function(0)
y=0
print u'有副作用的函数 %s' %usual_function(0)
纯函数的输出 2,2
有副作用的函数 2
有副作用的函数 0

1.1 高阶函数

函数是函数式编程的第一型,我们在函数式编程中努力用函数来表达所有的概念,完成所有的操作。
在面向对象编程中,我们把对象传来传去,那在函数式编程中,我们要做的是把函数传来传去,而这个,说成术语,我们把他叫做高阶函数。

1
2
3
4
5
6
7
8
9
# 函数作为参数传递
def add(x, y, f):
'''
@param f :函数, 只接受一个参数的函数
'''
return f(x) + f(y)
print add(-3,4, lambda x:x**2) # return (-3)^2+4^2
print add(-3,4, abs) # return abs(-3)+abs(4)
25
7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#函数作为返回值传递
def lazy_sum(*args):
'''
在函数里面定义返回一个函数,这个函数的作用是用来求和
'''
def sum():
print "函数真正执行"
ax = 0
for n in args:
ax = ax + n
return ax
print '将函数作为返回值返回'
return sum
function_sum=lazy_sum(1,2,3)
function_sum()
将函数作为返回值返回
函数真正执行
函数真正执行





6

1.2 匿名函数

在我们程序中,经常有这样一些需求:

  1. 需要一个临时函数,这个函数只会使用一次,或者使用的很少。
  2. 这个函数的方法体很短,以至于比方法声明都短,写起来实在没劲(我将其称之为“一句话方法”)。
    当我们在传入函数时,有些时候,不需要显式地定义函数,直接传入匿名函数更方便。

比如map 函数
map 函数

如果我们想要将一个数组(列表)中的每个元素都+2返回

1
2
3
4
5
def add2(x):
return x+2
print map( add2 , [1,2,3,4,5] )
print map( lambda x:x+2, [1,2,3,4,5])
[3, 4, 5, 6, 7]
[3, 4, 5, 6, 7]

java的
面向对象传递的是对象(匿名内部类)

1
2
3
4
5
6
new Thread(new Runnable() {
@Override
public void run() {
System.out.println("Before Java8 ");
}
}).start();

面向函数可以传递一个函数,而且可以传递匿名函数

1
new Thread( () -> System.out.println("In Java8!") ).start();

1.3 闭包(Closure)

闭包的产生,并不是纯函数式编程,而是在把函数式编程思想引入到命令式编程中所必然

对于函数f来说,它引用了这个函数外部的一个变量,当执行完function_add2=closure(2)之后,执行closure(2)所用的栈空间应该被清空,x理应被回收,那么这个时候函数f(也就是function_add2)还引用着外部变量x?这需要语言在某种层面,通过某种方式实现。闭包由一个函数和创建这个函数时所引用的外部的变量组成
function_add2 绑定了外部变量2,function_add10绑定了外部变量10

1
2
3
4
5
6
7
8
9
10
11
12
def closure(x):
def f(y):
return x+y
return f #return lambda y:x+y
function_add2=closure(2)
print "2+3",function_add2(3)
print"2+4", function_add2(4)
function_add10=closure(10)
print "10+3",function_add10(3)
print "10+4",function_add10(4)

2不变性

不变性(immutability)是函数式编程的基石之一。
FP中并没有变量的概念,东西一旦创建后就不能再变化,所以在FP中经常使用这一术语而非变量

  1. 不变性对程序并行化有着深远的影响,因为一切不可变意味着可以就地并行,不涉及竞态,也就没有了锁的概念。
  2. 不变性还对重构有了新的意义,因为它使得对函数的执行有了数学意义,于是乎重构本身成了对函数的化简。FP使代码的分析变的容易,从而使重构的过程也变的轻松了许多。
  3. 不变性还对测试有了新的启发,函数的输入和输出不改变任何状态,于是我们可以随时使用REPL工具来测试函数,测试通过即可使用,不用担心行为的异常,不变性保证了该函数在任何地方都能以同样的方式工作。事实上,在函数式编程实践中,“编写函数、使用REPL工具测试,使用”三步曲有着强大的生产力。

更容易理解的代码。由于不存在副作用,无论多少次执行,相同的输入就意味着相同的输出。纯函数比有可变状态的函数和对象理解起来要容易简单得多。你无需再担心对象的某个状态的改变,会对它的某个行为(函数)产生影响。

2.1 递归

事实上函数式程序是可以保存状态的,只不过它们用的不是变量,而是函数。状态保存在函数的参数中,也就是说在栈上。如果你需要保存一个状态一段时间并且时不时的修改它,那么你可以编写一个递归函数。
比如要计算一个列表的长度:

1
2
3
4
5
6
7
def list_len(l):
if l==[]:return 0
return list_len(l[1:])+1
print list_len([1,2,3,4,5])
print list_len([])
print list_len([0,6,2,34,5])
5
0
5

1.2 尾递归

普通递归函数的效率是很低的,拿斐波那契数列(Fibonacci sequence)为例,每计算一次,都需要为其分配一个单独的堆栈空间,而堆栈空间的数量和n的关系是指数关系
fib

1
2
3
4
def F(n):
if n==1: return 1
if n==0: return 0
else: return F(n-1)+F(n-2)

尾递归和一般的递归不同在对内存的占用,普通递归创建stack累积而后计算收缩,尾递归只会占用恒量的内存(和迭代一样)
怎么写尾递归?形式上只要最后一个return语句是单纯函数就可以

观察到,tail_F(n,ret1,ret2)中形式变量ret1和ret2的实际变量值是不断更新的,对比普通递归就很清楚,后者每个F()调用中y值不变,仅在层级上加深。所以,尾递归是把变化的参数传递给递归函数的变量了。
sd

1
2
3
4
5
def tail_F(n,ret1,ret2):
if n==0: return ret1
return tail_F(n-1,ret2, ret1+ret2)
tail_F(5,0,1)
5

2.3 惰性求值

函数无副作用,变量不可变,那么早算晚算的结果应该是一样的
惰性求值使得代码具备了巨大的优化潜能。支持惰性求值的编译器会像数学家看待代数表达式那样看待函数式程序:抵消相同项从而避免执行无谓的代码,安排代码执行顺序从而实现更高的执行效率甚至是减少错误。在此基础上优化是不会破坏代码正常运行的。严格使用形式系统的基本元素进行编程带来的最大的好处,是可以用数学方法分析处理代码,因为这样的程序是完全符合数学法则的。

1
2
3
4
5
6
7
8
9
10
11
12
13
val fun=(x:Int)=>{println("计算x+2")
x+2} //fun: Int => Int = <function1>
val y1=fun(2)
//计算x+2
//y1: Int = 4
lazy val y2=fun(2)
//y2: Int = <lazy>
y2+3
//计算x+2
//res1: Int = 7

3 模式匹配

模式匹配不是什么新的创新特性,事实上,它和函数式编程的关系不大。把产生模式匹配归因于函数式编程的唯一的原因是函数式语言早就提供了模式匹配,然而现在的命令式语言还大多做不到。

1
2
3
4
5
6
7
8
def processLine(tokens: Any) = tokens match {
case Array(a, "", _*) => "second is empty,first is"+ a.toString
case i:Int if i%2 ==0 => "偶数"
case x:Int => println("Int")
case s:String => println("string")
case m : Map[_ , _] => m.size
case _ => "default"
}

4 currying(柯里化)

λx.λy.x+y 这是一个加法的lambda 演算f(x,y)=x+y
$$λx.λy.x+y \qquad2 \qquad 3=5$$
等效如下
$$((λx.λy.x+y)2)3)=5$$
如果只输入一个参数
$$(λx.λy.x+y) 2 = λy.2+y $$
返回结果是一个参数是一个函数

然后接着 在把3传入
$$λy.2+y \qquad 3 =5$$

其实就是
f(x,y)=x+y

g(y)=f(x=2,y)=2+y

Scala里的Curry化可以把函数从接收多个参数转换成多个参数列表。如果要用同样的一组实参多次调用一个函数,可以用curry化来减少噪音,让代码更有味道。

关于柯里化(currying),我们可以这么理解:柯里化就是一个函数在参数没给全时返回另一个函数,返回的函数的参数正好是余下的参数。比如:你制定了x和y, 如2的3次方,就返回8, 如果你只制定x为2,y没指定, 那么就返回一个函数:2的y次方, 这个函数只有一个参数:y。

1
2
3
4
5
6
7
8
9
10
def doSomethingNtimes(n:Int)(f:()=>Unit){
1 to n foreach(ii=>f())}
val doSomething20times=doSomethingNtimes(20)_
lazy val println20Times=doSomething20times(()=>println("SDSDDS"))
println20Times
doSomethingNtimes(20){
()=>println("SD")
}