函數(shù)式編程與面向?qū)ο缶幊蘙1]: Lambda表達(dá)式 函數(shù)柯里化 高階函數(shù).md
之劍
2016.5.2 11:19:09
什么是lambda表達(dá)式
例子
For example, in Lisp the 'square' function can be expressed as a lambda expression as follows:
(lambda (x) (* x x))
定義
“Lambda 表達(dá)式”(lambda expression)是一個(gè)匿名函數(shù)裆操，Lambda表達(dá)式基于數(shù)學(xué)中的λ演算得名章喉，直接對應(yīng)于其中的lambda抽象(lambda abstraction)，是一個(gè)匿名函數(shù)，即沒有函數(shù)名的函數(shù)娇斑。Lambda表達(dá)式可以表示閉包（注意和數(shù)學(xué)傳統(tǒng)意義上的不同）描焰。
Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It was first introduced by mathematician Alonzo Church in the 1930s as part of an investigation into the foundations of mathematics. Lambda calculus is a universal model of computation equivalent to a Turing machine (Church-Turing thesis, 1937). Its namesake, Greek letter lambda (λ), is used in lambda terms (also called lambda expressions) to denote binding a variable in a function.
Lambda calculus may be typed and untyped. In typed lambda calculus functions can be applied only if they are capable of accepting the given input's "type" of data.
Lambda calculus has applications in many different areas in mathematics, philosophy,linguistics, and computer science. Lambda calculus has played an important role in the development of the theory of programming languages. Functional programming languages implement the lambda calculus. Lambda calculus also is a current research topic in Category theory.
λ演算(λ-calculus)
Lambda演算和函數(shù)式語言的計(jì)算模型天生較為接近母赵，Lambda表達(dá)式一般是這些語言必備的基本特性。如：
Scheme:
(lambda(x)(+x1))
Haskell:
\x->x+1
λ演算是一套用于研究函數(shù)定義悠砚、函數(shù)應(yīng)用和遞歸的形式系統(tǒng)。函數(shù)的作用 (application) 是左結(jié)合的：
f x y = (f x) y
它包括一條變換規(guī)則 (變量替換) 和一條函數(shù)定義方式.
比如說,下面的這個(gè)圓錐曲線二元二次函數(shù):
$$f(x,y)=x2+y2$$
讓我們用其他的一些方式來表達(dá):
匿名函數(shù)表達(dá)
$$(x,y) \rightarrow x^2 + y^2$$
柯里化表達(dá)
$$x \rightarrow (y \rightarrow x^2 + y^2 )$$
演算過程
為了更加簡單的理解其演算過程, 分解各個(gè)步驟如下:
數(shù)學(xué)函數(shù)表達(dá)式: \(f(5,2) = 5^2 + 2^2 = 29\)
匿名函數(shù)式:\( ((x,y) \rightarrow (x^2 + y^2)) (5,2) = 5^2 + 2^2 = 29\)
柯里化函數(shù)式: \( (x \rightarrow ( y \rightarrow (x^2 + y^2) )(5))(2)=(y \rightarrow (52+y2))(2) = 52+22=29 \)
lambda演算的歷史
λ演算由 Alonzo Church 和 Stephen Cole Kleene 在 20 世紀(jì)三十年代引入堂飞，Church 運(yùn)用 lambda 演算在 1936 年給出 判定性問題 (Entscheidungsproblem) 的一個(gè)否定的答案灌旧。這種演算可以用來清晰地定義什么是一個(gè)可計(jì)算函數(shù)。關(guān)于兩個(gè) lambda 演算表達(dá)式是否等價(jià)的命題無法通過一個(gè)通用的算法來解決绰筛，這是不可判定性能夠證明的頭一個(gè)問題枢泰，甚至還在停機(jī)問題之先。Lambda 演算對函數(shù)式編程有巨大的影響别智，特別是Lisp 語言宗苍。
Church 整數(shù)
在 lambda 演算中有許多方式都可以定義自然數(shù)，但最常見的還是Church 整數(shù)薄榛，下面是它們的定義：
$$ 0 = \lambda f\cdot \lambda x\cdot x $$
$$ 1 = \lambda f\cdot \lambda x\cdot f x $$
$$ 2 = \lambda f\cdot \lambda x\cdot f (f x ) $$
$$ 3 = \lambda f\cdot \lambda x\cdot f(f (f x )) $$
$$...$$
$$ n = \lambda f\cdot \lambda x\cdot f^n( x ) $$
以此類推讳窟。直觀地說，lambda 演算中的數(shù)字 n 就是一個(gè)把函數(shù) f 作為參數(shù)并以 f 的 n 次冪為返回值的函數(shù)敞恋。換句話說丽啡，Church 整數(shù)是一個(gè)高階函數(shù) :
以單一參數(shù)函數(shù) f 為參數(shù)，返回另一個(gè)單一參數(shù)的函數(shù)硬猫。
(注意在 Church 原來的 lambda 演算中补箍，lambda 表達(dá)式的形式參數(shù)在函數(shù)體中至少出現(xiàn)一次，這使得我們無法像上面那樣定義 0)
C#Lambda表達(dá)式
C#的Lambda 表達(dá)式都使用 Lambda 運(yùn)算符 =>啸蜜，該運(yùn)算符讀為“goes to”坑雅。語法如下：
形參列表=>函數(shù)體
(input parameters) => expression
(input parameters) => {statement;}
函數(shù)體多于一條語句的可用大括號(hào)括起。例子:
() => Console.Write("0個(gè)參數(shù)")
I => Console.Write("1個(gè)參數(shù)時(shí)參數(shù)列中可省略括號(hào)衬横，值為：{0}",i)
(x,y) => Console.Write("包含2個(gè)參數(shù)裹粤，值為：{0}*{1}",x,y)
//兩條語句時(shí)必須要大括號(hào)
I => { i++;Console.Write("兩條語句的情況"); }
Lambda 表達(dá)式是一種可用于創(chuàng)建委托或表達(dá)式目錄樹類型的匿名函數(shù)。 通過使用 lambda 表達(dá)式蜂林，可以寫入可作為參數(shù)傳遞或作為函數(shù)調(diào)用值返回的本地函數(shù)遥诉。 Lambda 表達(dá)式對于編寫 LINQ 查詢表達(dá)式特別有用。
若要?jiǎng)?chuàng)建 Lambda 表達(dá)式噪叙，需要在 Lambda 運(yùn)算符 => 左側(cè)指定輸入?yún)?shù)（如果有）矮锈，然后在另一側(cè)輸入表達(dá)式或語句塊。 例如睁蕾，lambda 表達(dá)式 x => x * x 指定名為 x 的參數(shù)并返回 x 的平方值苞笨。
過濾條件:
List<User> users = new List<User>();
Func<User, bool> predicate = ((user) =>
{
return user.UserId > 100;
}
);
List<User> temps = users.Where(predicate).ToList();
Java Lambda表達(dá)式
Java 8的一個(gè)大亮點(diǎn)是引入Lambda表達(dá)式，使用它設(shè)計(jì)的代碼會(huì)更加簡潔。當(dāng)開發(fā)者在編寫Lambda表達(dá)式時(shí)猫缭，也會(huì)隨之被編譯成一個(gè)函數(shù)式接口葱弟。下面這個(gè)例子就是使用Lambda語法來代替匿名的內(nèi)部類，代碼不僅簡潔猜丹，而且還可讀芝加。
沒有使用Lambda的老方法：
Runnable r = new Runnable(){
@Override
public void run(){
System.out.println("Running without Lambda");
}
};
使用Lambda表達(dá)式:
Runnable r =() -> {
System.out.println("Running without Lambda");
};
C++ Lambda表達(dá)式
ISO C++ 11 標(biāo)準(zhǔn)的一大亮點(diǎn)是引入Lambda表達(dá)式∩渲希基本語法如下：
[capture list] (parameter list) ->return type { function body }
其中除了“[ ]”（其中捕獲列表可以為空）和“復(fù)合語句”（相當(dāng)于具名函數(shù)定義的函數(shù)體）藏杖，其它都是可選的。它的類型是唯一的具有成員operator()的非聯(lián)合的類類型脉顿，稱為閉包類型(closure type)蝌麸。
C++中，一個(gè)lambda表達(dá)式表示一個(gè)可調(diào)用的代碼單元艾疟。我們可以將其理解為一個(gè)未命名的內(nèi)聯(lián)函數(shù)来吩。它與普通函數(shù)不同的是，lambda必須使用尾置返回來指定返回類型蔽莱。
scala的匿名函數(shù)
scala的匿名函數(shù)使用非常的廣泛弟疆，這也是函數(shù)式語言的標(biāo)志之一。
scala中的集合類List有一個(gè)map方法盗冷，該方法接收一個(gè)函數(shù)作為參數(shù)怠苔，對List中的每一個(gè)元素使用參數(shù)指定的方法，此處非常適合用匿名函數(shù)仪糖，請看下面代碼：
val l=List(1,2,3)
l.map(i=>i+9)
上面代碼的第二行map函數(shù)的參數(shù)就是一個(gè)匿名函數(shù)柑司，或者是lambda表達(dá)式。
i=>i+9中的=>是參數(shù)列表和返回值的分隔符锅劝，如果少于兩個(gè)參數(shù)可以不寫小括號(hào)攒驰，后面部分是函數(shù)的返回值。如果函數(shù)體包含多行代碼可以使用花括號(hào)故爵，例如：
l.map((i)=>{
println("HI");
i+9
})
scala函數(shù)特有特性之調(diào)配curried
定義常規(guī)的scala add函數(shù):
def add (i:Int,j:Int):Int=i+j
這個(gè)函數(shù)太簡單了.
我們定義一個(gè)devide函數(shù)實(shí)現(xiàn)除法讼育，一般我們會(huì)這么寫：
// 多參數(shù)的寫法
def multiply(x: Int, y: Int) = x * y
Moses Schnfinkel 和 Gottlob Frege 發(fā)明了如下的表達(dá)方式:
def multiply(x: Int)(y: Int) => x * y
這個(gè)函數(shù)和上面的函數(shù)不同之處在于它的參數(shù)列表，是一個(gè)參數(shù)一個(gè)小括號(hào)稠集，不是把所有參數(shù)都放到一個(gè)括號(hào)內(nèi)的。下面我們通過實(shí)際的例子來理解scala的curried饥瓷。
我們要定義一個(gè)乘法函數(shù):
// 柯里化的寫法
def multiply(x: Int)(y: Int) = x * y
// 計(jì)算兩個(gè)數(shù)的乘積
multiply(6)(7)
multiply(6)返回的是函數(shù)(y: Int)=>6*y剥纷，再將這個(gè)函數(shù)應(yīng)用到7
(6 * y ) (7) = 42
最終得到結(jié)果42.
這就是scala的乘法函數(shù)了.
curried不太好理解，enjoy it!函數(shù)柯里化的主要功能是提供了強(qiáng)大的動(dòng)態(tài)函數(shù)創(chuàng)建方法呢铆，通過調(diào)用另一個(gè)函數(shù)并為它傳入要柯里化（currying）的函數(shù)和必要的參數(shù)而得到晦鞋。通俗點(diǎn)說就是利用已有的函數(shù)，再創(chuàng)建一個(gè)動(dòng)態(tài)的函數(shù)，該動(dòng)態(tài)函數(shù)內(nèi)部還是通過已有的函數(shù)來發(fā)生作用.
我們在想, 這些計(jì)算機(jī)科學(xué)家,數(shù)學(xué)家們腦子里天天都在想些什么? 盡發(fā)明一些普通人不好理解的概念. 但是, 存在即合理.既然這玩意存在著,必定表明必有其存在之意義.
多參數(shù)是個(gè)虛飾悠垛，不是編程語言的根本性的特質(zhì)线定。利用柯里化把某個(gè)函數(shù)參數(shù)單獨(dú)拎出來，提供更多用于類型推斷的信息.
在計(jì)算機(jī)科學(xué)中确买，柯里化（Currying）是把接受多個(gè)參數(shù)的函數(shù)變換成接受一個(gè)單一參數(shù)(最初函數(shù)的第一個(gè)參數(shù))的函數(shù)斤讥，并且返回接受余下的參數(shù)且返回結(jié)果的新函數(shù)的技術(shù)。這個(gè)技術(shù)由 Christopher Strachey 以邏輯學(xué)家 Haskell Curry 命名的湾趾，盡管它是 Moses Schnfinkel 和 Gottlob Frege 發(fā)明的芭商。
在直覺上，柯里化聲稱“如果你固定某些參數(shù)搀缠，你將得到接受余下參數(shù)的一個(gè)函數(shù)”铛楣。所以對于有兩個(gè)變量的函數(shù)yx，如果固定了 y = 2艺普，則得到有一個(gè)變量的函數(shù) 2x簸州。
在理論計(jì)算機(jī)科學(xué)中，柯里化提供了在簡單的理論模型中比如只接受一個(gè)單一參數(shù)的lambda 演算中研究帶有多個(gè)參數(shù)的函數(shù)的方式歧譬。
柯里化特性決定了它這應(yīng)用場景岸浑。提前把易變因素，傳參固定下來缴罗，生成一個(gè)更明確的應(yīng)用函數(shù)助琐。最典型的代表應(yīng)用，是bind函數(shù)用以固定this這個(gè)易變對象面氓。
Function.prototype.bind = function(context) {
var _this = this,
_args = Array.prototype.slice.call(arguments, 1);
return function() {
return _this.apply(context, _args.concat(Array.prototype.slice.call(arguments)))
}
}
柯里化其實(shí)本身是固定一個(gè)可以預(yù)期的參數(shù)兵钮，并返回一個(gè)特定的函數(shù)。這增加了函數(shù)的適用性舌界，但同時(shí)也降低了函數(shù)的適用范圍掘譬。這個(gè)思路有點(diǎn)像微積分里面的多重積分的處理方式.
柯里化的本質(zhì)就是函數(shù)參數(shù)單一化. 因?yàn)槎鄥?shù)有其問題.你在寫很多高階函數(shù)的時(shí)候，你都得考慮你的 參數(shù)函數(shù)f 在面臨各種傳參方式的情況下要怎么處理呻拌，這事兒是痛苦并且容易忘記的葱轩，因?yàn)槟惚静粦?yīng)該關(guān)心f的參數(shù)是些啥的！盲目地引入傳遞多參的機(jī)制藐握，其實(shí)是沒有把問題想明白的表現(xiàn)靴拱。語法層面支持的多參函數(shù)定義是一種扁平、簡單猾普、有效的方式袜炕，但是，當(dāng)程序需要做高階函數(shù)抽象的時(shí)候初家，這種方式會(huì)帶來麻煩偎窘。
通過組合型數(shù)據(jù)來傳遞復(fù)雜參數(shù)乌助，是一種很自然的方式，這種情況下并不需要刻意考慮“多參函數(shù)”這種問題陌知，并且這種方式對于做高階函數(shù)抽象非常友好他托。
科里化的方式定義多參函數(shù)，同樣是一種自然產(chǎn)生的方式仆葡，只要把函數(shù)當(dāng)做一等公民赏参，就會(huì)存在科里化的方式≌丬剑科里化的方式使得我們的函數(shù)可以更細(xì)粒度地方便地組合登刺。
但是，是否要使用科里化的方式嗡呼，卻是一件需要細(xì)細(xì)揣摩的事情纸俭。比如，我要定義一個(gè)rotate函數(shù)南窗，它接受一個(gè)二維向量的坐標(biāo)揍很，返回一個(gè)逆時(shí)針旋轉(zhuǎn)九十度后的向量坐標(biāo)，那么你可能會(huì)把它定義成
rotate = (\x -> (\y -> (y, -x)))
或者
rotate = (\(x, y) -> (y, -x))
你覺得哪種定義方式比較好呢万伤？ 在這個(gè)例子里窒悔，顯然是第二種定義方式比較好，
- 一來敌买，二維向量的兩個(gè)坐標(biāo)通常是成對出現(xiàn)的简珠，很少會(huì)有“部分應(yīng)用”的需要，所以也就自然用不到科里化的任何好處虹钮；
- 二來聋庵，當(dāng)你需要把一個(gè)向量rotate兩次的時(shí)候，科里化版本就會(huì)體現(xiàn)出異常的麻煩了芙粱。
所以祭玉，結(jié)論是：
如果某些參數(shù)在大部分情況下，總是需要同時(shí)給出春畔，才具有真實(shí)的意義脱货，那么應(yīng)該把這些參數(shù)組合成一個(gè)組合型參數(shù)來處理，而不應(yīng)該科里化律姨。
如果要定義的多參函數(shù)是一個(gè)閉合函數(shù)振峻，那么它是很可能需要被多次應(yīng)用的，這種情況下择份，應(yīng)該用組合型參數(shù)的方式來處理铺韧。
如果先指定某一些參數(shù)就有明確的意義，那么就應(yīng)該用科里化的方式來處理缓淹。
在F#里哈打，各種函數(shù)的signature 都是 int -> int -> int ->什么的……
what does that even mean??
Currying和partial application對于functional programming有怎樣的真正的威力？
currying和partial application會(huì)affect performance嗎讯壶？
匿名函數(shù)
函數(shù)不一定需要名稱：
(x: Double) => 3 * x // 該匿名函數(shù)將傳給它的參數(shù)乘3
可以將匿名函數(shù)賦值給變量料仗，也可以當(dāng)參數(shù)傳遞。
高階函數(shù)(Higher-order function)
變量可以指向函數(shù)
以Python內(nèi)置的求絕對值的函數(shù)abs()為例伏蚊，調(diào)用該函數(shù)用以下代碼：
abs(-10)
10
但是立轧，如果只寫abs呢？
abs
<built-in function abs>
可見躏吊，abs(-10)是函數(shù)調(diào)用氛改，而abs是函數(shù)本身。
要獲得函數(shù)調(diào)用結(jié)果比伏，我們可以把結(jié)果賦值給變量：
x = abs(-10)
x
10
但是胜卤，如果把函數(shù)本身賦值給變量呢？
f = abs
f
<built-in function abs>
結(jié)論：函數(shù)本身也可以賦值給變量赁项，即：變量可以指向函數(shù)葛躏。
如果一個(gè)變量指向了一個(gè)函數(shù)，那么悠菜，可否通過該變量來調(diào)用這個(gè)函數(shù)舰攒？用代碼驗(yàn)證一下：
f = abs
f(-10)
10
成功！說明變量f現(xiàn)在已經(jīng)指向了abs函數(shù)本身悔醋。
函數(shù)名也是變量
那么函數(shù)名是什么呢摩窃？函數(shù)名其實(shí)就是指向函數(shù)的變量！對于abs()這個(gè)函數(shù)芬骄，完全可以把函數(shù)名abs看成變量猾愿，它指向一個(gè)可以計(jì)算絕對值的函數(shù)！
高階函數(shù)
既然變量可以指向函數(shù)德玫，函數(shù)的參數(shù)能接收變量匪蟀，那么一個(gè)函數(shù)就可以接收另一個(gè)函數(shù)作為參數(shù)，這種函數(shù)就稱之為高階函數(shù)宰僧。
一個(gè)最簡單的高階函數(shù)：
def add(x, y, f):
return f(x) + f(y)
當(dāng)我們調(diào)用add(-5, 6, abs)時(shí)材彪，參數(shù)x，y和f分別接收-5琴儿，6和abs段化，根據(jù)函數(shù)定義，我們可以推導(dǎo)計(jì)算過程為：
x ==> -5
y ==> 6
f ==> abs
f(x) + f(y) ==> abs(-5) + abs(6) ==> 11
用代碼驗(yàn)證一下：
add(-5, 6, abs)
11
編寫高階函數(shù)造成，就是讓函數(shù)的參數(shù)能夠接收別的函數(shù)显熏。
把函數(shù)作為參數(shù)傳入，這樣的函數(shù)稱為高階函數(shù)晒屎，函數(shù)式編程就是指這種高度抽象的編程范式。
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>
