计算机科学中,柯里化(英語:Currying),又译为卡瑞化加里化,是把接受多个参数函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数而且返回结果的新函数的技术。这个技术由克里斯托弗·斯特雷奇以逻辑学家哈斯凱爾·加里命名的,尽管它是Moses Schönfinkel戈特洛布·弗雷格发明的。

在直觉上,柯里化声称「如果你固定某些参数,你将得到接受余下参数的一个函数」。所以对于有两个变量的函数,如果固定了,则得到有一个变量的函数

理论计算机科学中,柯里化提供了在简单的理论模型中,比如:只接受一个单一参数的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演算繼承而來的,其中多參數的函數通常以柯里形式表示。

柯里化與部份求值是相關的,但不完全相同。在實作中,閉包的編程技術可以用來執行部份求值和一種捲曲,通過將參數隱藏在使用柯里化函數的環境中。

部份求值

编辑

柯里化有如倣效接受多個參數的函數評估過程,若以紙筆手工作業,要週密地寫出評估過程中的所有步驟。

例如,給定某一函數  :

要評估   時,首先以  代入  
因為結果會是函數  的輸出,所以可定義為一個新函數   
接下來將  參數以  替換,產生了  

在紙上使用傳統符號,上述過程通常是一次代入兩個參數  的值就完成了。
而每個參數其實是依次序替換,在每一步替換的中介函數只能接受單一個參數。

以上範例有點缺陷,雖然應用上類似函數的部份求值。對柯里化的過程來說,但並非完全相同(見下文)。

示例

编辑

柯里化(Currying)是產生一系列連鎖函數的一種方法,其中每個函數只有一個參數。藉由另一個柯里化之後的新函數,傳回其它剩餘參數的功能,將原本以多個參數應用的函數“隱藏”起來,如下所述。

給定帶有 xy兩個參數的函數 f,也就是,

 

然後可以構造一個與原來的 f 相關的新函數 hx。這個函數的形式只有單一參數 y,並給定該參數,則 hx 返回 f(x,y)。也就是,

 .

在這裡應該了解 h上的下標 x是當成隱藏作用的符號設施,或者說把一個參數放在一邊,使原函數變成只帶一個參數。柯里化(Currying)提供了符號標記上的技巧,將函數因而抽象化。

這個技巧要利用 map或函數構造子。符號  用於表示抽象化的實際行為。 例如以   這樣子來表示:某個函數將一個參數 y映射到結果 z

然後考慮從 hx 記號中刪掉下標 x,就得到了一個 柯里化表示的代表符 h; 而成為另一個給予 x 能把其“值”傳回的不同函數 hx;它恰好是一個函數構造,其映射過程 可以用   語句來表達,或者描述為一個將參數 y映射到結果 z的函數。也就是,

 ,

用不同代表符號(但意義相同)來看,

 

函數 h 本身現在可用 hx 相似的表示,並寫成

 

能夠負責並處理對開頭涉及的函數參數。鑑於上述情況,柯里化的行為可被理解為一函數,給予某些任意的 f,即涉及相關的 h函數可以產生 h的所述功能;論及 f。也就是,

 

或相當於

 

這說明了柯里化的基本性質:它是參數重新定位的機制,將原函數中的每一個參數綁定到不同的新函數,而返回另一個相關的函數。也就是給定函數 f原本傳回一個“值”,則柯里化“構造”了一個新函數 h 而傳回的是涉及 f的函數。另一種理解柯里化的不同方式,則意識到它只是一個代數遊戲,符號的句法重新排列。人們不會問這些符號的“含義”是什麼; 一個人只同意他們的重新排列規則。 要看出這一點,注意原來的函數 f本身可能寫成

 

與上面的函數 h互相比較,可以看出這兩種形式都重新排列了括號,以及將逗號轉換為箭頭。回到前面的例子,

 

然後有,

 

作為上例柯里化的相等物。 添加一個參數到 g 然後給出

 

以及

 

剝除參數的方法或許更容易地理解,例如有四個參數的函數:

 

經過上述操作,導出為形式

 

這應用到三元組之上可得到

 .

然後適當地寫成柯里化形式

 

一直繼續玩著重新安排符號的代數遊戲,最終導出了完全的柯里化形式

 

對箭頭運算符一般理解是右結合的,所以上面大部份的括號是多餘的,在意義不變的情況下可以刪除掉。因此,寫成了很常見的

 

也就是函數 f完全的柯里化形式。

定義

编辑

從非形式的一般定義開始,柯里化是最容易理解的,然後再塑造它以適應許多不同的領域。
首先說明一些符號的標記法。

  表示從   映射到   的函數 

  表示從    的所有函數。

這裡,   可以是集合、或者是類型,或者它們可以是其它型別的物件,如下所述。

 表示有序對,即笛卡爾乘積。

給定類型為  的函數 柯里化即構造或創建一個新的函數:

 

也就是說, 取一個類型為  的參數,並返回一個類型為  的函數。Uncurrying則相反。

集合論

编辑

數理領域的集合論中,符號  用於表示從  集合映射到  集合的函數。柯里化是指從  映射到   函數,和從  之中映射,由    函數,這些組合的自然變換。事實上是這種自然變換關係,闡述了出現在集合論中的指數符號。在集合的範疇論中  被稱為指數物件。

函數空間

编辑

在函數空間理論中,如泛函分析或拓撲的同倫,人們通常對拓撲空間之間的連續函數感興趣。從    所有的函數集,寫成  (Hom函子)並使用   來表示連續函數的子集。在這裡的  一一對應的

 

uncurrying 是反向的映射。如果從    集合為連續函數 給出了紧致开拓扑緊緻開拓撲,而且如果  空間是局部豪斯多夫緊緻的,那麼  是一個連續函數,也是同胚。儘管可能有更多情況,當    緊生成的時候,情況都是相同的。

這結果發展成了指數表示法

 

有時稱為指數法則。 而有用的推論是,一個函數若且唯若其柯里化形式是連續時,它才是連續的。另一個重要的結果是應用程序映射(在這種情況通常稱為“評估”)是連續的(注意eval在計算機科學中的概念與此嚴格不同)。也就是說,

 

 是緊緻開放的,而且  局部緊緻的豪斯多夫時,那上述式子是連續的。這兩個結果對於確立同倫的連續性非常重要,亦即當  是單位區間  ,所以  能想成 就是從   的兩個函數的同倫,或者等價地,是  中的單個(連續)路徑。

代數拓撲

编辑

域理論

编辑

在序理論對於偏序集合的格,當格是給定的 Scott拓撲時,則  會是一個連續函數。為了提供 lambda演算的語義學,要先研究 Scott連續函數(因為普通集合理論不適合這樣做)。更一般地說,現在研究 Scott連續函數的域理論中,含括了計算機算法的指稱語義學。

請注意,Scott拓撲結構與拓撲空間範疇中可能遇到的許多常見拓撲結構完全不同; Scott拓撲通常更為精巧,而不是很嚴審的。連續性的概念使它出現在同倫類型理論中,粗略地說,兩個計算機程序可以被認為是同倫的,如果他們可以“連續”地從一個重構到另一個,即計算得出相同的結果。

Lambda演算

编辑

型別理論

编辑

在型別理論中,對於計算機科學型別系統的一般概念,被形式化為一個具體的代數類型。例如寫為  時, 意指那個   是一種類型,而   箭頭符號代表是類型構造函數,特別是指函數類型或箭頭類型。類似地,類型的笛卡爾積是由  構造函數,而建構出的複合結構類型。

型別理論方法可以用 ML編程語言表達,而受啟發衍生出的語言有:CaML,Haskell和F#。

邏輯

编辑

Curry-Howard下,柯里化和对偶柯里化的存在相當於邏輯定理 ,因為多元组(型別積, product type)對應於邏輯中的且連接,而函數類型對應於蕴涵

範疇論

编辑

历史

编辑

「科里化」一词由克里斯托弗·斯特雷奇创造,以逻辑学家哈斯凱爾·加里命名。另外一个名词 "Schönfinkelisation" 则以Moses Schönfinkel命名。在数学历史中,这个原理可以追溯到1893年戈特洛布·弗雷格的工作。

参见

编辑