Haskell Tree help

Question

Could anyone please help me with my assignment questions? I've done most of it but I'm still stuck on these 3 questions.

Here is the question:

Consider the following types of search trees and balanced trees

data STree = Leaf | Node STree Int STree  
data Btree = Tip Int | Branch Btree Btree

whose constructors are subject to the following constraints:

• Values of the form Node left n right must have all integers in left being at most n and all integers in right being greater than n.
• Values of the form Branch left right must have a difference between the numbers of integers in left and right of at most one.

a) Define a recursive function stree :: [Int] -> STree that constructs a search tree from a list of integers.

b) Define a recursive function btree :: [Int] -> BTree that constructs a balanced tree from a non-empty list of integers.

c) Using merge, define a recursive function collapse :: BTree -> [Int] that collapses a balanced tree to give a sorted list of integers.

Please help me!!!

Thanks very much in advance!

Answer 1

Don't want to take all the fun, but here is my go at part a.

stree :: [Int] -> Stree
stree []     = Leaf
stree (x:xs) = let (left, right) = partition (<= x) xs
               in Stree (stree left) x (stree right)

It just takes the components that should be on the left and right and recursively builds the subtrees for each.

Assuming the use of sort is legit, then I'm pretty certain this works for part b.

btree :: [Int] -> Btree
btree (x:[]) = Tip x
btree xs     = let len = length xs `div` 2
                   ys = sort xs
               in Branch (btree (take len ys)) (btree (drop len ys))

Answer 2

stree = foldr insert Leaf
  where insert :: Int -> STree -> STree
        insert i (Node l i' r)  | i <= i'   = Node (insert i l) i' r
                                | otherwise = Node l i' (insert i r)
        insert i (Leaf) = Node Leaf i Leaf

This isn't a very efficient solution, nor does it produce a very balanced tree, but it's a good example of how to iteratively build a data structure in Haskell. Using foldr to handle the iteration for us, we insert one element at a time into the tree, passing the new tree into the function that builds the next. We descend through the tree, until we find a leaf, and replace that Leaf with a Node to hold the given value.

Answer 3

These are recursive data structures. Let's start with the Search Tree:

data STree = Leaf | Node STree Int STree

and all values in the left must be less than the parent, which must be less than all values in the right. Can you write down the answers for stree [] and stree [x]? How far can you go?

I'll start:

stree [] = Leaf
stree [x] = Node Leaf x Leaf
stree ([x,y]) = if x < y then Node Leaf x (Node Leaf y Leaf) else Node (Node Leaf y Leaf) x Leaf

That sort of nested if and node construction is going to get awful pretty fast. What common sub-expressions can we factor out?

singleton x = Node Leaf x Leaf

That makes life a little easier:

stree [] = Leaf
stree [x] = singleton x
stree ([x,y]) = if x < y then Node Leaf x (singleton y) else Node (singleton y) x Leaf

But it doesn't attack the basic problem of the nested if. One common trick for lists is to take them one element at a time. Can that work for us?

addToSTree :: Int -> STree -> STree
addToStree x Leaf = singleton x
addToStree x (Node left n right) | x < n = ...
                                 | otherwise = ...

Can you fill in the dots above? Once you have that, then it'll be time to make a loop over the contents of the list.

BTree can be solved similarly.