Are Arrays Functions?

Summary

Posted on January 16, 2026 When I was a youngster first perusing the Haskell documentation for arrays, I was amused to find the following description of just what these mysterious things might be: Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers. I found this to be a hilariously obtuse and unnecessarily formalist description of a common data structure. Now, older, wiser, and well ensconced in the ivory towers of academia, I look at this description and think that it is actually a wonderful definition of the essence of arrays! And given that this sentence still lingers in my thoughts so many years later, who can say that it is not actually a far better piece of documentation than some more prosaic description might have been? To a language designer, the correspondence between arrays and functions (for it does exist, independent of whether you think it is a useful way to document them) is alluring, for one of the best ways to improve a language is to make it smaller. Our goal is not to unify the representation of arrays and functions, of course - nobody would seriously claim that representing an array via some Church-encoding is a good idea in a supposedly practical programming language. Instead, what might be worthwhile considering is what consequences might arise from unifying arrays and functions at the syntax or type level, and why Futhark ultimately has not done so. There is some prior work to consider. The array language K has a syntactic unification of arrays and functions, as both are indexed/applied with the notation f[x]. This is however pretty much where the correspondence stops. As an APL derivative, K programming is based on bulk operations on entire arrays, rather than element-at-a-time programming, and the operators that perform these bulk operations cannot be applied to functions. And of course, K has no type system, so the correspondence is purely syntactic. Dex ...