哈斯克爾函數求解釋

Question

data BTree a = Empty | Node (BTree a) a (BTree a) -- This is a node-labelled binary tree 

可能有人請解釋是以下Haskell函數？

1. labels :: BTree a -> [a]

   labels Empty = [] 
   labels (Node left label right) = labels left ++ [label] ++ labels right 
   

2. reflect :: BTree a -> BTree a

   reflect Empty = Empty 
   reflect (Node left label right) = Node (reflect left) label (reflect right) 
   

Answer 1

首先：一些格式。這是怎樣的代碼通常在Haskell中被格式化：

data BTree a = Empty 
      | Node (BTree a) a (BTree a) 

labels :: BTree a -> [a] 
labels Empty     = [] 
labels (Node left label right) = labels left ++ [label] ++ labels right 

reflect :: BTree a -> BTree a 
reflect Empty     = Empty 
reflect (Node left label right) = Node (reflect left) label (reflect right) 

（提示：如果您通過4個空格縮進的代碼會顯示正確的語法高亮顯示）。 現在，讓我們通過它：

data BTree a = Empty 
      | Node (BTree a) a (BTree a) 

定義一個新的「參數」的數據類型。由於小型a這是一個類型參數，所以稱爲參數。這意味着a可通過任何其他類型的替代，例如Int，Double，String，或任何。在C++中思考模板或在Java中使用泛型。 Empty和Node被稱爲構造的數據類型的。 A BTree a可以是Empty或（這就是|象徵的）包含Node，其包含BTree a和a和另一個BTree a。定義是遞歸，因爲數據類型（BTree a）顯示在它自己的定義中。

labels :: BTree a -> [a] 
labels Empty     = [] 
labels (Node left label right) = labels left ++ [label] ++ labels right 

labels收集包含在樹中的所有值。第一行是類型聲明：它需要一個二叉樹a節點（BTree a）和地圖，爲的a S（[a]）的列表。這種類型已經給你一個關於可能發生什麼的好主意。

接下來的兩行是所謂模式匹配。這些與其他語言中的case語句類似：您區分不同的可能性，然後選擇適當的情況（儘管它們更強大）。您應該注意它們與BTree a所具有的兩個構造函數完全相符。如果我們在Empty節點，那麼我們只會返回一個空列表（[]）。否則，我們將進入下一行，並有一個Node，它必須有BTree a和a和BTree a，我們綁定到left,label和right。無論我們想要什麼，我們可能都會撥打left,label和right，但這些都很直觀。

現在left和right再次BTree a型的，所以我們可以呼籲兩國labels，並期望他們返回a個列表，即[a]。所以標籤也是遞歸，因爲它在它的定義中調用它自己。這是一個非常強大的技術，在Haskell中使用很多。 labels然後連接從labels left獲得的列表，其中僅包含當前標籤（[label]），然後從labels right獲得的列表。因此，我們可以有效地得出結論，它將來自左側子樹的標籤與當前標籤以及右側子樹中的標籤進行連接，並將其全部放入列表中。

reflect :: BTree a -> BTree a 
reflect Empty     = Empty 
reflect (Node left label right) = Node (reflect left) label (reflect right) 

與labels的工作方式幾乎相同，只不過它返回標籤樹而不是列表。如此有效地，這沒有任何作用，它是一種昂貴的身份識別功能。但它是一個更強大的模板。例如，您可以很容易地將另一個函數傳遞給reflect並將其應用於其每個元素。