Inserting list into Binary Tree in Haskell

Question

Basically, I'm trying to insert elements from the list into the binary tree one by one, or that's what I thought it should be done when inserting list to the tree.

Here is my tree for inserting:

data Tree = EmptyTree | Node Integer Tree Tree deriving (Show, Eq, Ord)
insertElement x EmptyTree = Node x EmptyTree EmptyTree
insertElement x (Node a left right) = if x == a
                                  then (Node x left right)
                                  else if x < a
                                  then (Node a (insertElement x left) right)
                                  else
                                  Node a left (insertElement x right)

and I thought I could use map to get elements from list and insert it into the list.

Something like this: inserter x = map (insertElement x EmptyTree) where I get list with inserter and insert it into the list.

But, this code is pretty much incorrect I think, and I was wondering how can I do this?

Answer 1

If you would use inserter xs = map (`insertElement` EmptyTree) you will create a list of trees where each item is inserted once.

What you can do is use foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b or foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b to each time pass the accumulator, the thus far build up list, and thus insert the next item, so:

inserter :: Foldable f => f Integer -> Tree
inserter = foldr insertElement EmptyTree

or:

inserter :: Foldable f => f Integer -> Tree
inserter = foldl (flip insertElement) EmptyTree

It might however make more sense to allow to specify the base tree, and thus using inserter to insert a Foldable of items to a Tree that might already contain items, for example:

inserter :: Foldable f => Tree -> f Integer -> Tree
inserter = foldl (flip insertElement)