Convert a sorted list to a binary tree

Question

I have encoded the following tree:

as

Unir (Unir (Unir Vacio 1 Vacio) 2 Vacio) 5 (Unir Vacio 8 Vacio)

using the following Algebraic Data Type:

data ABB a = Vacio | Unir (ABB a) a (ABB a)

However, I defined the following function:

list2ABB :: Ord a => [a] -> ABB a
list2ABB [] = Vacio
list2ABB (x:xs) = insertABB x (list2ABB xs)

and when I execute:

list2ABB [1,2,5,8]

I get a different result:

Unir (Unir (Unir (Unir Vacio 1 Vacio) 2 Vacio) 5 Vacio) 8 Vacio

Is there something wrong with my definition or encoding ?

EDIT:

Thank you everyone for the answer. Replying one of the queries, I am posting my definition of insertABB:

insertABB :: Ord a => a -> ABB a -> ABB a
insertABB x Vacio = Unir Vacio x Vacio
insertABB x (Unir ti y td)
    | x < y     = Unir (insertABB x ti) y td
    | x > y     = Unir ti y (insertABB x td)
    | otherwise = Unir ti y td

Answer 1

Your insertABB function each time locates how the item should be inserted without balancing.

Since the list is sorted, and you insert it in a foldr like way, it will insert the items right-to-left. It will thus start with an empty tree, and then insert the rightmost element. This means that the root element will be the largest item in the list.

Next we insert an element that is smaller than the root element, so that will be the root element of the left subtree of the root tree. Next again an element that is smaller, so the left subtree of the left subtree of the root.

If the process finishes, this thus means that all right subtrees of all nodes will be empty, and the data is inserted in a linked-list like manner.

If you want to produce a balanced tree, you can work with a balancing tree, like an AVL-tree ^[wiki].

Since the list is already sorted, we can construct a complete tree. We do this by first locating the item in the middle of the list, take that as root element, and then insert the sublists as subtrees.

We can for example work with a hare and tortoise approach:

hareTortoise :: [a] -> ([a], [a])
hareTortoise xs = go xs xs
  where
    go [] ts = ([], ts)
    go [_] ~(t : ts) = ([t], ts)
    go (_ : _ : hs) ~(t : ts) = let ~(ya, yb) = go hs ts in (t : ya, yb)

We can then use this to construct the tree with:

constructSorted :: [a] -> ABB a
constructSorted [] = Vacio
constructSorted [x] = Unir Vacio x Vacio
constructSorted xs = let ~(ls, ~(r:rs)) = hareTortoise xs in Unir (constructSorted ls) r (constructSorted rs)