# function order

又要帶新人了，回顧一下 [What Color is Your Function](https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/) ，想起一般 web 仔並不知道怎麼「計算」 function 的 order 。這裡就來簡單介紹一下。

每次聽到人說 higher-order function 時，從字面會引出兩個問題：

- "order" 怎麼算？
- "higher" 是 higher than 什麼？

在程式語言理論裡， function 的 order 是這樣定義的：

- primitive 型別（例如 `R` ）的 order 是 `0`
- function 型別 `X -> Y` 的 order 是 `order(X -> Y) = max(order(X) + 1, order(Y))`

先來算算，一個一般 function 的 order 是多少？

order(R -> R)
= max(order(R) + 1, order(R))
= max(0 + 1, 0)
= 1

這是一個從數字到數字的 function ， order 是 `1` 。

再算算，吃 function 當參數的 function ， order 是多少？

order((R -> R) -> R)
= max(order(R -> R) + 1, order(R))
= max(1 + 1, 0)
= 2

這種就是真正的 higher-order function ， order 是 `2` 。

最後算算 curry function 的 order 。

一般多參數的 function `(R, R) -> R` 在 curry 後會變成 `R -> (R -> R)` ，也就是 `R -> R -> R` ，注意它跟前面的 `(R -> R) -> R` 不一樣喔。

order(R -> R -> R)
= max(order(R) + 1, order(R -> R))
= max(0 + 1, 1)
= 1

現在可以回答第二個問題了， higher-order 是 higher than 什麼？很明顯是 higher than `1` 。所以一般的 function 就算 curry 過了，還是 order 為 `1` 的 function ，只有把 function 當參數的，才能說是 higher-order function ，你學會了嗎？

---

補充：

fb 上的[林先生提到](https://www.facebook.com/groups/f2e.tw/posts/9815821941788416/?comment_id=9835650613138882&reply_comment_id=9838850409485569)，他查到的 higher-order function 定義是：

> a function that either takes one or more functions as arguments or "returns a function as its result"

本以為是 web 圈傳承不力，才讓這種 curry 會改變 order 的奇怪定義一直流傳。但現在只要提到 higher-order function 都是這樣寫。

記得當初是在一本講 System Fω 的書上看到這個式子的，書中用來計算 type operator （也就是 type function ）的 order 。 `(* -> *) -> *` 才算是 higher-order type 。

現在網上找不到該書了，但如果搜尋 Type systems for programming languages ，在 123 頁附近會看到類似的定義。

奇怪的事情來了，怎麼在討論 type function 時， order 不會因為 curry 而改變，但到了一般 function 時， order 就會被 curry 影響了？

也許當初實作圈從學術圈引進 higher-order 這個詞的時候，就誤用了它，才有這種不一致的現象。