Haskell/其他資料結構

其他資料結構

中級 Haskell

在本章中，我們將透過示例說明如何使用我們迄今為止研究的技術來處理更復雜的資料型別。特別是，我們將看到遞迴資料結構的示例，這些資料結構是包含相同型別的值的資料型別。遞迴資料結構在許多程式設計技術中發揮著至關重要的作用，因此即使您不需要經常定義一個新的資料結構（與使用庫中的現有資料結構相比），瞭解它們是什麼以及如何操作它們也很重要。除此之外，仔細遵循本章中的實現是您初學者 Haskell 能力的一個很好的練習。

注意

Haskell 庫生態系統提供了大量的資料結構（遞迴的和非遞迴的），涵蓋了廣泛的實際需求。除了列表之外，還有對映、集合、有限序列和陣列，等等。學習主要資料結構的最佳起點是 Haskell 實踐跟蹤中的資料結構入門。我們建議您在完成接下來的幾個中級 Haskell 章之後至少快速瀏覽一遍。

樹

遞迴資料結構中最重要的型別之一是樹。樹的型別有很多，所以我們任意選擇一個簡單的樹作為例子。以下是它的定義

data Tree a = Leaf a | Branch (Tree a) (Tree a)

如您所見，它是引數化的；也就是說，我們可以有 Int 型別的樹，String 型別的樹，Maybe Int 型別的樹，(Int, String) 對型別的樹等等。使這個資料型別特殊的是 Tree 出現在它自己的定義中。一個 Tree a 要麼是一個葉，包含型別 a 的值，要麼是一個分支，從它懸掛著另外兩棵型別 Tree a 的樹。

列表作為樹

正如我們在 Lists II 和 Lists III 中所見，我們將列表分解為兩種情況：一個空列表（用[]表示），以及指定型別的一個元素加上另一個列表（用(x:xs)表示）。這意味著列表資料型別的定義可能看起來像這樣

 -- Pseudo-Haskell, will not actually work (because lists have special syntax).
data [a] = [] | (a:[a])

您可以實際操作的等效定義是

data List a = Nil | Cons a (List a)

與樹一樣，列表也是遞迴的。對於列表，建構函式是 [] 和 (:)。它們分別對應於上面 Tree 定義中的 Leaf 和 Branch。這意味著我們可以像使用空列表和 (x:xs) 一樣使用 Leaf 和 Branch 進行模式匹配。

對映和摺疊

我們已經瞭解了列表的對映和摺疊。現在，我們可以為新的 Tree 型別編寫對映和摺疊函式。回顧一下

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show)
data [a]    = []     | (:)    a [a]
  -- (:) a [a] is the same as (a:[a]) with prefix instead of infix notation.

注意

推導將在後面的類和型別部分進行解釋。現在，將其理解為告訴 Haskell（以及擴充套件到您的直譯器）如何顯示 Tree 例項。

對映

讓我們看一下列表 map 的定義

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

如果我們要編寫 treeMap，它的型別是什麼？如果您知道它的型別應該是什麼，定義函式就會更容易。

我們希望 treeMap 在某個型別的 Tree 上工作，並透過對樹的每個元素應用一個函式來返回另一個某個型別的 Tree。

treeMap :: (a -> b) -> Tree a -> Tree b

這與列表示例一樣。

現在，當談論 Tree 時，每個 Leaf 只包含一個值，因此我們所要做的就是將給定的函式應用於該值，然後返回一個帶有更改後的值的 Leaf

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f (Leaf x) = Leaf (f x)

這與 map 中的空列表情況非常相似。現在，如果我們有一個 Branch，它將包含兩個子樹；我們該如何處理這些子樹？列表 map 對列表的尾部（遞迴）使用了一個對自身的呼叫，因此我們也應該對這兩個子樹這樣做。treeMap 的完整定義如下

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f (Leaf x) = Leaf (f x)
treeMap f (Branch left right) = Branch (treeMap f left) (treeMap f right)

我們可以透過注意到 treeMap f 本身是一個型別為 Tree a -> Tree b 的函式來使程式碼更具可讀性。這給了我們以下修改後的定義

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f = g where
  g (Leaf x) = Leaf (f x)
  g (Branch left right) = Branch (g left) (g right)

如果您沒有立即理解這一點，請嘗試重新閱讀。這種模式匹配的使用乍一看可能很奇怪，但對於資料型別的使用至關重要。請記住，模式匹配發生在建構函式上。

準備好了就繼續閱讀有關樹的摺疊的資訊。

摺疊

與對映一樣，讓我們首先回顧一下列表 foldr 的定義

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

回想一下列表有兩個建構函式

(:) :: a -> [a] -> [a]  -- takes an element and combines it with the rest of the list
[] :: [a]  -- the empty list takes zero arguments

因此 foldr 接受兩個引數，分別對應於這兩個建構函式

f :: a -> b -> b  -- a function takes two elements and operates on them to return a single result
acc :: b  -- the accumulator defines what happens with the empty list

讓我們花點時間澄清這一點。如果初始 foldr 給定一個空列表，則返回預設累加器。對於非空列表，將第一個元素與摺疊列表尾部的結果（使用 f）組合起來，因此摺疊會一直進行，直到我們到達空列表。

與列表的 foldr 一樣，我們希望 treeFold 將某個型別的樹轉換為另一個型別的值；因此，我們將使用 Tree a -> b 而不是 [a] -> b。我們如何指定轉換？首先要注意 Tree a 有兩個建構函式（就像列表有兩個建構函式一樣）

Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a

所以 treeFold 將有兩個引數，分別對應於這兩個建構函式

fbranch :: b -> b -> b
fleaf :: a -> b

綜合起來，我們得到以下型別定義

treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b

也就是說，第一個引數的型別為 (b -> b -> b)，是一個指定如何將子樹組合成單個結果的函式；第二個引數的型別為 a -> b，是一個指定如何處理葉子（它是遞迴的結尾，就像空列表對於列表一樣）的函式；第三個引數的型別為 Tree a，是我們想要摺疊的整個樹。

與 treeMap 一樣，我們將透過引入一個區域性函式 g 來避免重複引數 fbranch 和 fleaf

treeFold :: (b -> b -> b) -> (a -> b)  -> Tree a -> b
treeFold fbranch fleaf = g where
  -- definition of g goes here

引數 fleaf 告訴我們如何處理 Leaf 子樹

g (Leaf x) = fleaf x

引數 fbranch 告訴我們如何將兩個子樹的“摺疊”結果組合起來

g (Branch left right) = fbranch (g left) (g right)

我們的完整定義變為

treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold fbranch fleaf = g where
  g (Leaf x) = fleaf x
  g (Branch left right) = fbranch (g left) (g right)

有關這些工作原理的示例，將 Tree 資料定義以及 treeMap 和 treeFold 函式複製到一個 Haskell 檔案中，以及以下示例樹和摺疊示例函式。

tree1 :: Tree Integer
tree1 = 
    Branch
       (Branch 
           (Branch 
               (Leaf 1) 
               (Branch (Leaf 2) (Leaf 3))) 
           (Branch 
               (Leaf 4) 
               (Branch (Leaf 5) (Leaf 6)))) 
       (Branch
           (Branch (Leaf 7) (Leaf 8)) 
           (Leaf 9))
 
doubleTree = treeMap (*2)  -- doubles each value in tree
sumTree = treeFold (+) id -- sum of the leaf values in tree
fringeTree = treeFold (++) (: [])  -- list of the leaves of tree

然後將它載入到 GHCi 中並進行評估

doubleTree tree1
sumTree tree1

其他資料型別

對映和摺疊函式可以為任何型別的資料型別定義。為了概括應用於列表和樹的策略，在本節的最後，我們將為一個非常奇怪、人為構建的資料型別計算對映和摺疊

data Weird a b = First a
               | Second b
               | Third [(a,b)]
               | Fourth (Weird a b)

在您按照示例操作時編寫函式可能是一個有益的練習，嘗試讓編碼領先於閱讀一步。

一般對映

在使用這種 Weird 型別時，第一個重要的區別是它具有兩個型別引數。因此，我們希望對映函式接受兩個函式作為引數，一個用於應用於型別a的元素，另一個用於應用於型別b的元素。考慮到這一點，我們可以編寫 weirdMap 的型別簽名

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d

下一步是定義weirdMap。關鍵是對映保留了資料型別的結構，因此該函式必須計算為一個使用與原始Weird相同的建構函式的Weird。因此，我們需要一個定義來處理每個建構函式，這些建構函式被用作編寫它們的模式。和以前一樣，為了避免重複weirdMap的引數列表，where 子句非常有用。下面是該函式的草圖。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = --More to follow
    g (Second y)         = --More to follow
    g (Third z)          = --More to follow
    g (Fourth w)         = --More to follow

前兩種情況相當簡單，因為Weird內部只有一個a或b型別的元素。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = First (fa x)
    g (Second y)         = Second (fb y)
    g (Third z)          = --More to follow
    g (Fourth w)         = --More to follow

Third 比較棘手，因為它包含一個列表，其元素本身是資料結構（元組）。因此，我們需要遍歷巢狀的資料結構，對所有型別為a和b的元素應用fa和fb，最後（因為對映必須保留結構）生成一個元組列表 - [(c,d)] - 用於建構函式。最簡單的方法似乎只是分解Weird內部的列表並使用模式進行操作。

    g (Third []) = Third []
    g (Third ((x,y):zs)) = Third ( (fa x, fb y) : ( (\(Third z) -> z) (g (Third zs)) ) )

這似乎是作為列表的典型遞迴函式編寫的。我們首先將感興趣的函式應用於第一個元素以獲得新列表的頭部，(fa x, fb y)。但我們會把它與什麼連線起來呢？由於g需要一個Weird引數，我們需要使用列表尾部建立一個Weird以進行遞迴呼叫。但是，g將返回一個Weird而不是一個列表，因此我們必須從該Weird中檢索修改後的列表 - 這就是 lambda 函式的作用。最後，還需要定義空列表基本情況。

經過所有這些，我們得到一個混亂的函式。每次遞迴呼叫g都需要將zs包裝到一個Weird中，而我們真正想要做的是使用(fa x, fb y)和修改後的xs來構建一個列表。此解決方案的問題在於g可以（透過模式匹配）直接作用於列表頭，但（由於其型別簽名）不能直接呼叫列表尾部。因此，最好在不使用模式匹配分解列表的情況下應用fa和fb（至少就g直接而言）。但是，確實存在直接逐元素修改列表的方法...

    g (Third z) = Third ( map (\(x, y) -> (fa x, fb y) ) z)

...我們久經考驗的map 函式，它使用 lambda 函式修改列表z中的所有元組。事實上，編寫定義的第一個嘗試看起來就像一個列表對映的應用，除了多餘的Weird打包和解包。我們透過讓map完成z的模式拆分來消除這些，map直接與常規列表一起工作。您可能覺得將 map 定義擴充套件到g內部以更清楚地看到區別很有用。最後，您可能更喜歡使用列表推導語法以另一種簡潔的方式編寫此新版本。

    g (Third z) = Third [ (fa x, fb y) | (x,y) <- z ]

新增Third函式後，只剩下Fourth要定義了。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = First (fa x)
    g (Second y)         = Second (fb y)
    g (Third z)          = Third ( map (\(x, y) -> (fa x, fb y) ) z)
    g (Fourth w)         = --More to follow

我們只需要遞迴地應用g即可。

weirdMap :: (a -> c) -> (b -> d) -> Weird a b -> Weird c d
weirdMap fa fb = g
  where
    g (First x)          = First (fa x)
    g (Second y)         = Second (fb y)
    g (Third z)          = Third ( map (\(x, y) -> (fa x, fb y) ) z)
    g (Fourth w)         = Fourth (g w)

通用摺疊

雖然我們能夠透過為每個單獨的型別指定一個函式來定義對映，但這對於摺疊來說還不夠。對於摺疊，我們需要為每個建構函式提供一個函式。在列表中，建構函式是[]和(:)。foldr 函式中的acc引數對應於[]建構函式。foldr 函式中的f引數對應於(:)建構函式。Weird 資料型別有四個建構函式，因此我們需要四個函式 - 一個用於處理每個建構函式指定的資料型別的內部結構。接下來，我們有一個Weird a b型別的引數，最後我們希望整個摺疊函式計算為其他一些任意型別的值。此外，我們傳遞給weirdFold的每個函式必須計算為與weirdFold相同的型別。這使我們能夠製作一個模擬型別簽名並草擬定義。

weirdFold :: (something1 -> c) -> (something2 -> c) -> (something3 -> c) -> (something4 -> c) -> Weird a b -> c
weirdFold f1 f2 f3 f4 = g
  where
    g (First x)          = --Something of type c here
    g (Second y)         = --Something of type c here
    g (Third z)          = --Something of type c here
    g (Fourth w)         = --Something of type c here

現在，我們需要弄清楚哪些型別對應於something1、something2、something3和something4。這是透過分析建構函式來完成的，因為函式必須以資料型別元素作為引數（這些元素的型別由建構函式型別簽名指定）。同樣，前兩個函式的型別和定義很簡單。第三個也不難，因為就摺疊(a,b)列表而言，元組與簡單型別沒有區別（與 map 示例不同，現在內部結構並不重要）。然而，第四個建構函式是遞迴的，我們需要小心。與weirdMap一樣，我們還需要遞迴地呼叫g函式。這使我們得到了最終的定義。

weirdFold :: (a -> c) -> (b -> c) -> ([(a,b)] -> c) -> (c -> c) -> Weird a b -> c
weirdFold f1 f2 f3 f4 = g
  where
    g (First x)          = f1 x
    g (Second y)         = f2 y
    g (Third z)          = f3 z
    g (Fourth w)         = f4 (g w)

注意

如果您期望在上面的weirdFold中看到非常複雜的表示式，並對解決方案的直接性感到驚訝，那麼看看如果我們用這種風格編寫常見的foldr並且沒有列表的特殊方括號語法來分散我們的注意力，它會是什麼樣子可能會有所幫助。

-- List a is [a], Cons is (:) and Nil is []
data List a = Cons a (List a) | Nil

listFoldr :: (a -> b -> b) -> (b) -> List a -> b
listFoldr fCons fNil = g
  where
    g (Cons x xs) = fCons x (g xs)
    g Nil         = fNil

現在更容易看到其中的相似之處。額外的複雜之處在於Cons（即(:)）接受兩個引數（因此，fCons也是如此）並且是遞迴的，需要呼叫g。此外，fNil當然不是一個真正的函式，因為它不接受任何引數。

遞迴資料型別上的摺疊

就摺疊而言，Weird是一個相當容易處理的資料型別。只有一個遞迴建構函式，它甚至沒有巢狀在其他結構中。如果我們新增一個真正複雜的第五個建構函式會發生什麼？

    Fifth [Weird a b] a (Weird a a, Maybe (Weird a b))

這是一個有效但又棘手的問題。通常，以下規則適用。

要提供給摺疊的函式與對應建構函式具有相同數量的引數。
此類函式引數的型別與建構函式引數的型別匹配，除非建構函式是遞迴的（即，接受其自身型別的引數）。
如果建構函式是遞迴的，建構函式的任何遞迴引數將對應於摺疊計算結果的型別的一個引數。^[1]
如果建構函式是遞迴的，則應將完整的摺疊函式（遞迴地）應用於遞迴建構函式引數。
如果遞迴元素出現在另一個數據結構內部，則應使用該資料結構的適當對映函式將摺疊函式應用於它。

因此，f5將具有以下型別

f5 :: [c] -> a -> (Weird a a, Maybe c) -> c

因為Fifth的型別是

Fifth :: [Weird a b] -> a -> (Weird a a, Maybe (Weird a b)) -> Weird a b

Fifth建構函式的g定義將是

    g (Fifth list x (waa, mc)) = f5 (map g list) x (waa, maybeMap g mc)
      where
        maybeMap f Nothing = Nothing
        maybeMap f (Just w) = Just (f w)

請注意，Weird a a部分沒有發生任何奇怪的事情。沒有呼叫g。怎麼回事？這是遞迴，對吧？好吧，不完全是。Weird a a和Weird a b是不同的型別，因此它不是真正的遞迴。不能保證例如，f2將適用於型別為 'a' 的東西，而它期望一個型別為 'b' 的東西。它在某些情況下可能是真的，但在所有情況下都不可靠。

還要檢視maybeMap的定義。驗證它是否確實是一個對映函式，因為