Skip to main content

APLicative Programming with Naperian Functors

Jeremy Gibbons

Abstract

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 array-oriented 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.

Book Title
European Symposium on Programming
Editor
Hongseok Yang
Month
April
Pages
568−583
Series
LNCS
Volume
10201
Year
2017
Keynote at Lambda World 2017 in Cadiz
Talk at NPFL workshop at ICFP 2018