FP-21 函数式程序设计

2023-07-30 12:03:46

Lecture 21 函数式程序设计

命令式程序设计范式（imperative programming）

过程式与面向对象程序设计属于命令式程序设计范式（imperative programming）

  • 需要对“如何做”进行详细描述，包括操作步骤和状态变化。

  • 它们与冯诺依曼体系结构一致，是使用较广泛的程序设计范式，适合于解决大部分的实际应用问题。

声明式程序设计范式（declarative programming）

除了命令式程序设计范式外，还有一类是声明式程序设计范式（declarative programming）

  • 只需要对“做什么”进行描述，而如何做则由实现系统自动完成。

  • 有良好的数学理论支持，易于保证程序的正确性，并且，设计出的程序比较精炼和具有潜在的并行性。

声明式程序设计范式的典型代表：

  • 函数式程序设计
  • 逻辑式程序设计

什么是函数式程序设计

函数式程序设计（functional programming）是指把程序组织成一组数学函数，计算过程体现为基于一系列函数应用（把函数作用于数据）的表达式求值。

函数也被作为值（数据）来看待，即函数的参数和返回值也可以是函数。

基于的理论是递归函数理论和lambda演算。

函数式程序设计的基本特征

  • “纯”函数（引用透明）：以相同的参数调用一个函数总得到相同的值。（无副作用）

  • 没有状态（数据不可变）：计算不改变已有数据，而是产生新的数据。（无赋值操作）

  • 函数也是值（first-class citizen) ：函数的参数和返回值都可以是函数。（高阶函数）

  • 递归是主要的控制结构：重复操作不采用迭代（循环）形式。

  • 表达式的惰性（延迟）求值（Lazy evaluation）：需要的时候才计算。

  • 潜在的并行性。

函数式程序设计语言

纯函数式语言：

  • Common Lisp, Scheme, Clojure, Racket, Erlang, OCaml, Haskell, F#

对函数式编程提供支持的非函数式语言：

  • Perl, PHP, C# 3.0, Java 8, Python, C++(11)

函数式程序设计的例子

计算：

a * b + c / d
  • 命令式编程：
t1 = a * b;
t2 = c / d;
r = t1 + t2;
  • 函数式编程：
multiply(...) { ... }
divide(...) { ... }
add(...) { ... }
... add(multiply(a,b),divide(c,d)) ...

计算一系列数的和：

a1 + a2 + a3 + ... + aN
  • 命令式编程：
int a[N] = {a1, a2, a3,..., aN},sum=0;
for (int i=0; i<N; i++) sum += a[i];
cout << sum;
  • 函数式编程：
int sum(int x[], int n)
{ if (n==1) return x[0];
     else return x[0]+sum(x+1,n-1);
}
int a[N] = {a1, a2, a3,..., aN};
cout << sum(a,N);

计算字符串的逆序：

"abcd" --> "dcba"
  • 命令式编程：
void reverse(char str[])
{ int len=strlen(str);
   for (int i=0; i<len/2; i++)
   {  char t=str[i];
      str[i] = str[len-i-1]; str[len-i-1] = t;
   }
}
  • 函数式编程：
string reverse(string str) 
{ if (len(str) == 1) 
 　	return str;
  else 
	 return concat(reverse(substr(str,1,len(str)-1)),substr(str,0,1));
}

注意：不是写成函数就是函数式编程！

计算一系列数中偶数的个数。

  • 命令式编程：
int a[N] = {a1, a2, a3,..., aN},count=0;
for (int i=0; i<N; i++) 
   if (a[i]%2 == 0) count++;
cout << count;
  • 函数式编程
bool f(int x) { return x%2 == 0; } 
vector<int> v={a1, a2, a3,..., aN};
cout << count_if(v.begin(),v.end(),f);

函数式程序设计的基本手段

递归：实现重复操作，不采用迭代方式（循环）。

尾递归：递归调用是递归函数的最后一步操作。（优化）

filter/map/reduce（过滤/映射/规约）

  • 过滤：把一个集合中满足某条件的元素选出来，构成一个新的集合。

  • 映射：分别对一个集合中每个元素进行某种操作，结果放到一个新集合中。

  • 规约：对一个集合中所有元素进行某个操作后得到一个值。

bind（绑定）：给一个函数的某些参数指定固定的值，返回一个只含有未指定值的参数所构成的函数。（偏函数）

currying（柯里化）：把接受多个参数的函数变换成接受单一参数（原函数的第一个参数）的函数，该函数返回一个接收剩余参数的函数。

递归

例如，求第n个fibonacci数

  • 命令式方案（迭代）
int fib_1=1,fib_2=1,n=10;
for (int i=3; i<=n; i++)
{	int temp=fib_1+fib_2;
	fib_1 = fib_2; fib_2 = temp;
}
cout << fib_2 << endl;
  • 函数式方案1（递归）
int fib(int n)
{	if (n == 1 || n == 2)  return 1;
	else  return fib(n-2)+fib(n-1);
}
cout << fib(10) << endl;

尾递归

函数式方案2（尾递归）

int fib(int n, int a, int b)
{	if (n == 1)  return a;
	else  return fib(n-1,b,a+b); 
}
cout << fib(10,1,1) << endl;
  • 便于编译程序优化：

    • 由于递归调用是本次调用的最后一步操作，因此，递归调用时可重用本次调用的栈空间。

    • 可以自动转成迭代。

尾递归自动转迭代

int fib(int n, int a, int b)
{	 while (true)
   { if (n == 1)  return a;
	    else  //return fib(n-1,b,a+b);
      { int t1=n-1,t2=b,t3=a+b;
         n = t1; a = t2; b = t3;
      }
   }
}

一般形式：

T f(T1 x1, T2 x2, ...)
{  ......
    ... return f(m1,m2,...);
    ......
    ... return f(n1,n2,...);
    ......
}

转换成：

T f(T1 x1, T2 x2, ...)
{  while (true)
    { ......
       ... { T1 t1=m1; T2 t2=m2; ... 
              x1 = t1; x2 = t2; ... continue;} 
       ......
       ... { T1 t1=n1; T2 t2=n2; ... 
              x1 = t1; x2 = t2; ... continue;}
       ......
    }
}

Filter操作

例如，求某整数集合中的所有正整数：

vector <int> nums={1,-2,7,0,3}, positives;
copy_if(nums.begin(),nums.end(),
	back_inserter(positives),[](int x){return x>0;});
for_each(positives.begin(),positives.end(),
	[](int x){ cout << x <<','; });

Map操作

例如，计算某整数集合中各整数的平方;

vector <int> nums={1,-2,7,0,3}, squares;
transform(nums.begin(),nums.end(), 
	back_inserter(squares), [](int x){return x*x;});
for_each(squares.begin(), squares.end(),
              [](int x){cout<<x<<',';});

Reduce操作

vector <int> nums={1,-2,7,0,3};
int sum = accumulate(nums.begin(), nums.end(),
			0, [](int a,int x) {return a+x;});
cout << sum;

运用过滤/映射/规约操作来实现：输出学生中所有女生的名字和平均年龄：

vector<Student> students,students_2;
vector<string> names;
copy_if(students.begin(),students.end(),
	     back_inserter(students_2),
   	[](Student &st) { return st.get_sex()==FEMALE;});

transform(students_2.begin(),students_2.end(),
		back_inserter(names),
	[](Student &st) { return st.get_name(); });

sort(names.begin(),names.end());
for_each(names.begin(),names.end(),
	[](string& s) { cout << s << endl; });

cout << accumulate(students_2.begin(),students_2.end(),0,
[](int a,Student &st) {return a+st.get_age();})/students_2.size();

bind操作

对于一个多参数的函数，在某些应用场景下，它的一些参数往往取固定的值。

可以针对这样的函数，生成一个新函数，该新函数不包含原函数中已指定固定值的参数。（partial function application，偏函数）

偏函数可缩小一个函数的适用范围，提高函数的针对性。

例如，对于下面的print函数：

void print(int n,int base); //按base指定的进制输出n

由于它常常用来按十进制输出，因此，可以基于print生成一个新函数print10，它只接受一个参数n，base固定为10：

#include <functional>
using namespace std;
using namespace std::placeholders;
function<void(int)> print10=bind(print,_1,10);
print10(23); //print(23,10);
  • Fty2 bind(Fty1 fn, T1 t1, T2 t2, ..., TN tN);

    • fn为N个参数的函数（或函数对象）；

    • t1～tN是为函数fn指定的参数值，其中的ti可以是绑定的值，也可以是未绑定的值。

    • 对未绑定的值用_1、_2、…等来表示，其中的数字表示未绑定值的参数在新函数参数表中的位置；

    • bind返回由所有未绑定值的参数所构成的新函数。

例如：

#include <functional>
using namespace std; 
using namespace std::placeholders; 
                              //_1、_2、...的定义所在的名空间
void product(double x, double y, double z)
{  cout << x << "*" << y << "*" << z << endl;
}
......
function<void(int,int)> f2=
bind(product,_1,4,_2);//bind返回一个带两个参数的函数
f2(3,5); //把bind返回的函数作用于(3,5)，输出：3*4*5

#include <functional>
using namespace std; 
using namespace std::placeholders; 
                              //_1、_2、...的定义所在的名空间
void product(double x, double y, double z)
{  cout << x << "*" << y << "*" << z << endl;
}
......
function<void(int,int)> f2=
bind(product,_2,4,_1);//bind返回一个带两个参数的函数
f2(3,5); //把bind返回的函数作用于(3,5)，输出：5*4*3

例如：

#include <functional>
using namespace std; 
using namespace std::placeholders; 
bool greater2(double x, double y) { return x > y; }
auto is_greater_than_42=bind(greater2, _1, 42);
auto is_less_than_42=bind(greater2, 42, _1);
cout << is_greater_than_42(45); //true
cout << is_less_than_42(45); //false

Currying操作

把函数f(x,y)变成单参数函数h(x)，h返回一个函数g(y)：

#include <functional>
using namespace std;
int f(int x,int y) 
{ return x+y; 
}
function<int (int)>  h(int x) //返回值是个函数对象
{ return [x](int y)->int { return x+y; };
   //等价于：return bind(f,x,_1);
}
......
cout << f(1,2);
cout << h(1)(2);

例如，利用上面的函数h可以为函数f生成一个特定的函数：

function<int (int)> add5=h(5); //add5(y)=5+y
......
int a,b,c;
......
... add5(a) ... //返回a+5
... add5(b) ... //返回b+5
... add5(c) ... //返回c+5
上一篇：C++输出斐波那契数列的前n项


下一篇：Python函数中的参数传递