search - Haskellの二分探索木の要素?

Question

Haskellの二分探索木で要素を検索するにはどうすればよいですか? 私は自分のツリーを定義しました:

 data Tree a = 
     Null | 
     L a | 
     N (Tree a) a (Tree a) 
     deriving Show 

BST の要素を検索する関数を作成したい:

 findElem :: Tree a -> a -> Maybe a
 findElem tree n = ...

どうすれば作れますか？

Answer 1

コメントで示唆されているように、Lコンストラクターを削除してN Null x Null代わりに使用する必要があります。これにより、リーフ ノードの不要な特殊なケースをコーディングする必要がなくなります。

findElem次に、次のようになります。

findElem :: Ord a => Tree a -> a -> Maybe a
findElem Null _ = -- ...
findElem (N l x r) y =
    case compare x y of
        LT -> -- ...
        EQ -> -- ...
        GT -> -- ...