Tom MacWright

tom@macwright.org

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)))

as:

collectNodePositions tree 0 0 |> List.filter noRoot |> List.map drawEdge

JavaScript’s Array class has a filter method on its prototype, in the object-oriented tradition, so you could express this chaining with its methods. But there exists a schism between ‘functional’ utilities like date-fns versus chainable OOP APIs like moment. And there are libraries like lodash that offer wrappers to do something similar, but they do it in a relatively tricky way.

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 ]

Effects

Elm could be described as a cross between Haskell and JavaScript, with redux’s concepts supported in deep levels of the language. Where redux has a bunch of boilerplate, Elm is incredibly succinct. And while you can force yourself to be strict and stick to safe patterns in JavaScript, Elm is strict and safe by default.

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.

April 28, 2017  @tmcw