I made a splay tree, but I don't understand how to delete min element from it, can someone help please?
data Splay a = Empty | Node a (Splay a) (Splay a) deriving Show
data Direction = L | R deriving Eq
rotate :: Direction -> Splay a -> Splay a
rotate L (Node x a (Node y b c)) = (Node y (Node x a b) c)
rotate R (Node y (Node x a b) c) = (Node x a (Node y b c))
insert :: Ord a => a -> Splay a -> Splay a
insert x t = let (path, t') = pathToInserted x t in splay t' path
where pathToInserted :: Ord a => a -> Splay a -> ([Direction], Splay a)
pathToInserted x Empty = ([], Node x Empty Empty)
pathToInserted x t@(Node val l r)
| x == val = ([], t)
| x < val = let (path,l') = pathToInserted x l in (L:path, Node val l' r)
| x > val = let (path,r') = pathToInserted x r in (R:path, Node val l r')
splay :: Splay a -> [Direction] -> Splay a
splay t [] = t
-- Zig
splay t [L] = rotate R t
splay t [R] = rotate L t
-- Zig-zig
splay (Node q (Node p x c) d) (L:L:path) =
rotate R $ rotate R (Node q (Node p (splay x path) c) d)
splay (Node p a (Node q b x)) (R:R:path) =
rotate L $ rotate L (Node p a (Node q b (splay x path)))
-- Zig-zag
splay (Node q (Node p a x) d) (L:R:path) =
rotate R (Node q (rotate L $ Node p a (splay x path)) d)
splay (Node p a (Node q x d)) (R:L:path) =
rotate L (Node p a (rotate R $ Node q (splay x path) d))
fromList :: Ord a => [a] -> Splay a
fromList = foldr insert Empty
insert' :: Ord a => a -> Splay a -> Splay a
insert' x Empty = Node x Empty Empty
insert' x t@(Node val l r)
| x == val = t
| x < val = rotate R (Node val (insert' x l) r)
| x > val = rotate L (Node val l (insert' x r))
main :: IO()
main = putStrLn . show $ fromList [8,3,10,1,6,4,7,14,13]
Splay the leftmost element and return its right child. You'll need a helper like pathToInserted
to return a list of L
s of the proper length.