1Trees
2=====
3Trees are an opinionated way of thinking about hierarchical data.
4
5An interior node of a tree is a collection: a list, record or dictionary.
6Nested collections can model many important compound data types:
7 * a vector is a list of numbers
8 * a matrix is a list of vectors of the same count
9 * a table is a list of records with the same fields
10
11Array theory (derived from APL) is a powerful framework for parallel
12transformation of bulk data. However, tree theory is distinct from array
13theory: all collections have the same status (records and dictionaries are
14not scalars), so tree operations are not vectorized over lists of records
15and dictionaries.
16
17There are two approaches to data transformation. You can query and update a
18tree using lenses, or transform it using a pipeline of bulk operations.
19 * Some tree transformations are reversible: you can link the elements of the
20   output tree back to the corresponding elements of the input tree. Thus the
21   transformation is a lens, and you can use it to update the input tree.
22 * Some tree transformations are not reversible: they are functions but
23   not lenses.
24
25Tree theory supports both approaches.
26 * Lenses support imperative style interfaces for incremental tree update.
27   Eg, assignment statements like 'R.foo := x' and 'A[i] := x'.
28   We need these interfaces for mapping imperative-style GPU programming
29   languages, APIs and frameworks onto Curv.
30 * Lenses support modular, composable pure functional GUIs. A lens is a
31   modular data access and update abstraction that connects a model with
32   a view and controller.
33 * Data transformation pipelines, inspired either by APL or by functional
34   programming (map, reduce, filter), are well known and popular, and are
35   also being used for GPU programming. Tree theory also supports this style.
36
37In order to integrate the two approaches, it would be good if Lenses can be
38modelled as functions with additional structure.
39