8 min to read
CIS 194 03 Recursion patterns, polymorphism, and Prelude 遞歸模式，多態性和前奏
Source: 03-rec-poly
▌Recursion patterns, polymorphism, and the Prelude
遞歸模式，多態性和前奏
CIS 194 第 3 週 2013 年 1 月 28 日
完成 HW 2 時，您可能花費了大量時間來編寫顯式遞歸函數。在這一點上，您可能會認為 Haskell 程序員大部分時間都在這樣做。實際上，經驗豐富的 Haskell 程序員 幾乎不會 編寫遞歸函數！
這怎麼可能？關鍵是要注意，儘管遞歸函數在理論上可以做很多事情，但實際上，某些通用模式會一遍又一遍地出現。通過將這些模式抽像到庫函數中，程序員可以保留對這些函數進行遞歸的底層細節，而在更高層次上思考問題，這是 wholemeal 編程 的目標。
▌Recursion patterns 遞歸模式
回顧我們對 Int 值列表的簡單定義：
data IntList = Empty | Cons Int IntList
deriving Show
我們可能會對 IntList 做什麽事情？ 以下是幾種常見的可能性：
- 對列表的每個元素執行一些操作
- 僅保留列表中的某些元素，並丟棄其他元素。基於測試。
- 以某種方式 “匯總 (summarize)” 列表中的元素（找到它們的總和，乘積，最大值…）
- 您可能會想到其他！
▌Map 映射
讓我們考慮第一個（對列表的每個元素執行一些操作）。
例如，我們可以向列表中的每個元素加一
或者我們可以通過使用絕對值來確保列表中的每個元素都是不是負數：
absAll :: IntList -> IntList
absAll Empty = Empty
absAll (Cons x xs) = Cons (abs x) (absAll xs)
或者我們可以對每個元素求平方：
squareAll :: IntList -> IntList
squareAll Empty = Empty
squareAll (Cons x xs) = Cons (x*x) (squareAll xs)
此時，您的頭腦中應該閃爍著紅色的大燈和警告鈴。這三個功能看起來太相似了。應該有某種方法可以抽像出通用性，因此我們不必重複自己！
確實有一種方法 —— 您可不可以指出來？這三個示例中哪些部分相同，哪些部分發生變化？
當然，改變部分是我們要對列表的每個元素執行的操作。我們可以將此操作指定為 Int -> Int 類型的函數。在這裡，我們開始看到能夠將函數作為輸入傳遞給其他功能有多麼巨大的用處！
現在，我們可以使用 mapIntList 實現 addOneToAll, absAll 和 squareAll
exampleList = Cons (-1) (Cons 2 (Cons (-6) Empty))
addOne x = x + 1
square x = x * x
mapIntList addOne exampleList
mapIntList abs exampleList
mapIntList square exampleList
▌Filter 過濾
另一個常見的模式是，當我們希望僅保留列表中的某些元素，而根據測試將其他元素丟棄時。 例如，我們可能只想保留正數：
或僅偶數：
keepOnlyEven :: IntList -> IntList
keepOnlyEven Empty = Empty
keepOnlyEven (Cons x xs)
| even x = Cons x (keepOnlyEven xs)
| otherwise = keepOnlyEven xs
我們如何概括這種模式？什麼保持不變，我們需要抽象什麼？
▌Fold 折疊
我們提到的最後一種模式是“匯總(summarize)”列表中的元素。這也被稱為“折疊(fold)”或“減少(reduce)”操作。下週我們將回到這。同時，您可能需要考慮如何抽像出這種模式！
▌Polymorphism 多態性
現在，我們已經編寫了一些不錯的通用函數，用於在Ints列表上進行映射和過濾。 但是，我們還沒有完成概括！ 如果我們想過濾整數列表怎麼辦？ 或者 Bools？ 還是字符串堆棧樹列表的列表(lists of lists of trees of stacks of Strings, XD)？ 對於每種情況，我們都必須創建新的數據類型和新的函數。 更糟糕的是，代碼將完全相同。 唯一不同的是類型簽名。 Haskell 不能在這裡幫助我們嗎？
當然可以！Haskell 支持數據類型和函數的多態。“多態”一詞來自希臘語（πολύμορφος），意思是“具有多種形式”：多態的東西適用於多種類型。
▌Polymorphic data types 多態數據類型
首先，讓我們看看如何聲明一個多態數據類型。
data List t = E | C t (List t)
（由於我們已經將 Empty 和 Conss 用於 IntList 的構造函數，因此我們無法重用 Empty 和 Cons，因此我們將使用 E 和 C 代替）之前有 data IntList = ...，我們現在有 data List t = ... ， t 是一個 類型變量 ，可以代表任何類型。（類型變量必須以小寫字母開頭，而類型必須以大寫字母開頭。）data List t = ... 表示 List 類型是由類型 參數化 的，與函數可以由某些輸入參數化的方式幾乎相同。
給定類型 t， (List t) 由構造函數 E 或構造函數 C 以及類型 t 和另一個 (List t) 組成。這裡有些例子：
lst1 :: List Int
lst1 = C 3 (C 5 (C 2 E))
lst2 :: List Char
lst2 = C 'x' (C 'y' (C 'z' E))
lst3 :: List Bool
lst3 = C True (C False E)
▌Polymorphic functions 多態函數
現在，我們來概括 filterIntList 一下我們的新多態 List。我們可以只使用 filterIntList 的代碼，將 E 替換為 Empty ，將 C 替換為 Cons：
filterList _ E = E
filterList p (C x xs)
| p x = C x (filterList p xs)
| otherwise = filterList p xs
現在，filterList 是什麼類型 ？讓我們看看 ghci 的類型推斷：
*Main> :t filterList
filterList :: (t -> Bool) -> List t -> List t
我們可以這樣理解：“對於任何類型的 t，filterList 都會將一個函數從 t 轉換為 Bool，並獲取 t 的列表，然後返回 t 的列表。”
概括 mapIntList 呢？ 我們應該給函數 mapList 賦予什麼類型，該函數將一個函數應用於 List t 中的每個元素？
我們的第一個想法可能是給它一個類型
mapList :: (t -> t) -> List t -> List t
這行得通，但是這意味著在應用 mapList 時，我們總是得到一個與元素列表類型相同的列表。 這過於嚴格：我們希望能夠執行諸如 mapList show 之類的操作，以便將 Ints 列表轉換為 Strings 列表。 那麼，這裡是 mapList 的最通用類型，以及一個實現：
mapList :: (a -> b) -> List a -> List b
mapList _ E = E
mapList f (C x xs) = C (f x) (mapList f xs)
關於多態函數要記住的重要一件事是，調用者可以選擇類型。編寫多態函數時，它必須適用於每種可能的輸入類型。再加上 Haskell 無法直接根據某物的類型做出決策的事實，這具有一些有趣的含義，我們將在後面進行探討。
▌The Prelude 序幕 / 前奏
Prelude 是具有一堆標准定義的模塊，該模塊隱式地導入到每個 Haskell 程序中。值得花一些時間瀏覽其文檔，以熟悉可用的工具。
當然，在 Prelude 中定義了多態列表，以及用於處理它們的許多有用的多態函數。例如，filter 和 map 是我們 filterList 和 mapList 的對應物 。實際上，該 Data.List 模塊包含更多列表函數。
要知道的另一種有用的多態類型是 Maybe，定義為
data Maybe a = Nothing | Just a
類型 Maybe a 的值要么包含類型的值 a（包裝在 Just 構造函數中），要么包含 Nothing（表示某種故障或錯誤）。Data.Maybe 模塊具有處理 Maybe 值的函數。
原始連接丟失，可參看 Data.Maybe
▌Total and partial functions 全部和部分函數
考慮這種多態類型：
[a] -> a
哪些函數可以具有這種類型？類型表示給定列表的事物為 a 類型 ，函數必須產生一些類型的值 a。例如，Prelude 函數 head 具有這種類型。
… 但是如果給 head 一個空列表作為輸入會發生什麼呢？ 讓我們看一下 head 的源代碼…
原始連接丟失，找不到代替
它崩潰了！ 由於它必須適用於所有類型，因此它無能為力。 無法憑空構成任意類型的元素。
head 是所謂的部分函數：有些輸入會導致 head 崩潰。 具有某些輸入將使它們無限遞歸的函數也稱為部分函數(partial functions)。 在所有可能的輸入上定義良好的函數稱為 全部函數(Total functions)。
Haskell 的最佳做法是盡可能避免部分函數。 實際上，在任何編程語言中，避免使用部分函數都是一種好習慣，但是在大多數情況下，這令人討厭。 Haskell 傾向於使其變得非常容易和明智。
head 是個錯誤！它不應該出現在 Prelude 中。您幾乎不應該使用的其他部分 Prelude 函數包括 tail， init，last，和(!!)。從這一點開始，在作業中使用這些函數將失去樣式得分！
該怎麼做呢？
▌Replacing partial functions 替換部分函數
通常，部分匹配函數（如 head, tail等等）可以由模式匹配代替。 請考慮以下兩個定義：
doStuff1 :: [Int] -> Int
doStuff1 [] = 0
doStuff1 [_] = 0
doStuff1 xs = head xs + (head (tail xs))
doStuff2 :: [Int] -> Int
doStuff2 [] = 0
doStuff2 [_] = 0
doStuff2 (x1:x2:_) = x1 + x2
這些函數計算出的結果完全相同，並且它們都是 total 。 但是只有第二個顯然是 total，而且無論如何都更容易閱讀。
▌Writing partial functions 編寫部分函數
如果發現自己編寫了部分函數怎麼辦？ 有兩種方法。 首先是更改函數的輸出類型以指示可能的故障。 回顧一下 Maybe 的定義：
data Maybe a = Nothing | Just a
現在，假設我們正在寫 head。我們可以像這樣安全地重寫它：
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
確實，在 safe package 中 定義了這樣一個函數。
為什麼這是個好主意？
safeHead永遠不會崩潰safeHead的類型很明顯，對於某些輸入它可能會失敗- 類型系統確保
safeHead的用戶必須適當地檢查safeHead的返回值，以查看他們是否獲得了值或Nothing
從某種意義上說，safeHead 仍然是“部分”；但是我們已經在類型系統中反映了局部性，因此現在是安全的。目的是使類型盡可能多地告訴我們函數的行為。
好的，但是如果我們知道僅在保證有非空列表的情況下使用 head ，該怎麼辦？ 在這種情況下，收回 Maybe a 確實很煩人，因為我們必須花更多的精力來處理我們“不知道”實際上不可能發生的情況。
答案是，如果確實可以保證某些條件，那麼類型應該反映出保證！ 然後編譯器可以為您執行保證。 例如：
data NonEmptyList a = NEL a [a]
nelToList :: NonEmptyList a -> [a]
nelToList (NEL x xs) = x:xs
listToNel :: [a] -> Maybe (NonEmptyList a)
listToNel [] = Nothing
listToNel (x:xs) = Just $ NEL x xs
headNEL :: NonEmptyList a -> a
headNEL (NEL a _) = a
tailNEL :: NonEmptyList a -> [a]
tailNEL (NEL _ as) = as
您可能會認為這樣做僅適用於笨蛋，不是適用於像您這樣的超級編碼天才的傢伙。 當然，您 絕不會犯任何錯誤，例如將空列表傳遞給只需要非空函數的函數。 對？ 好吧，這裏肯定有一個笨蛋，但不是你在想的人。
