Generic Programming on the Nesting Structure of Arrays

Multi-dimensional arrays lack expressiveness with respect to logical layers of data; they provide no means to encode that, for example, a three-dimensional array of double values is used to represent a matrix of RGB-values. Existing approaches, e.g., boxing and unboxing the inner dimensions of an array, allow the programmer to encode additional structure, but make programming on nested arrays a tedious and error-prone task: nesting and de-nesting operations have to be explicitly encoded in function applications. Apart from the additional work spent on program specification, this scattered encoding of structural information renders refactoring of widely used data structures difficult. We propose a new means to model the structure of homogeneously nested arrays in the type system, rather than the actual data. We exploit this additional type knowledge for subtypingbased function overloading, liberating the programmer from explicitly encoding nesting operations in function applications. Furthermore, we propose and demonstrate a nesting-structure generic programming extension that allows us to define user-defined homogeneously nested array-types without the usual boiler-plate code.