Haskell deleting in a binary search tree

Question

So far I have come up with something like this. What I am trying to do here is get the right most or the leftmost element depending on which is available and swapping them with root and deleting the corresponding rightmost or left most element. I just need some help figuring out why it fails when I ask it to delete root of a tree but it works for all other cases and what does Irrefutable pattern failed mean?

If I do something like delt 3 Node 3 (Node 2 (Node 1 Empty Empty) Empty) (Node 4 Empty Empty) it gives an error like Node *** Exception: delt.hs:26:40-75: Irrefutable pattern failed for pattern (Main.Node rm (Main.Empty) (Main.Empty))

delt 2 a gives Node 3 (Node 1 Empty Empty) (Node 4 Empty Empty)

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)
treeIns :: (Ord a) => a -> Tree a -> Tree a
treeIns x Empty= Node x (Empty) (Empty)
treeIns x (Node a l r)
  | x == a = Node a l r
  | x < a = Node a (treeIns x l) r
  | x > a = Node a l (treeIns x r)

leftm :: Tree a -> Tree a
leftm Empty = Empty
leftm (Node a (Empty) (Empty)) = (Node a (Empty) (Empty))
leftm (Node a (l) (Empty)) = leftm l
leftm (Node a (l) (r)) = leftm l

rightm :: Tree a -> Tree a
rightm Empty = Empty
rightm (Node a (Empty) (Empty)) = (Node a (Empty) (Empty))
rightm (Node a (Empty) (r)) = rightm r
rightm (Node a (l) (r)) = rightm r


delt :: (Eq a, Ord a)=>a -> Tree a -> Tree a
delt x Empty = Empty
delt x (Node a (Empty)(Empty))
  | x== a = Empty
delt x (Node a l r)
  |x == a = (if l /= (Empty) then (let (Node rm (Empty) (Empty)) = rightm l in (Node rm (delt rm l) r)) else (let (Node rm (Empty) (Empty)) = l\
eftm r in (Node rm l (delt rm r)) ))
  |x>a = Node a (l) (delt x r)
  |x < a = Node a (delt x l ) r

Answer 1

Here is a similar implementation just for reference. (Without the delete part though)

-- a tree can be empty or contain a value with two other Trees
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

instance Functor Tree where
    fmap f EmptyTree = EmptyTree
    fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

-- create a Node with a value and two Empty subtrees (left and right)
singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

-- insert a new Node into a tree
insertInTree :: (Ord a) => a -> Tree a -> Tree a

-- insert into empty tree is equal to creating a new tree
insertInTree x EmptyTree = singleton x

-- pattern match on value and subtrees
insertInTree x (Node a left right)
    -- if element is equal to root element, return same tree
    | x == a = Node x left right

    -- if element is smaller than root, go to left
    -- subtree and check again.
    | x < a = Node a (insertInTree x left) right

    -- if element is bigger than root, go to right
    -- subtree and check again.
    | x > a = Node a left (insertInTree x right)

-- binary tree search
search :: (Ord a) => a -> Tree a -> Bool

-- search in EmptyTree is always False
search x EmptyTree = False

-- serach in a Node
search x (Node a left right)

    -- if element equals root element, great
    | x == a = True

    -- if element is smaller than root, continue search on the left side
    | x < a = search x left

    -- if element is bigger than root, continue search on the right side
    | x > a = search x right

-- create a test tree
myTree = foldr insertInTree EmptyTree [15,75,651,2,3,4,85,42,1,5,36,45,78,12,2]