1 值、函數、與定義

1.4 函數合成

拿到一個函數 f，我們能做的基本操作包括把 f 作用在某個參數上、 把 f 傳給別的函數... 此外，另一個常用的基本操作是將 f 和別的函數合成(compose) 為一個新函數。 Robert Gl\"{u}ck 認為函數上應有三個基本操作： 函數應用、函數合成、以及求一個函數的反函數。 前兩者已經提到，第三者則是大部分語言欠缺的。 「合成」運算子在 Haskell 中寫成(.). 這個運算子的形式定義如下（我們先看定義本體，待會兒再看型別）：

(f . g) x  = f (g x)

若用口語說，f . g 是將 f 和 g兩個函數「串起來」得到的新函數： 輸入 x 先丟給 g, 後者算出的結果再傳給 f.

例 1.7

square . double 與 double . square 都是由 Int 到 Int 的函數. 直覺上，前者把輸入先給 double, 其結果再給 square。 後者則反過來。 如何了解它們的行為？既然它們是函數，我們便餵給它們一個參數，看看會展開成什麼！ 兩者分別展開如下：

   (square . double) x
=    {- (.) 的定義 -}
   square (double x)
=  (x + x) * (x + x) 

   (double . square) x
=    {- (.) 的定義 -}
   double (square x)
=  (x * x) + (x * x)

所以，如果輸入為 x, (square . double) x 計算 $(2x)^2$; (double . square) x 則是 $2x^2$.

但，並不是所有函數都可以串在一起： f . g 之中，g 的輸出型別和 f 的輸入型別必須一致才行。 運算子 (.) 包括型別的完整定義為：

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x  = f (g x)

如果 g 的型別是 a -> b, f 的型別是 b -> c, 將他們串接起來後， 便得到一個型別為 a -> c 的函數。

有了(.), 函數 twice 可以定義如下：

twice    :: (a -> a) -> (a -> a)
twice f  = f . f

確實，根據 (.) 的定義，twice f x = (f . f) x = f (f x)，和 twice 原來的定義相同。

為了討論函數合成的性質，我們先介紹一個函數 id:

id :: a -> a
id x = x

它又稱作單位函數或恆等函數。 這是一個似乎沒有在做什麼的函數：給任何輸入，id 都原封不動地把它送到輸出 --- 這也反映在他的型別 a -> a 上。 這個函數有什麼重要性呢？ 原來，(.) 滿足結合律，並且以 id 為單位元素（這也是「單位函數」這名字的由來）：

用數學術語來說的話，id 與 (.) 形成一個幺半群 (monoid)。 函數 id 的重要性就如同 0 在代數中的重要性（0 與 (+) 也是一個幺半群）。我們在許多計算、證明中都會見到它。

以下我們試著證明 (.) 的結合律。我們想論證 (f . g) . h = f . (g . h)，但該如何下手？ 該等式的等號左右兩邊都是函數。 當我們說兩個整數相等，意思很清楚：如果等號左邊是 0, 右邊也是 0; 如果左邊是 1, 右邊也是 1... 但說兩個函數「相等」，是什麼意思呢？

定義 1.8 外延相等(extensional equality)

給定兩個型別相同的函數 f 和 g, 當我們說它們外延相等(extensionally equal)， 意思是給任何一個輸入，f 和 g 都算出相等的輸出。也就是： (∀ x. f x = g x).

本書中，當我們寫兩個函數相等(f = g)時，指的便是外延相等，除非例外註明。

在外延相等的假設下，證明 (f . g) . h = f . (g . h) 也就是證明對任何一個 x, ((f . g) . h) x = (f . (g . h)) x 均成立. 我們推論如下：

  ((f . g) . h) x
=  {- (.) 的定義 -}
  (f . g) (h x)
=  {- (.) 的定義 -}
  f (g (h x))
=  {- (.) 的定義 -}
  f ((g . h) x) 
=  {- (.) 的定義 -}
  (f . (g . h)) x

既然 (f . g) . h = f . (g . h)，我們便可統一寫成 f . g . h, 不用加括號了。

練習 1.6

證明 id . f = f = f . id.

答案

根據外延相等，我們需證明 (∀ x . id . f = f = f . id). 推論如下：

   (id . f) x
=    {- (.) 之定義 -}
   id (f x)
=    {- id 之定義 -}
   f x
=    {- id 之定義 -}
   f (id x)
=    {- (.) 之定義 -}
   (f . id) x

合成 (.) 也是一個中序運算子。和其他中序運算子一樣，其優先性低於函數應用。 因此，當我們寫 f . g x, 指的是 f . (g x) --- g x 為一個函數， 和 f 合成，而不是 (f . g) x （後者根據 (.) 的定義，是 f (g x)）。

答案

前三者都是 Int -> Int。

  1. 根據 (.) 的定義，(square . smaller 3) x = square (smaller 3 x). 因此 square . smaller 3 是一個函數，將其輸入和 3 比較，取較小者的平方。

  2. (smaller 3 . square) x = smaller 3 (square x). 因此它讀入 x, 並在 3 或 x^2 之中選較小的那個。

  3. smaller (square 3) 是一個函數，讀入 x 之後，選擇 x 與 3^2 之中較小的那個。

  4. smaller . square 3 有型別錯誤： square 3 不是一個函數（而是一個整數）， 無法和 smaller 合成。

函數應用運算子   本書中有些時候會將許多函數組合成一串，例如 square . double . (+1) . smaller 3 。由於函數應用的優先順序比一般二元運算元高，把上述式子應用在參數 5 之上時得寫成

  (square . double . (+1) . smaller 7) 5

（這個式子的值為 $(2\times(5+1))^2$。） 每次都得加一對括號似乎有些累贅。Haskell 另有一個運算子($), 唸作 ``apply'', 代表函數應用： 

($) :: (a -> b) -> a -> b
f $ x = f x

f $ x 和 f x 意思一樣。那麼我們為何需要這個運算子呢？原因之一是 ($) 的優先度比 (.) 低，因此上式可省去括號改寫如下：

  square . double . (+1) . smaller 7 $ 5

運算子 ($) 的另一個重要意義是：「函數應用」這個動作有了符號， 成為可以獨立討論的事物。例如，($) 可以當作參數。 一個這麼做的例子是習題 1.11 。

常量函數   既然介紹了 id, 本節也順便介紹一個以後將使用到的基本組件。 給定 x 之後，函數 const x 是一個 不論拿到什麼函數，都傳回 x的函數。 函數 const 的定義如下：

const :: a -> b -> a
const x y = x

第1.1 節開頭的範例 three 可定義為 three = const 3.

「無論如何都傳回 x」聽來好像是個沒用的函數， 但和 id 一樣，我們日後會看到它在演算、證明中時常用上。 事實上，組件邏輯理論告訴我們：所有函數都可以由 id, const, 和下述的 subst 三個函數組合出來。

subst :: (a -> b -> c) -> (a -> b) -> (a -> c)
subst f g x = f x (g x)