I need help on display an AVL Tree in Haskell -


data avl t = empty | node t (avl t) (avl t) int                  deriving (eq, ord, show)   insertnode :: (ord a) => -> avl -> avl insertnode x empty = node x empty empty 0 insertnode x (node n left right balancefactor)     | x < n = let leftnode = insertnode x left               in                balancetree (node n leftnode right ((treeheight leftnode) - (treeheight right)))     | otherwise = let rightnode = insertnode x right                   in                    balancetree (node n left rightnode ((treeheight left) - (treeheight rightnode)))  findnode :: avl -> findnode empty = error "findnode empty" findnode (node _ _ _) =  findleftnode :: avl -> avl findleftnode empty = error "findleftnode empty" findleftnode (node _ left _ _) = left  findrightnode :: avl -> avl findrightnode empty = error "findrightnode empty" findrightnode (node _ _ right _) = right  findbalancefactor :: avl -> int findbalancefactor empty = 0 findbalancefactor (node _ _ _ bf) = bf  treeheight :: avl -> int treeheight empty = 0 treeheight (node _ left right _) = 1 + (max (treeheight left) (treeheight right))  balancetree :: avl -> avl balancetree empty = empty balancetree (node r empty empty bf) = node r empty empty bf balancetree (node r left right bf)     | bf == -2 && rbf == -1 = let rl = (findleftnode right)                               in                                (node (findnode right)                                                               --                                (node r left rl ((treeheight left) - (treeheight rl)))                               -- "right right" case                                (findrightnode right)                                ((1 + (max (treeheight left) (treeheight rl))) - (treeheight (findrightnode right)))                                )     | bf == -2 && rbf == 1 = let rl = findleftnode right                                  rr = findrightnode right                              in                               (node (findnode (rl))                                                                 --                               (node r left (findleftnode rl) ((treeheight left) - (treeheight (findleftnode rl))))  -- "right left" case                               (node (findnode right) (findrightnode rl) rr ((treeheight (findrightnode rl)) - (treeheight rr)))                               ((max (treeheight left) (treeheight (findleftnode rl))) - (max (treeheight (findrightnode rl)) (treeheight rr)))                               )     | bf == 2 && lbf == 1 = let lr = findrightnode left                             in                              (node (findnode left)                                                                  --                              (findleftnode left)                                                                    -- "left left" case                              (node r lr right ((treeheight lr) - (treeheight right)))                              ((treeheight (findleftnode left)) - (1 + (max (treeheight lr) (treeheight right))))                              )     | bf == 2 && lbf == -1 = let lr = findrightnode left                                  ll = findleftnode left                              in                               (node (findnode lr)                                                                              --                               (node (findnode left) ll (findleftnode lr) ((treeheight ll) - (treeheight (findleftnode lr))))   -- "left right" case                               (node r (findrightnode lr) right ((treeheight (findrightnode lr)) - (treeheight right)))                               ((max (treeheight ll) (treeheight (findleftnode lr))) - (max (treeheight(findrightnode lr)) (treeheight right)))                               )     | otherwise = (node r left right bf)     rbf = findbalancefactor right           lbf = findbalancefactor left 

this current state of implementation of avl tree. normal input usually:

insertnode 4 (node 2 (node 1 empty empty 0) (node 3 empty empty 0) 0) 

which results in:

node 2 (node 1 empty empty 0) (node 3 empty (node 4 empty empty 0) (-1)) (-1) 

i want have function display inputted tree in neat fashion, example, tree directly above:

2  1   empty   empty  3   empty   4    empty    empty 

does have suggestions how implemented? wish nodes displayed only, , once reaches end of branch prints "empty". i've hit quite brick wall , tried few attempts little success.

edit: hi guys, quick responses. suggestions work, however, implementation of displaying tree without use of packages or libraries. sorry not clarifying this!

what you're looking pretty printer! use “pretty” package on hackage.

import text.prettyprint 

your tree pretty simple structure, i'm going define in 1 shot. there many helpful combinators in text.prettyprint though, check them out! they're easy use in ghci too, when don't understand documentation, give whirl.

prettytree :: show t => avl t -> doc prettytree empty          = text "empty" prettytree (node t l r _) = text (show t)                             $+$ nest 1 (prettytree l)                             $+$ nest 1 (prettytree r) 

doc has show instance fine with, or can use more powerful styling functions.

λ let tree = node 2 (node 1 empty empty 0) (node 3 empty (node 4 empty empty 0) (-1)) (-1) λ prettytree (tree :: avl int) 2  1   empty   empty  3   empty   4    empty    empty 

if wanted without external dependencies, crib style sub in own shims combinators.

type doc = [string]  text :: string -> doc text = pure  indent :: doc -> doc indent = map (' ':)  vertical :: doc -> doc -> doc vertical = (++)  prettytree :: show t => avl t -> doc prettytree empty          = text "empty" prettytree (node t l r _) = vertical (text (show t))                                      (indent (vertical (prettytree l)                                                        (prettytree r)))  render :: doc -> string render = concat 

Comments