Drawing a binary tree structure in haskell

Question

I am working in Haskell and attempting to draw a tree data structure which uses 'nodes' which have one or two children trees and 'tips' which are empty trees.

The drawing process takes the highest level node and draws a straight line upwards whose length is equal to the value of the node itself.

Tips don't have lines drawn for them.

From this initial line, the children of the node are drawn at an angle 'd' to the parent line. The lines are angled left for the left children and right for the right children of the node. The length of these lines are equal to the value of each child respectively.

This repeats for each node down the tree structure.

My problem is that we are using a single cursor (which can move forwards, backwards and rotate) to draw the trees. Therefore drawing the entire tree seems to require some kind of algorithm for systematically drawing out a tree (e.g prioritising drawing children on the left until a tip is reached, and then back tracking and drawing a right child)

However this approach seems extremely complex because Haskell is unable to store variables which would be required to remember which parts of the tree the cursor has already drawn.

Is there an algorithm which is capable of achieving this? If not, is there some other way to draw a tree using a single cursor on a 2d plane?

Thanks for any help.

It sounds like you want an algorithm for a "depth-first tree traversal", and one technique that can help you with "variables which would be required to remember which parts of the tree the cursor has already drawn" is to use a zipper. — jberryman
If every drawing function that you write would afterwards move the curser back to its original position, no state needs to be kepts. Simply recurse over the tree and write it out. But it would be easier to help if you show some code (what is your drawing API, what are your data types). — Joachim Breitner
@JoachimBreitner I am not sure what you mean, could you elaborate? — James

adamse adamse · Accepted Answer · 2015-11-22T19:04:16

Assuming this is your drawing API:

forward :: Int -> IO ()
backward :: Int -> IO ()
rotate :: Double -> IO ()

And from your description the tree datatype looks like this:

data Tree
  = Bin Tree Int Tree
  | Tip

Then you can recursively draw the left subtree followed by the right as you suggested: (a "pre-order depth-first" traversal of the tree)

draw :: Double -- ^ Angle
     -> Tree
     -> IO ()
draw d Tip = return () -- no lines for Tips
draw d (Bin l v r) = do
  -- draw this node's line
  forward v

  -- draw left subtree
  rotate d
  draw d l

  -- draw right subtree
  rotate (2 * (-d))
  draw d r

  -- return to starting position
  rotate d
  backward v

Drawing a binary tree structure in haskell

1 Answers