模式匹配警告与二叉树

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对这两个字符串只进行一次传递并确定哪个顺序关系成立。