模式匹配警告與二叉樹

Question

我是Haskell的初學者，在理解我所得到的警告時遇到了一些麻煩。我實現了一個二叉樹，

data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Eq, Show, 
Read) 

，它工作正常，但我會得到不完整的圖案對這個代碼

get :: Ord a => a -> Tree a -> Maybe a 
get _ Nil = Nothing 
get x (Node v lt rt) 
    | x == v = Just x 
    | x < v = get x lt 
    | x > v = get x rt 

它要我匹配的模式爲_ (Node _ _ _)警告。我不確定這種模式的含義是什麼？

Answer 1

這裏有兩個問題。首先，數據類型：

data Tree a = Nil | Node a (Tree left) (Tree right) deriving (Eq, Show, Read) 
--        ^left? ^right? 

在您的數據定義，您使用的left和right，但這些都是在數據定義的頭部形成不，因此這些不會打字參數。你可能想說：

data Tree a = Nil 
       | Node { value :: a, left :: Tree a, right :: Tree a} 
       deriving (Eq, Show, Read)

但現在我們仍然得到一個錯誤：

hs.hs:5:1: Warning: 
    Pattern match(es) are non-exhaustive 
    In an equation for ‘get’: Patterns not matched: _ (Node _ _ _) 
Ok, modules loaded: Main. 

這裏的問題是，哈斯克爾不知道兩個值只能是<，==或>）。

如果你寫Ord的instance，那麼你有一個「聯繫人」，你將定義一個總訂貨。換句話說，對於任何兩個值x和y，它認爲x < y,x > y或x == y。然而問題是Haskell確實不是知道的。對於Haskell，函數(<),(==)或(>)中的任何函數都可導致True或False。因此 - 因爲編譯器是總是保守 - 它會考慮有兩個值的情況下，使所有x < y，x == y和x > y失敗（說你假設會寫foo x y，bar x y和qux x y那麼這絕對會偏偏這是因爲它們三個黑匣子函數）。您可以通過在最後一種情況下寫otherwise解決它：

get :: Ord a => a -> Tree a -> Maybe a 
get _ Nil = Nothing 
get x (Node v lt rt) 
    | x == v = Just x 
    | x < v = get x lt 
    | otherwise = get x rt

otherwise是True的別名因此沒有可能不採取該分支。所以，現在的保守編譯理解的是，無論什麼樣的x和y的值，它總是會一些分支，因爲如果不採取前兩種，它會肯定取最後一個。

你可能會認爲這是奇怪的，但由於通常不會在正式語言（僅在文檔中，因此自然語言）中規定的合同，編譯器沒有意味着要知道：你可以作爲一個程序員決定不尊重合同（但請注意，這是一個壞主意非常）。即使你通常以程序員的身份編寫正式合同，你仍然可以決定不尊重它，而且編譯器不能總是對正式合同進行必要的邏輯推理。

Answer 2

威廉·Onsem已經解釋的問題很好。我只想補充一點，是可能以非常相似的方式進行x和v之間的比較，以張貼的代碼，其分支機構但是找到詳盡的編譯器。

代替

get :: Ord a => a -> Tree a -> Maybe a 
get _ Nil = Nothing 
get x (Node v lt rt) 
    | x == v = Just x 
    | x < v = get x lt 
    | x > v = get x rt 

簡單地使用

get :: Ord a => a -> Tree a -> Maybe a 
get _ Nil = Nothing 
get x (Node v lt rt) = case compare x v of 
    EQ -> Just x 
    LT -> get x lt 
    GT -> get x rt 

事實上，compare是一個函數取兩個參數，在枚舉類型Ordering，這隻能是EQ（等於）返回一個值， LT（小於），和GT（大於）。由於這是一個代數類型，GHC可以看到它的所有構造函數都由case處理。

此外，取決於實際類型a，使用compare可以更有效率。例如，在比較兩個可能長的字符串時，在遍歷它們兩次（如果不是三次，在原始代碼中），它是次優的：compare對這兩個字符串只進行一次傳遞並確定哪個順序關係成立。