150102(4)

Haskell


Tree

-- Tree.hs : 二分探索木
module Tree (
  Tree,
  emptyTree, singleton,
  treeInsert, treeElem
) where

-- データ型の定義
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

-- 空の木
emptyTree :: Tree a
emptyTree = Nil

-- 要素が一つの木
singleton :: a -> Tree a
singleton x = Node x Nil Nil

-- データの挿入
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x Nil = singleton x
treeInsert x (Node y l r)
  | x == y    = Node x l r
  | x < y     = Node y (treeInsert x l) r
  | otherwise = Node y l (treeInsert x r)

-- データの探索
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem _ Nil = False
treeElem x (Node y l r)
  | x == y    = True
  | x < y     = treeElem x l
  | otherwise = treeElem x r

Prelude> :l Tree
[1 of 1] Compiling Tree             ( Tree.hs, interpreted )
Ok, modules loaded: Tree.
*Tree> emptyTree
Nil
*Tree> singleton 1
Node 1 Nil Nil
*Tree> let nums = [8, 6, 4, 1, 7, 3, 5]
*Tree> let numsTree = foldr treeInsert emptyTree nums
*Tree> numsTree
Node 5 (Node 3 (Node 1 Nil Nil) (Node 4 Nil Nil)) (Node 7 (Node 6 Nil Nil) (Node
 8 Nil Nil))
*Tree> treeElem 3 numsTree
True
*Tree> treeElem 2 numsTree
False
*Tree> treeInsert 2 numsTree
Node 5 (Node 3 (Node 1 Nil (Node 2 Nil Nil)) (Node 4 Nil Nil)) (Node 7 (Node 6 N
il Nil) (Node 8 Nil Nil))