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