12-3 函數(shù)式程序設計

函數(shù)式程序設計主要內容命令式vs聲明式程序設計范式什么是函數(shù)式程序設計函數(shù)式程序設計基本手段邏輯式程序設計簡介命令式程序設計范式

（imperativeprogramming）命令式程序設計范式是指：針對一個目標，需要給出達到目標的操作步驟和狀態(tài)變化，即要對“如何做”進行詳細描述。它們與馮諾依曼體系結構一致，是使用較廣泛的程序設計范式，適合于解決大部分的實際應用問題。命令式程序設計范式的典型代表：過程式程序設計面向對象程序設計聲明式程序設計范式

（declarativeprogramming）聲明式程序設計范式是指：只需要給出目標的定義，不需要對如何達到目標（包括操作步驟和狀態(tài)變化）進行描述，即只需要對“做什么”進行描述。有良好的數(shù)學理論支持，易于保證程序的正確性，并且，設計出的程序比較精煉和具有潛在的并行性。聲明式程序設計范式的典型代表：函數(shù)式程序設計邏輯式程序設計例：命令式VS聲明式計算：a*b+c/d命令式編程： t1=a*b; t2=c/d; r=t1+t2;函數(shù)式編程： ...add(multiply(a,b),divide(c,d))...計算一系列數(shù)的和： a1+a2+a3+...+aN命令式編程： inta[N]={a1,a2,a3,...,aN},sum=0; for(inti=0;i<N;i++)sum

+=a[i]; cout<<sum;函數(shù)式編程： intsum(intx[],intn) {if(n==1)returnx[0];

elsereturnx[0]+sum(x+1,n-1); } inta[N]={a1,a2,a3,...,aN}; cout<<sum(a,N);什么是函數(shù)式程序設計函數(shù)式程序設計（functionalprogramming）是指把程序組織成一組數(shù)學函數(shù)，計算過程體現(xiàn)為基于一系列函數(shù)應用（把函數(shù)作用于數(shù)據(jù)）的表達式求值。函數(shù)也被作為值（數(shù)據(jù)）來看待，即函數(shù)的參數(shù)和返回值也可以是函數(shù)?；诘睦碚撌沁f歸函數(shù)理論和lambda演算。函數(shù)式程序設計的基本特征“純”函數(shù)：以相同的參數(shù)調用一個函數(shù)總得到相同的值。（引用透明）除了產生計算結果，不會改變其他任何東西。（無副作用）沒有狀態(tài)：計算體現(xiàn)為數(shù)據(jù)之間的映射，它不改變已有數(shù)據(jù)，而是產生新的數(shù)據(jù)。（無賦值操作）函數(shù)也是值：函數(shù)的參數(shù)和返回值都可以是函數(shù)，可由已有函數(shù)生成新的函數(shù)。（高階函數(shù)）遞歸是主要的控制結構：重復操作采用函數(shù)的遞歸調用來實現(xiàn)，而不采用迭代（循環(huán)）。表達式的惰性（延遲）求值（Lazyevaluation）：一個表達式只有需要用到它的值的時候才會去計算它。潛在的并行性：由于程序沒有狀態(tài)以及函數(shù)的引用透明和無副作用等特點，因此一些操作可以并行執(zhí)行。計算字符串的逆序："abcd"-->"dcba"命令式編程：voidreverse(charstr[])//修改已有數(shù)據(jù){for(inti=0,j=strlen(str)-1;i<j;i++,j--)

{chart=str[i];

str[i]=str[j];str[j]=t;

}}函數(shù)式編程：stringreverse(stringstr)//不修改已有數(shù)據(jù)，而是產生新數(shù)據(jù){if(len(str)==1)

returnstr;elsereturnconcat(reverse(substr(str,1,len(str)-1)),

substr(str,0,1));}//concat：字符串拼接；substr：求子串注意：不是寫成函數(shù)就是函數(shù)式編程！計算一系列數(shù)中偶數(shù)的個數(shù)。命令式編程：inta[N]={a1,a2,a3,...,aN},count=0;for(inti=0;i<N;i++)//指定操作步驟

if(a[i]%2==0)count++;cout<<count;函數(shù)式編程：boolf(intx){returnx%2==0;}vector<int>v={a1,a2,a3,...,aN};cout<<count_if(v.begin(),v.end(),f);函數(shù)式編程語言純函數(shù)式編程語言：CommonLisp,Scheme,Clojure,Racket,Erlang,OCaml,Haskell,F#對函數(shù)式編程提供支持的語言：Perl,PHP,C#3.0,Java8,Python,C++(11)C++是個多范式編程語言：除了支持過程式和面向對象程序設計范式外，也支持函數(shù)式程序設計范式。在C++中，函數(shù)式編程主要通過STL來實現(xiàn)。函數(shù)式程序設計的基本手段遞歸和尾遞歸過濾/映射/規(guī)約操作（Filter/Map/Reduce）部分函數(shù)應用（PartialFunctionApplication）柯里化（Currying）......遞歸實現(xiàn)重復操作，不采用迭代方式（循環(huán)），而是采用遞歸。例如，求第n個fibonacci數(shù)：命令式方案（迭代）intfib_1=1,fib_2=1,n=10;for(inti=3;i<=n;i++)//求第10個fibonacci數(shù){ inttemp=fib_1+fib_2;

fib_1=fib_2;fib_2=temp;}cout<<fib_2<<endl;函數(shù)式方案1（遞歸）intfib(intn){ if(n==1||n==2)return1; else

returnfib(n-2)+fib(n-1);}cout<<fib(10)<<endl;//求第10個fibonacci數(shù)尾遞歸由于函數(shù)遞歸調用效率低、遞歸調用深度受?？臻g的限制，因此，函數(shù)式編程常采用尾遞歸，即遞歸調用是函數(shù)的最后一步操作。求第n個fibonacci數(shù)的函數(shù)式方案2（尾遞歸）intfib(intn,inta,intb){ if(n==1)returna;

elseif(n==2)returnb; elsereturnfib(n-1,b,a+b);}cout<<fib(10,1,1)<<endl;//求第10個fibonacci數(shù)注意：不是函數(shù)體中只有一次遞歸調用就是尾遞歸！例如，下面的求n!的函數(shù)就不是尾遞歸：intfactorial(intn){if(n==1)return1;else

returnn*factorial(n-1);}尾遞歸調用便于編譯程序優(yōu)化：由于遞歸調用后不再做其它事，從而不會再使用當前棧空間的內容，因此，遞歸調用時不必額外分配棧空間，可重用當前的?？臻g?？梢宰詣愚D成迭代。intfib(intn,inta,intb){ while(true)

{if(n==1)returna;

elseif(n==2)returnb; else//returnfib(n-1,b,a+b);{intt1=n-1,t2=b,t3=a+b;n=t1;a=t2;b=t3;}

}}尾遞歸自動轉迭代一般形式的尾遞歸：Tf(T1x1,T2x2,...){.........returnf(m1,m2,...);.........returnf(n1,n2,...);......}轉換成等價的迭代：Tf(T1x1,T2x2,...){while(true){.........{T1t1=m1;T2t2=m2;...

x1=t1;x2=t2;...continue;}.........{T1t1=n1;T2t2=n2;...x1=t1;x2=t2;...continue;}......}}過濾操作（Filter）把一個集合中滿足某條件的元素選出來，構成一個新的集合。例如，求某整數(shù)集合中的所有正整數(shù)：vector<int>nums={1,-2,7,0,3},positives;copy_if(nums.begin(),nums.end(),

back_inserter(positives),[](intx){returnx>0;});for_each(positives.begin(),positives.end(),

[](intx){cout<<x<<',';});映射操作（Map）對一個集合中的每個元素分別進行某個操作，結果放到一個新集合中。例如，求某整數(shù)集合中各整數(shù)的平方：vector<int>nums={1,-2,7,0,3},squares;transform(nums.begin(),nums.end(),

back_inserter(squares),

[](intx){returnx*x;});for_each(squares.begin(),squares.end(),

[](intx){cout<<x<<',';});便于并行優(yōu)化規(guī)約操作（Reduce）對一個集合中的所有元素連續(xù)進行某個操作，最后得到一個值。例如，計算某整數(shù)集合中所有整數(shù)的和vector<int>nums={1,-2,7,0,3};intsum=accumulate(nums.begin(),nums.end(),

0,[](inta,intx){returna+x;});cout<<sum;運用過濾/映射/規(guī)約操作來實現(xiàn)：輸出學生中所有女生的名字和平均年齡：vector<Student>students,students_2;vector<string>names;//先篩選出“女生”copy_if(students.begin(),students.end(), back_inserter(students_2), [](Student&st){returnst.get_sex()==FEMALE;});//生成所有女生的名字transform(students_2.begin(),students_2.end(), back_inserter(names),

[](Student&st){returnst.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,[](inta,Student&st){returna+st.get_age();})/students_2.size();部分（偏）函數(shù)應用

（PartialFunctionApplication）對于一個多參數(shù)的函數(shù)，在某些應用場景下，它的一些參數(shù)往往取固定的值。部分函數(shù)應用是指：通過固定某函數(shù)的一些參數(shù)的值，生成一個新函數(shù)，該新函數(shù)不包含原函數(shù)中已指定固定值的參數(shù)。通過生成的新函數(shù)來使用原來的函數(shù)，可以省略一些具有固定值的參數(shù)傳遞。部分函數(shù)應用可縮小一個函數(shù)的適用范圍，提高函數(shù)的針對性。例如，對于下面的print函數(shù)：voidprint(intn,intbase);//按base指定的進制輸出n由于它常常用來按十進制輸出，因此，可以基于print生成一個新函數(shù)print10，它只接受一個參數(shù)n，把print的參數(shù)base固定為10：#include<functional>function<void(int)>print10= [](intn){returnprint(n,10);};或者autoprint10=[](intn){returnprint(n,10);};......print10(23);//等價于：print(23,10);上面的print10也可以通過STL中的算法bind以一種更通用的方式來實現(xiàn)：Fty2bind(Fty1fn,T1t1,T2t2,...,TNtn);fn為一個帶n個參數(shù)的函數(shù)（或函數(shù)對象）；t1～tn是為函數(shù)fn指定的參數(shù)值，其中的ti：可以是綁定的固定值；也可以是未綁定的值，未綁定的值用下劃線加上一個數(shù)字這樣的特殊名稱來表示（如：_1、_2、...等，在名空間std::placeholders中定義），其中的數(shù)字表示未綁定值的參數(shù)在新函數(shù)參數(shù)表中的位置；bind返回由所有未綁定值的參數(shù)所構成的新函數(shù)。例如，下面是基于bind實現(xiàn)的print10：#include<functional>usingnamespacestd;usingnamespacestd::placeholders;function<void(int)>print10=bind(print,_1,10);或者auto

print10=bind(print,_1,10);......print10(23);//等價于：print(23,10);再例如，下面的f2是把product的第二個參數(shù)y綁定為4之后得到的函數(shù)，其第一個參數(shù)為原來的x，第二個參數(shù)為原來的z：#include<functional>usingnamespacestd;usingnamespacestd::placeholders;

//_1、_2、...的定義所在的名空間doubleproduct(doublex,doubley,doublez){cout<<x<<"*"<<y<<"*"<<z<<endl;

returnx*y*z;}......function<double(double,double)>f2=bind(product,_1,4,_2); //bind返回一個帶兩個參數(shù)的函數(shù)：x和zf2(3,5);//把bind返回的函數(shù)作用于(3,5)，輸出：3*4*5再例如，下面的f3是把product的第二個參數(shù)y綁定為4之后得到的函數(shù)，其第一個參數(shù)為原來的z，第二個參數(shù)為原來的x：#include<functional>usingnamespacestd;usingnamespacestd::placeholders;

//_1、_2、...的定義所在的名空間doubleproduct(doublex,doubley,doublez){cout<<x<<"*"<<y<<"*"<<z<<endl;returnx*y*z;}......function<double(double,double)>f3=bind(product,_2,4,_1); //bind返回一個帶兩個參數(shù)的函數(shù)：z和xf3(3,5);//把bind返回的函數(shù)作用于(3,5)，輸出：5*4*3偏函數(shù)應用可縮小一個函數(shù)的適用范圍，提高函數(shù)的針對性。例如，可以基于下面的函數(shù)add生成兩個特殊的函數(shù)add1和add10，它們分別實現(xiàn)加一和加十的功能：#include<functional>usingnamespacestd;usingnamespacestd::placeholders;intadd(intx,inty){returnx+y;}autoadd1=bind(add,_1,1);//得到一個加1的函數(shù)autoadd10=bind(add,_1,10);//得到一個加10的函數(shù)......b=add1(a);//b為a的值加1c=add10(a);//c為a的值加10以數(shù)學家和邏輯學家HaskellCurry的名字來命名的。柯里化操作是把一個多參數(shù)的函數(shù)變換成一系列單參數(shù)的函數(shù)，它們分別接收原函數(shù)的第一個參數(shù)、第二個個參數(shù)、......。柯里化操作的意義：數(shù)學上：對單參數(shù)函數(shù)的研究模型可以用到多參數(shù)函數(shù)上。對程序設計：不必把一個多參數(shù)的函數(shù)所需要的參數(shù)同時提供給它，可以逐步提供?？吕锘僮鳎–urrying）例如，對于下面帶兩個參數(shù)的函數(shù)add：intadd(intx,inty){returnx+y;}可把它變成一個單參數(shù)函數(shù)add_cd（參數(shù)為函數(shù)f的參數(shù)x），該函數(shù)返回另一個單參數(shù)函數(shù)（參數(shù)為函數(shù)f的參數(shù)y）function<int(int)>

add_cd(intx)//返回值是個單參數(shù)函數(shù)//或者，autoadd_cd(intx){returnbind(add,x,_1);

//或

return[x](inty)->int{returnadd(x,y);};}......cout<<add_cd(1)(2);等價于：cout<<a