An alternative layout method is depicted in the illustration below:
Find out the rules and write the corresponding function. Hint: On a given level, the horizontal distance between neighboring nodes is constant.
Use the same conventions as in problem P64 and test your function in an appropriate way.
layout :: Tree a -> Tree (a, Pos) layout t = layoutAux x1 1 sep1 t where d = depth t ld = leftdepth t x1 = 2^(d-1) - 2^(d-ld) + 1 sep1 = 2^(d-2) layoutAux x y sep Empty = Empty layoutAux x y sep (Branch a l r) = Branch (a, (x,y)) (layoutAux (x-sep) (y+1) (sep `div` 2) l) (layoutAux (x+sep) (y+1) (sep `div` 2) r) depth :: Tree a -> Int depth Empty = 0 depth (Branch a l r) = max (depth l) (depth r) + 1 leftdepth :: Tree a -> Int leftdepth Empty = 0 leftdepth (Branch a l r) = leftdepth l + 1
The auxiliary function is passed the x- and y-coordinates for the root of the subtree, the horizontal separation between the root and its child nodes, and the subtree itself. It returns the subtree annotated with positions.