APLicative programming with Naperian functors

Conference item

Much of the expressive power of array-oriented languages such as Iverson's APL and J comes from their implicit lifting of scalar operations to act on higher-ranked data, for example to add a value to each element of a vector, or to add two compatible matrices pointwise. It is considered a shape error to attempt to combine arguments of incompatible shape, such as a 3-vector with a 4-vector. APL and J are dynamically typed, so such shape errors are caught only at run-time. Recent work by Slepak et al. develops a custom type system for an arrayoriented language, statically ruling out such errors. We show here that such a custom language design is unnecessary: the requisite compatibility checks can already be captured in modern expressive type systems, as found for example in Haskell; moreover, generative type-driven programming can exploit that static type information constructively to automatically induce the appropriate liftings. We show also that the structure of multi-dimensional data is inherently a matter of Naperian applicative functors |lax monoidal functors, with strength, commutative up to isomorphism under composition|that also support traversal.

Authors: Gibbons, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: European Joint Conferences on Theory and Practice of Software
• Host title: European Symposium on Programming
• Journal: European Symposium on Programming
• Publication date: 2017-03-01
• Acceptance date: 2016-12-17
• DOI: 10.1007/978-3-662-54434-1_21