Purely Functional Data Structures 写経 2.2 Binary Search Trees

Purely Functional Data Structures

続き。P11〜P15

data Ord a => Tree a = E | T (Tree a) a (Tree a) deriving (Show)

この辺は問題ないかな。

class Set s where
  empty :: Ord a => s a
  insert :: Ord a => a -> s a -> s a
  member :: Ord a => a -> s a -> Bool

全関数に Ord a => を書くのが面倒くさいですね。なんとかならんものでしょうか。

instance Set Tree where
  empty = E

  member _ E = False
  member x (T a y b)
    | x < y     = member x a
    | x > y     = member x b
    | otherwise = True

  insert x E = T E x E
  insert x s@(T a y b)
    | x < y     = T (insert x a) y b
    | x > y     = T a y (insert x b)
    | otherwise = s

asパターンって結構使うものなんですね。

ここら辺は特に難しい内容も無いんでさらりと。