# Haskell Insert function for Binary Trees

4163 views
2

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.

7

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 left 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 left)``````

posted this