Haskell Insert function for Binary Trees

Question

I'm trying to create a function called "insertm" that is supposed to insert a key and value into a binary tree.If the key already exists it should return "nothing". If not it should insert the key and value into the tree based on it's value. I was able to get most of it to go, but I'm getting an error that i'm not sure how to fix.

Here is an example:

      TestQ4> insertm 25 "vw" t5
      Just (10:"ghi")<$,(30:"def")<(20:"abc")<$,(25:"vw")>,$>>
      TestQ4> insertm 20 "vw" t5
      Nothing

Here is my code:

     data BinaryTree a b = Leaf | Node a b (BinaryTree a b) (BinaryTree a b) 

     insertm :: (Ord a, Show a, Show b) =>
     a -> b -> BinaryTree a b -> Maybe (BinaryTree a b)

     insertm val key Leaf = Just (Node val key Leaf Leaf)
     insertm x y (Node val key left right)
          | x == val = Nothing
          | x < val = Just (Node val key (insertm x y left) right)
          | otherwise = Just (Node val key left (insertm x y right))

And this is the error i get:

       * Couldn't match expected type `BinaryTree a b'
              with actual type `Maybe (BinaryTree a b)'
       * In the fourth argument of `Node', namely `(insertm x y right)'
         In the first argument of `Just', namely
           `(Node val key left (insertm x y right))'
         In the expression: Just (Node val key left (insertm x y right))
       * Relevant bindings include
          right :: BinaryTree a b (bound at TestQ4.hs:101:32)
          left :: BinaryTree a b (bound at TestQ4.hs:101:27)
          key :: b (bound at TestQ4.hs:101:23)
          val :: a (bound at TestQ4.hs:101:19)
          y :: b (bound at TestQ4.hs:101:11)
          x :: a (bound at TestQ4.hs:101:9)
         (Some bindings suppressed; use -fmax-relevant-binds=N or -fno-max- 
            relevant-binds)

          | x < val = Just (Node val key (insertm x y left) right)
                                          ^^^^^^^^^^^^^^^^

I also get the error for my otherwise case. So im a bit stuck any help would be appreciated.

Answer 1

The problem is that (insertm x y left) is a Maybe (BinaryTree a b) in:

 | x < val = Just (Node val key (insertm x y left) right)

not a BinaryTree a b, you thus can not just construct such a BinaryTree with a Maybe (BinaryTree a b) as subtree.

You can however "unpack" the value, and then use this, like:

insertm :: (Ord a, Show a, Show b) => a -> b -> BinaryTree a b -> Maybe (BinaryTree a b)
insertm val key Leaf = Just (Node val key Leaf Leaf)
insertm x y (Node val key left right)
    | x == val = Nothing
    | x < val = case insertm x y left of
        Just l -> Just (Node val key l right)
        Nothing -> Nothing
    | otherwise =  case insertm x y right of
        Just r -> Just (Node val key left r)
        Nothing -> Nothing

The above pattern is quite popular, we can use fmap :: Functor f => (a -> b) -> f a -> f b here, to map the x in Just x to a Just (f x) and map Nothing on Nothing:

insertm :: (Ord a, Show a, Show b) => a -> b -> BinaryTree a b -> Maybe (BinaryTree a b)
insertm val key Leaf = Just (Node val key Leaf Leaf)
insertm x y (Node val key left right)
    | x == val = Nothing
    | x < val = fmap (flip (Node val key) right) (insertm x y left)
    | otherwise = fmap (Node val key left) (insertm x y right)

or like @JonPurdy says:

insertm :: (Ord a, Show a, Show b) => a -> b -> BinaryTree a b -> Maybe (BinaryTree a b)
insertm val key Leaf = Just (Node val key Leaf Leaf)
insertm x y (Node val key left right)
    | x == val = Nothing
    | x < val = Node val key <$> insertm x y left <*> pure right
    | otherwise = Node val key left <$> insertm x y right

The (<$>) is function that is equivalent to fmap, and (<*>) :: f (a -> b) -> f a -> f b is a function that takes a here a Maybe (BinaryTree a b -> BinaryTree a b), and applies the function f wrapped in the Just with the value x wrapped in the right Just and returns Just (f x) given the two are thus Justs, if one of the two is a Nothing (or both), then it will return Nothing.