Trees, Elm, whiteboardable algorithms
I’ve been idly thinking about a blog post about the asymptotic complexity of running every street in a city, and in order to illustrate it, I need to visualize some trees: theoretical data structure trees. Since that post is still in the process of baking, here’s a side-product: tree layout.
Bill Mill wrote about presentable trees and d3.hierarchy contains lots of smart implementations, but I wanted to try my hand at a whiteboardable algorithm - something that I could implement quickly and easily, using basic math.
So, to begin with, here’s a naïve layout, which places each node ‘down and to the left/right’ of its parent. I’ve tweaked it to highlight conflicting node positions, where one of the subtrees was larger than the simple layout could handle:
I wanted a layout that didn’t have explicitly intersecting nodes, and wanted to do it with high school geometry.
The radial layout is relatively simple: nodes are numbered from left-to-right and assigned a depth, and then laid out on evenly-spaced points along the curvature of concentric circles. We use our old friends cosine and sine to compute the X & Y coordinates at each point.
The source for the binary tree and radial tree is open.
It was lots of fun doing these layouts in Elm, a curious new functional programming language that I previously implemented undo & redo within. I’m far from an expert in the language, but have some take-aways:
Forward function application
Elm’s forward function application method, |> is great: it lets you express code like
(List.map drawEdge (List.filter noRoot (collectNodePositions tree 0 0)))
collectNodePositions tree 0 0 |> List.filter noRoot |> List.map drawEdge
The forward function application operator is lovely: it makes chaining methods a style choice: library authors don’t have to choose functional style or chaining style.
Rethinking functionality and data
Something that I’ve found myself increasingly thinking about is the intermixing of function and data. For instance, in this codebase I was computing the X/Y location of a point, so:
[ (cos splayDegree) * depth * ringRadius) , (sin splayDegree) * depth * ringRadius) ]
After learning my first bits of functional programming, there was still an assumption baked deep in my mind that methods like
map were intended to map data over functions. Like you’d have an array of strings and you’d map them over
toFloat to parse them into an array of floating point numbers.
But breaking this assumption has been really beneficial: so, in this case, expressing this logic as mapping functions, cos & sin, over data, the radian value.
List.map (\x -> (x splayDegree) * depth * ringRadius) [ cos, sin ]
These tree algorithms feature one case of that: randomness. Non-deterministic data like time and randomness can sneak into Redux’s reducers by carelessness, whereas in Elm, the way you acquire random values is well-considered and extremely strict: you can’t simply ‘generate a random number’: you emit a command that causes a random number to be generated and sent through the loop.