Haskell で2分探索木

プログラミングの基礎 第17章 「再帰的なデータ構造」の二分探索木をHaskell でやってみました。

import Test.HUnit

data Tree_d = Empty | Leaf Int | Node (Tree_d, Int, Tree_d) deriving (Eq,Show)

insertTree :: Tree_d -> Int -> Tree_d

-- 空の木だったら Leaf を作って返す。
insertTree Empty    dat = Leaf dat

-- Leaf だったら 
-- Leaf の値より小さければ左に追加する値、中央に元のLeaf の値、右がEmpty
--                        Node (Leaf dat, n, Empty) を作って返す。
-- Leaf の値より大きければ Node (Empty, n, Leaf dat) を作って返す。
insertTree (Leaf n) dat = if dat==n then Leaf n
                                    else if dat < n then Node (Leaf dat, n, Empty)
                                                    else Node (Empty, n, Leaf dat)
-- Node だったら 
-- Node の値より小さければ左のTree要素に再帰する。
-- Leaf の値より大きければ右のTree要素に再帰する。
insertTree (Node (t1, n, t2)) dat = if dat==n then Node (t1, n, t2)
                                    else if dat < n then Node (insertTree t1 dat, n, t2)
                                                    else Node (t1, n, insertTree t2 dat)

tree1 = Empty
tree2 = Leaf 1
tree3 = Node (Leaf 1, 2, Leaf 3)
tree4 = Node (Empty,7,Leaf 9)
tree5 = Node (tree3,6,tree4)
-- > Node (Node (Leaf 1,2,Leaf 3),6,Node (Empty,7,Leaf 9))


treeTest = "Binary search tree" ~:
           test [ insertTree Empty 3    ~?= Leaf 3,
                  insertTree (Leaf 3) 2 ~?= Node (Leaf 2,3,Empty),
                  insertTree (Leaf 3) 3 ~?= Leaf 3,
                  insertTree (Leaf 3) 4 ~?= Node (Empty,3,Leaf 4),
                  insertTree tree5 4    ~?= Node (Node (Leaf 1,2,Node (Empty,3,Leaf 4)),6,Node (Empty,7,Leaf 9)) ]

testq = runTestTT treeTest
{-
ghci> testq
Cases: 5  Tried: 5  Errors: 0  Failures: 0
Counts {cases = 5, tried = 5, errors = 0, failures = 0}
-}