thinking

函数式编程

Posted by yueLng on 2018-02-27

概念定义

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.函数式编程是一种编程模型，他将计算机运算看做是数学中函数的计算，并且避免了状态以及变量的概念

函数式编程

函数式编程的核心思想是避免副作用，也就是说，函数接受参数并生成输出而不保留任何状态或修改任何不反映在返回值中的内容，遵循这种理想方式的函数可以被看成纯函数式函数。

1
2
3
/# 一个非纯函数
def remove_last_item(mylist):
	mylist.pop(-1) # this modifiles mylist

1
2
3
/# 一个纯函数
def butlast(mylist):
	return mylist[:-1] # this returns a copy of mylist

函数式编程实用特点

  • 可行化证明，（数学理论）
  • 模块化，在一定程度上对问题进行分冶
  • 简洁语法
  • 并发
  • 可测性

Python中的函数式编程

代码是命令式的。一个函数式的版本应该是声明式的

Map(映射)
1
2
name_lengths = map(len, ["Mary", "Isla", "Sam"])
squares = map(lambda x: x * x, [0, 1, 2, 3, 4])
Reduce(迭代)
1
sum = reduce(lambda a, x: a + x, [0, 1, 2, 3, 4])

lambda表达式

lambda包括一条变换规则（变量替换）和一条函数定义方式，Lambda演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图灵机的.

摘自wikipedia
在编程语言中，等价于匿名函数，被称为lambda表达式，作用是作为参数传入高阶函数，或者作为闭包返回
原本的lambda算子是只接收一个参数作为输入，在匿名函数中可以看到lambda是支持多个参数的，如下

1
(x,y) -> x*y

这种看似一个lambda表达式，其实是两个，而这种接受一个参数返回另一个接收第二个参数的函数叫柯里化

尾调用(Tail Call)

尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。尾调用之所以与其他调用不同，就在于它的特殊的调用位置。由于是函数的最后一步，所以不需要保存外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到，只要直接用内层函数的调用记录，取代外层的调用记录就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();
// 等同于
function f() {
  return g(3);
}
f();
// 等同于
g(3);

上面代码中，如果函数g不是尾调用，函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后，函数f就结束了，所以执行到最后一步，完全可以删除 f() 的调用记录，只保留 g(3) 的调用记录。

这就叫做”尾调用优化”（Tail call optimization），即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。这就是”尾调用优化”的意义。

递归本质上是一种循环操作。纯粹的函数式编程语言没有循环操作命令，所有的循环都用递归实现，这就是为什么尾递归对这些语言极其重要。对于其他支持”尾调用优化”的语言（比如Lua，ES6），只需要知道循环可以用递归代替，而一旦使用递归，就最好使用尾递归。

一些关于函数式编程的文章

  • 函数式编程扫盲篇
    飞林沙，推荐系统专家，这篇文章首先是说明了函数式编程在wiki上的概念，即本文定义，然后由erlang编程为例，高并发的使用更加轻量级的进程和函数不变性。接着说道函数式编程在现代编程中的意义，文章中特意对这一句话描红，是这样说的

    多核并行程序设计就这样被推到了前线，而命令式编程天生的缺陷却使并行编程模型变得非常复杂，无论是信号量，还是锁的概念，都使程序员不堪其重。

函数式在数学上表示就是，对应特定的输入，经过一系列函数，结果应该是可预见的，在抽象层面来说，是使用函数为最小单位，构造高阶函数对现实的重新代码抽象，需要注意的一点是，函数式编程是通过函数参数来保持状态的，作为函数的附属品。
递归是函数式编程绕不开的话题，文章指出循环在于描述我们该如何解决问题，而递归在于描述这个问题

1
2
3
4
5
def Fib(a):
    if a==0 or a==1:
        return 1
    else:
        return Fib(a-2)+Fib(a-1)

关于尾递归和伪递归，尾递归就是不要保持当前递归函数的状态，而把需要保持的东西全部用参数给传到下一个函数里，这样就可以自动清空本次调用的栈空间。斐波拉契数列尾递归的写法，下面是树形递归

1
2
3
4
5
def Fib(a,b,n):
    if n==0:
       return b
    else:
       return Fib(b,a+b,n-1)

对于上述代码的解释，传入的a和b分别是前两个数，那么每次我都推进一位，那么b就变成了第一个数，而a+b就变成的第二个数。其实对于尾递归都可以转化为循环的写法，还是编译器是否支持的问题，转化为循环迭代就不会有堆栈溢出的问题了
惰性求值和并行,如以下代码，获取a和b的值并无直接关联，如果可以利用多核的优势，使得获取a和b值的总时间为获取其中一个值的最长时间

1
2
3
4
def getResult():
    a = getA()   //Take a long time
    b = getB()   //Take a long time
    c = a + b

  • Python函数式编程指南

  • 对函数式语言的误解
    来自王垠大神对于函数式编程的理解，主要说明了一些Haskell使用者标榜自己是“纯函数式”编程者，但是王大神举了一个产生随机函数的例子来说明，纯函数式编程是没有必要的，虽然在Haskell领域针对这个问题想到了一个解决办法Monad，但是大神又说引入后编程是杂乱的，根本完全没必要，就算最后的实现上产生的机器代码编译后的结果都是相同的，无论是否使用了局部变量来保存中间结果。可以参看Haskell Wiki 关于monad的文章Monad Class，总的来说大神这篇文章能够给初次接触函数式编程的同学一个总体的认识。

  • Functional JavaScript Mini Book

参考资料

尾调用优化
函数式编程术语及示例

CATALOG
    FEATURED TAGS
    thinking
    FRIENDS