Haskell 2-3-4 Tree

Question

We've been asked to create a 2-3-4 tree in Haskell, as in write the data type, the insert function, and a display function.

I'm finding it very difficult to get information on this kind of tree, even in a language I'm comfortable with (Java, C++).

What I have so far -

data Tree t = Empty 
    | Two t (Tree t)(Tree t) 
    | Three t t (Tree t)(Tree t)(Tree t) 
    | Four t t t (Tree t)(Tree t)(Tree t)(Tree t) deriving (Eq, Ord, Show)


leaf2 a = Two a Empty Empty
leaf3 a b = Three a b Empty Empty Empty
leaf4 a b c = Four a b c Empty Empty Empty Empty

addNode::(Ord t) => t ->  Tree t -> Tree t
addNode t Empty = leaf2 t
addNode x (Two t left right)
    | x < t = Two t (addNode x left) right
    | otherwise = Two t left (addNode x right)

This compiles but I'm not sure if it's correct, but not sure how to start writing the insert into a three node or four node.

The assignment also says that "deriving show" for the display function is not enough, that it should print out the tree in the format normally seen in diagrams. Again, unsure on the way to go with this.

Any help or direction appreciated.

Did you read the wikipedia article about 2-3-4 trees? Did you understand its description of the insertion algorithm? If so could you describe where exactly you're stuck trying to implement it in Haskell? If not, please explain which part you did not understand. — sepp2k
Oh and regarding the Show instance: Do you know how to define instances in Haskell? Do you have an idea of what a show function for your Tree should look like? What problems did you encounter while trying to implement it? — sepp2k
Also, take a look at the drawTree function in the standard Data.Tree module, and think about how you might adapt that to your type. — C. A. McCann
I'll admit, the Wikipedia article does look like it's pretty confusing. You'll probably have better luck with one of the references linked in the article. — Edward Z. Yang
The main problem I'm having at this point is inserting into a 4 node. As I can't go back up the tree I need to check ahead to see if the next node is a 4 node so I can keep the data to split the node. — user478087

Dan Burton Dan Burton · Accepted Answer · 2011-12-20T17:47:21

I know nothing about 2-3-4 trees, but for the Three node, you would start with something like this:

addNode t (Three x y left mid right)
  | cond1 = expr1
  | cond2 = expr2
  (etc)

What cond1, cond2, expr1, and expr2 are, exactly, is dependent on the definition of what a 2-3-4 tree is.

As for a show method, the general outline would be this:

instance (Show t) => Show (Tree t) where
  show Empty = ...
  show (Two x l r) = ...show x...show l...show r...
  show (Three x y l m r) = ...
  show (Four x y z l m n r) = ...

The implementation depends on how you want it to look, but for the non-Empty cases, you will probably invoke show on all of the components of the tree being shown. If you want to indent the nested parts of the tree, then perhaps you should create a separate method:

instance (Show t) => Show (Tree t) where
  show = showTree 0

showTree :: Show t => Int -> Tree t -> String
showTree n = indent . go
  where indent = (replicate n ' ' ++)
        go Empty = "Empty"
        go (Two x l r) = (...show x...showTree (n+1) l...showTree (n+1) r...)
        (etc)

Haskell 2-3-4 Tree

2 Answers