プログラミングの基礎 第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} -}