Treetable: a case-study in q

17 Jun 2014 | , ,
Share on:

large green tree

Looking through the archives we came across this excellent post by Stevan Apter to his blog, “No Stinking Loops.” It’s a helpful reference piece, re-published by  Vector, the journal of the British APL Association as well, with an apt introduction:

“This article is the first in an occasional column [from] No Stinking Loops. Stevan Apter is one of the programmers Jeffry Borror referred to as “the q gods” in his textbook q for Mortals. The world of q programming has so far been largely hidden behind corporate non-disclosure contracts. Vector is glad to see it opening and proud to be publishing this.” preface by the editors of Vector.

0. Introduction

A treetable is a table with four additional properties.

Firstly, the records of the table are related hierarchically. Thus, a record may have one or more child-records, which may in turn have children. If a record has a parent, it has exactly one. A record without a parent is called a root record. A record without any children is called a leaf record. A record with children is called a node record.

Secondly, it is possible to drill down into a treetable. If a record is a parent, then some of its columns may be rollups of its child-records. By drilling down into a parent-record, it is possible to inspect the elements which are aggregated in the parent. All rollups are performed on the leaves of the tree rather than on the immediate children. This means that tree-construction can be ‘lazy’: not all intermediate rollups from parent to leaves need exist.

Thirdly, treetables have state. If the user drills down into the tree along a particular path, then closes a node along that path, the records on that path become invisible. If the user re-opens that parent, then the nodes along that path will become visible if they were visible before the parent was closed. In other words, closing an open parent does not destroy the visibility state of its children.

Fourthly, a treetable is naturally sorted in a way that is an extension of ordinary table sort. Intuitively, the sort of a treetable is a structure-preserving sort of the ‘blocks’ out of which it is composed. The sort is structure-preserving because the parent-child relation between records is preserved even though record-order is not. I’ve included an explanation of how such a multi-column sort works.

The treetable is a natural candidate for a control in a non-procedural data-driven GUI. K and q have a long tradition of such GUIs, stretching back to A+ and the native K3 GUI. The examples in this paper are abstracted from an implementation of a GUI recently developed for q. But the case-study is meant to stand alone, as an exercise in pure data design. In a future instalment, I hope to show how such designs are smoothly integrated into a data-driven GUI.

More here.