-
Notifications
You must be signed in to change notification settings - Fork 1
/
BinarySearchTree.hs
32 lines (25 loc) · 872 Bytes
/
BinarySearchTree.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
module BinarySearchTree where
-- Binary Search Tree (BST)
-- Nil is for empty bottom nodes
-- Node (left-subtree) element (right-subtree)
data Tree a =
Nil | Node (Tree a) a (Tree a)
deriving (Show, Eq)
-- Invariant: All elements in left subtree are less than root
-- while all elements in right subtree are greater than root
type Set = Tree
-- Since trees allow fast O(log n) inserts and lookups,
-- they can be used to implement Sets
-- return empty tree
empty :: Set a
empty = error "todo"
-- Insert element in BST
insert :: Ord a => a -> Set a -> Set a
insert = error "todo"
-- Check if given element exists in subtree
member :: Ord a => a -> Set a -> Bool
member = error "todo"
-- Apply given function to all elements of BST without changing the structure
instance Functor Tree where
fmap f Nil = error "todo"
fmap f (Node left x right) = error "todo"