29

次のコードを GHC で (-Wallフラグを使用して) コンパイルすると:

module Main where

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right)
    | x == a = Node a left right
    | x < a = Node a (insert x left) right
    | x > a = Node a left (insert x right)

main :: IO()
main = do
    let nums = [1..10]::[Int]
    print . foldr insert EmptyTree $ nums

GHC は、以下のパターン マッチングがinsert網羅的でないと不満を漏らしています。

test.hs|6| 1:
||     Warning: Pattern match(es) are non-exhaustive
||              In an equation for `insert': Patterns not matched: _ (Node _ _ _)

なぜ GHC はこの警告を出しているのですか? GHC が不平を言うパターンが で処理されることは明らかですinsert x (Node a left right)。

4

3 に答える 3

52

パターンマッチングが不完全だからです。x==a、x<a、またはのいずれかx>aが成り立つという保証はありません。たとえば、型がNaNDoubleであり、xNaN である場合、いずれも ではありませんTrue。

于 2012-05-22T12:39:26.573 に答える
42

Riccardo は正しいです。GHC は、ガードがすべて false である可能性はないと推測していません。だから彼の答えを受け入れてください。

脱線して、コーディング スタイルについて話します。

使用しないotherwise理由は、見た目が悪いからかもしれません。

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right)
    | x == a    = Node a left right
    | x < a     = Node a (insert x left) right
    | otherwise = Node a left (insert x right)

このコードを見て、人間の読者は、ファイナル ガードがx > a.

代わりに次のように書くこともできます:

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right) = case x `compare` a of
    EQ -> Node a left right
    LT -> Node a (insert x left) right
    GT -> Node a left (insert x right)

Orderingによって返される型には、、およびcompareの 3 つの値しかないため、GHC はすべての可能性をカバーしたことを確認でき、人間の読者はそれらを正しくカバーしたことを簡単に確認できます。EQLTGT

これは、より効率的なコードでもあります。呼び出してcompareから呼び出すのではなく、1 回==呼び出し<ます。

ここで、もう少し脱線して、怠惰について話します。

おそらく、次のような関数も書いたことがあるでしょう:

contains :: (Ord a) => a -> Tree a -> Bool
contains _ EmptyTree = False
contains x (Node a left right) = case x `compare` a of
    EQ -> True
    ...

の場合、ツリーがコンストラクターを使用し、その最初の引数が に等しいことx == aを知る必要があります。どちらのサブツリーが何であるかを知る必要はありません。Nodex

しかし、ここで上記の私の定義を振り返ってくださいinsert。指定されたツリーが の場合、最初の引数が常に である をNode常に返します。しかし、それを前もって述べているわけではありません。代わりに、 を評価します。Nodeax `compare` a

insertできるだけ遅く比較を実行するように書き直すことができます。

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right) = Node a newLeft newRight
  where comparison = x `compare` a
        newLeft  = if comparison == LT then insert x left  else left
        newRight = if comparison == GT then insert x right else right

Node aこれで、ビットをできるだけ早く返します --- たとえ比較でエラーがスローされたとしても! --- それでも、比較は最大で 1 回実行します。

于 2012-05-22T10:03:27.267 に答える
27

insert x (Node a left right)GHC は、あなたの 3 人の警備員が考えられるすべてのケースをカバーしているかどうかを推測できませんinsert x (Node a left right)。最後の条件x > aをotherwise(の同義語True) に置き換えてみてください。ただし、この特定のケースでは、ガードがすべてのケースをカバーしているわけではないことは事実です。二重数に関する augustss の例を参照してください。

于 2012-05-22T09:51:20.823 に答える