在计算机科学 中,柯里化 (英語:Currying ),又译为卡瑞化 或加里化 ,是把接受多个参数 的函数 变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数而且返回结果的新函数的技术。这个技术由克里斯托弗·斯特雷奇 以逻辑学家哈斯凱爾·加里 命名的,尽管它是Moses Schönfinkel 和戈特洛布·弗雷格 发明的。
在直觉上,柯里化声称「如果你固定某些参数,你将得到接受余下参数的一个函数」。所以对于有两个变量的函数
y
x
{\displaystyle y^{x}}
,如果固定了
y
=
2
{\displaystyle y=2}
,则得到有一个变量的函数
2
x
{\displaystyle 2^{x}}
。
在理论计算机科学 中,柯里化提供了在简单的理论模型中,比如:只接受一个单一参数的lambda演算 中,研究带有多个参数的函数的方式。
函数柯里化的对偶是Uncurrying ,一种使用匿名单参数函数来实现多参数函数的方法。例如:
var foo = function ( a ) {
return function ( b ) {
return a * a + b * b ;
}
}
这样调用上述函数:(foo(3))(4)
,或直接foo(3)(4)
。
動机
柯里化是一種處理函數中附有多個參數的方法,並在只允許單一參數的框架中使用這些函數。例如,一些分析技術只能用於具有單一參數的函數。現實中的函數往往有更多的參數。弗雷格表明,為單一參數情況提供解決方案已經足夠了,因為可以將具有多個參數的函數轉換為一個單參數的函數鏈。這種轉變是現在被稱為“柯里化”的過程。
在數學分析或計算機編程中,所有可能遇到的“普通”函數都可以被使用。但是,有些類別不可能使用柯里化;確實允許柯里化的最普通的類別是閉合的monoidal類別。一些編程語言幾乎總是使用curried函數來實現多個參數;值得注意的例子是 ML 和 Haskell,在這兩種情況下,所有函數都只有一個參數。這個屬性是從lambda演算繼承而來的,其中多參數的函數通常以柯里形式表示。
柯里化與部份求值是相關的,但不完全相同。在實作中,閉包 的編程技術可以用來執行部份求值和一種捲曲,通過將參數隱藏在使用柯里化函數的環境中。
部份求值
柯里化有如倣效接受多個參數的函數評估過程,若以紙筆手工作業,要週密地寫出評估過程中的所有步驟。
例如,給定某一函數
f
(
x
,
y
)
=
y
/
x
{\displaystyle f(x,y)=y/x}
:
要評估
f
(
2
,
3
)
{\displaystyle f(2,3)}
時,首先以
2
{\displaystyle 2}
代入
x
{\displaystyle x}
因為結果會是函數
y
{\displaystyle y}
的輸出,所以可定義為一個新函數
g
(
y
)
{\displaystyle g(y)}
為
g
(
y
)
=
f
(
2
,
y
)
=
y
/
2
{\displaystyle g(y)=f(2,y)=y/2}
接下來將
y
{\displaystyle y}
參數以
3
{\displaystyle 3}
替換,產生了
g
(
3
)
=
f
(
2
,
3
)
=
3
/
2
{\displaystyle g(3)=f(2,3)=3/2}
在紙上使用傳統符號,上述過程通常是一次代入兩個參數
x
,
y
{\displaystyle x,y}
的值就完成了。
而每個參數其實是依次序替換,在每一步替換的中介函數只能接受單一個參數。
以上範例有點缺陷,雖然應用上類似函數的部份求值。對柯里化的過程來說,但並非完全相同(見下文)。
示例
柯里化(Currying)是產生一系列連鎖函數的一種方法,其中每個函數只有一個參數。藉由另一個柯里化之後的新函數,傳回其它剩餘參數的功能,將原本以多個參數應用的函數“隱藏”起來,如下所述。
給定帶有 x 和y 兩個參數的函數 f ,也就是,
f
(
x
,
y
)
{\displaystyle f(x,y)}
然後可以構造一個與原來的 f 相關的新函數 h x 。這個函數的形式只有單一參數 y ,並給定該參數,則 h x 返回 f (x ,y )。也就是,
h
x
(
y
)
=
f
(
x
,
y
)
{\displaystyle h_{x}(y)=f(x,y)}
.
在這裡應該了解 h 上的下標 x 是當成隱藏作用的符號設施,或者說把一個參數放在一邊,使原函數變成只帶一個參數。柯里化(Currying)提供了符號標記上的技巧,將函數因而抽象化。
這個技巧要利用 map 或函數構造子。符號
↦
{\displaystyle \mapsto }
用於表示抽象化的實際行為。
例如以
y
↦
z
{\displaystyle y\mapsto z}
這樣子來表示:某個函數將一個參數 y 映射到結果 z 。
然後考慮從 h x 記號中刪掉下標 x ,就得到了一個 柯里化表示 的代表符 h ;
而成為另一個給予 x 能把其“值”傳回的不同函數 h x ;它恰好是一個函數構造,其映射過程
可以用
y
↦
f
(
x
,
y
)
{\displaystyle y\mapsto f(x,y)}
語句來表達,或者描述為一個將參數 y 映射到結果 z 的函數。也就是,
h
x
=
(
y
↦
f
(
x
,
y
)
)
{\displaystyle h_{x}=(y\mapsto f(x,y))}
,
用不同代表符號(但意義相同)來看,
h
(
x
)
=
(
y
↦
f
(
x
,
y
)
)
{\displaystyle h(x)=(y\mapsto f(x,y))}
函數 h 本身現在可用 h x 相似的表示,並寫成
h
=
(
x
↦
(
y
↦
f
(
x
,
y
)
)
)
{\displaystyle h=(x\mapsto (y\mapsto f(x,y)))}
能夠負責並處理對開頭涉及 的函數參數。鑑於上述情況,柯里化的行為可被理解為一函數,給予某些任意的 f ,即涉及相關的 h 函數可以產生 h 的所述功能;論及 f 。也就是,
curry
=
(
f
↦
h
)
{\displaystyle {\text{curry}}=(f\mapsto h)}
或相當於
curry
(
f
)
=
h
{\displaystyle {\text{curry}}(f)=h}
這說明了柯里化的基本性質:它是參數重新定位的機制,將原函數中的每一個參數綁定到不同的新函數,而返回另一個相關的函數。也就是給定函數 f 原本傳回一個“值”,則柯里化“構造”了一個新函數 h 而傳回的是涉及 f 的函數。另一種理解柯里化的不同方式,則意識到它只是一個代數遊戲,符號的句法重新排列。人們不會問這些符號的“含義”是什麼; 一個人只同意他們的重新排列規則。 要看出這一點,注意原來的函數 f 本身可能寫成
f
=
(
(
x
,
y
)
↦
f
(
x
,
y
)
)
{\displaystyle f=((x,y)\mapsto f(x,y))}
與上面的函數 h 互相比較,可以看出這兩種形式都重新排列了括號,以及將逗號轉換為箭頭。回到前面的例子,
f
(
x
,
y
)
=
y
x
{\displaystyle f(x,y)={\frac {y}{x}}}
然後有,
g
=
h
2
=
h
(
2
)
=
(
y
↦
f
(
2
,
y
)
)
{\displaystyle g=h_{2}=h(2)=(y\mapsto f(2,y))}
作為上例柯里化的相等物。 添加一個參數到 g 然後給出
g
(
y
)
=
h
2
(
y
)
=
h
(
2
)
(
y
)
=
f
(
2
,
y
)
=
y
2
{\displaystyle g(y)=h_{2}(y)=h(2)(y)=f(2,y)={\frac {y}{2}}}
以及
g
(
3
)
=
h
2
(
3
)
=
h
(
2
)
(
3
)
=
f
(
2
,
3
)
=
3
2
.
{\displaystyle g(3)=h_{2}(3)=h(2)(3)=f(2,3)={\frac {3}{2}}.}
剝除參數的方法或許更容易地理解,例如有四個參數的函數:
f
(
x
,
y
,
z
,
w
)
{\displaystyle f(x,y,z,w)}
經過上述操作,導出為形式
h
x
=
(
(
y
,
z
,
w
)
↦
f
(
x
,
y
,
z
,
w
)
)
{\displaystyle h_{x}=((y,z,w)\mapsto f(x,y,z,w))}
這應用到三元組之上可得到
h
x
(
y
,
z
,
w
)
=
f
(
x
,
y
,
z
,
w
)
{\displaystyle h_{x}(y,z,w)=f(x,y,z,w)}
.
然後適當地寫成柯里化形式
h
=
(
x
↦
(
(
y
,
z
,
w
)
↦
f
(
x
,
y
,
z
,
w
)
)
)
{\displaystyle h=(x\mapsto ((y,z,w)\mapsto f(x,y,z,w)))}
一直繼續玩著重新安排符號的代數遊戲,最終導出了完全的柯里化形式
x
↦
(
y
↦
(
z
↦
(
w
↦
f
(
x
,
y
,
z
,
w
)
)
)
)
{\displaystyle x\mapsto (y\mapsto (z\mapsto (w\mapsto f(x,y,z,w))))}
對箭頭運算符一般理解是右結合的,所以上面大部份的括號是多餘的,在意義不變的情況下可以刪除掉。因此,寫成了很常見的
x
↦
y
↦
z
↦
w
↦
f
(
x
,
y
,
z
,
w
)
{\displaystyle x\mapsto y\mapsto z\mapsto w\mapsto f(x,y,z,w)}
也就是函數 f 完全的柯里化形式。
定義
從非形式的一般定義開始,柯里化是最容易理解的,然後再塑造它以適應許多不同的領域。
首先說明一些符號的標記法。
f
:
X
→
Y
{\displaystyle f\colon X\to Y}
表示從
X
{\displaystyle X}
映射到
Y
{\displaystyle Y}
的函數
f
{\displaystyle f}
。
X
→
Y
{\displaystyle X\to Y}
表示從
X
{\displaystyle X}
到
Y
{\displaystyle Y}
的所有函數。
這裡,
X
{\displaystyle X}
和
Y
{\displaystyle Y}
可以是集合、或者是類型,或者它們可以是其它型別的物件,如下所述。
令
X
×
Y
{\displaystyle X\times Y}
表示有序對,即笛卡爾乘積。
給定類型為
f
:
(
X
×
Y
)
→
Z
{\displaystyle f\colon (X\times Y)\to Z}
的函數
f
{\displaystyle f}
,柯里化 即構造或創建一個新的函數:
curry
(
f
)
:
X
→
(
Y
→
Z
)
{\displaystyle {\text{curry}}(f)\colon X\to (Y\to Z)}
也就是說,
curry
(
f
)
{\displaystyle {\text{curry}}(f)}
取一個類型為
X
{\displaystyle X}
的參數,並返回一個類型為
Y
→
Z
{\displaystyle Y\to Z}
的函數。Uncurrying 則相反。
集合論
數理領域的集合論 中,符號
Y
X
{\displaystyle Y^{X}}
用於表示從
X
{\displaystyle X}
集合映射到
Y
{\displaystyle Y}
集合的函數。柯里化是指從
B
×
C
{\displaystyle B\times C}
映射到
A
{\displaystyle A}
的
A
B
×
C
{\displaystyle A^{B\times C}}
函數,和從
B
{\displaystyle B}
之中映射,由
C
{\displaystyle C}
到
A
{\displaystyle A}
的
(
A
C
)
B
{\displaystyle \left(A^{C}\right)^{B}}
函數,這些組合的自然變換 。事實上是這種自然變換關係,闡述了出現在集合論中的指數符號。在集合的範疇論中
Y
X
{\displaystyle Y^{X}}
被稱為指數物件。
函數空間
在函數空間理論中,如泛函分析或拓撲的同倫,人們通常對拓撲空間之間的連續函數感興趣。從
X
{\displaystyle X}
到
Y
{\displaystyle Y}
所有的 函數集,寫成
Hom
(
X
,
Y
)
{\displaystyle {\text{Hom}}(X,Y)}
(Hom函子)並使用
Y
X
{\displaystyle Y^{X}}
來表示連續函數的子集。在這裡的
curry
{\displaystyle {\text{curry}}}
是一一對應的
curry
:
Hom
(
X
×
Y
,
Z
)
→
Hom
(
X
,
Hom
(
Y
,
Z
)
)
,
{\displaystyle {\text{curry}}:{\text{Hom}}(X\times Y,Z)\to {\text{Hom}}(X,{\text{Hom}}(Y,Z)),}
而 uncurrying 是反向的映射。如果從
X
{\displaystyle X}
到
Y
{\displaystyle Y}
的
Y
X
{\displaystyle Y^{X}}
集合為連續函數
給出了紧致开拓扑 緊緻開拓撲,而且如果
Y
{\displaystyle Y}
空間是局部豪斯多夫緊緻的 ,那麼
curry
{\displaystyle {\text{curry}}}
是一個連續函數,也是同胚。儘管可能有更多情況,當
X
{\displaystyle X}
,
Y
{\displaystyle Y}
和
Y
X
{\displaystyle Y^{X}}
是緊生成 的時候,情況都是相同的。
這結果發展成了指數表示法
curry
:
Z
X
×
Y
→
(
Z
Y
)
X
{\displaystyle {\text{curry}}:Z^{X\times Y}\to (Z^{Y})^{X}}
有時稱為指數法則 。 而有用的推論是,一個函數若且唯若其柯里化形式是連續時,它才是連續的。另一個重要的結果是應用程序映射(在這種情況通常稱為“評估”)是連續的(注意eval
在計算機科學中的概念與此嚴格不同)。也就是說,
eval
:
Y
X
×
X
→
Y
(
f
,
x
)
↦
f
(
x
)
{\displaystyle {\begin{aligned}&&{\text{eval}}:Y^{X}\times X\to Y\\&&(f,x)\mapsto f(x)\end{aligned}}}
當
Y
X
{\displaystyle Y^{X}}
是緊緻開放的,而且
Y
{\displaystyle Y}
局部緊緻的豪斯多夫時,那上述式子是連續的。這兩個結果對於確立同倫的連續性非常重要,亦即當
X
{\displaystyle X}
是單位區間
I
{\displaystyle I}
,所以
Z
I
×
Y
≅
(
Z
Y
)
I
{\displaystyle Z^{I\times Y}\cong (Z^{Y})^{I}}
能想成
就是從
Y
{\displaystyle Y}
到
Z
{\displaystyle Z}
的兩個函數的同倫,或者等價地,是
Z
Y
{\displaystyle Z^{Y}}
中的單個(連續)路徑。
代數拓撲
域理論
在序理論對於偏序集合的格,當格是給定的 Scott拓撲時,則
curry
{\displaystyle {\text{curry}}}
會是一個連續函數。為了提供 lambda演算的語義學,要先研究 Scott連續函數(因為普通集合理論不適合這樣做)。更一般地說,現在研究 Scott連續函數的域理論中,含括了計算機算法的指稱語義學。
請注意,Scott拓撲結構與拓撲空間範疇中可能遇到的許多常見拓撲結構完全不同; Scott拓撲通常更為精巧,而不是很嚴審的。連續性的概念使它出現在同倫類型理論中,粗略地說,兩個計算機程序可以被認為是同倫的,如果他們可以“連續”地從一個重構到另一個,即計算得出相同的結果。
Lambda演算
型別理論
在型別理論中,對於計算機科學型別系統的一般概念,被形式化為一個具體的代數類型。例如寫為
f
:
X
→
Y
{\displaystyle f\colon X\to Y}
時,
意指那個
X
{\displaystyle X}
和
Y
{\displaystyle Y}
是一種類型,而
→
{\displaystyle \to }
箭頭符號代表是類型構造函數,特別是指函數類型或箭頭類型。類似地,類型的笛卡爾積是由
×
{\displaystyle \times }
構造函數,而建構出的複合結構類型。
型別理論方法可以用 ML編程語言表達,而受啟發衍生出的語言有:CaML,Haskell和F#。
邏輯
在Curry-Howard 下,柯里化和对偶柯里化的存在相當於邏輯定理
(
A
∧
B
)
→
C
⇔
A
→
(
B
→
C
)
{\displaystyle (A\land B)\to C\Leftrightarrow A\to (B\to C)}
,因為多元组 (型別積, product type)對應於邏輯中的且連接 ,而函數類型對應於蕴涵 。
範疇論
历史
「科里化」一词由克里斯托弗·斯特雷奇 创造,以逻辑学家哈斯凱爾·加里 命名。另外一个名词 "Schönfinkelisation" 则以Moses Schönfinkel命名。在数学历史中,这个原理可以追溯到1893年戈特洛布·弗雷格 的工作。
参见