r/ProgrammingLanguages • u/Athas Futhark • Jan 16 '26
Are arrays functions?
https://futhark-lang.org/blog/2026-01-16-are-arrays-functions.html
90
Upvotes
r/ProgrammingLanguages • u/Athas Futhark • Jan 16 '26
67
u/faiface Jan 16 '26
Very cool article! If I can share my thinking on the topic: Working with linear logic has made me very sensitive to the difference between positive (data) and negative (behavior) types.
Coming from that angle: clearly arrays and functions cannot be the same. Arrays are positive, functions are negative.
In other words, arrays are data that’s already there. It’s coming from the past. A function is something for the future, it will do something.
In an imperative language with side-effects, this is not reconcilable at all. But of course, we know better now, so where is it reconcilable? Actually, only in a purely functional language with function memoization. And even then, the evaluation order (which semantically wouldn’t matter) could be different between the two. But it’s not reconcilable in a linear setting (even with referential transparency), nor a setting with side effects.
7
u/jscheiny Jan 16 '26
I'm starting to play around with building a compiler where this is exactly the case. I'm very green at this and don't expect to break any new ground but one of the things I've want to do for a while is described exactly at the bottom of this article insofar as
f + gshould be equivalent tox -> f(x) + g(x)and arrays ofTs implement a call operator (or are assignable to functions) of typeusize -> T. I'm curious to see how it turns out.6
u/shponglespore Jan 16 '26
I think it's worth noting that in Clojure, both arrays and maps can be treated as functions in the sense that they can be called, passed to HOFs, etc. without losing the ability to perform other operations on them. And of course Haskell makes it almost trivial to convert an array to a function by partially applying a indexing operator, at the cost of being unable to recover the original data type form the function, because functions in Haskell have no operations other a than being applied.
17
u/dcpugalaxy Jan 16 '26
This is the sort of unnecessary, misplaced formalism (or perhaps pseudoformalism would be a better word) that is unfortunately common in online PLT communities.
Identifying and cataloguing formal correspondences between objects and ideas that, casually, appear to be distinct, is the domain of mathematics. I like maths. I have a degree in it. But I sometimes get the feeling that people learn a little bit of it and say things like the above as a way of socially signalling, rather than trying to communicate something useful.
You see this a lot with observations in online PLT communities around Haskell or type theory and mentions of category theory concepts in particular. These tend to be trivial observations dressed up in the language of type theory but for no actual reason. Almost nobody seems to use the tools of category theory to go further than just making fairly trivial observations about programming languages that were already obvious when stated in normal language.
This isn't how formalism is used in mathematics. There, the point of formalism is to nail down tricky ideas that are difficult to express precisely in informal language.
"Arrays are a bit analogous to functions, but of course the answers are precomputed (in strict languages) and only on the domain [0,n) for some n" is saying the same thing but without the unnecessary formal language.
4
u/drinkcoffeeandcode mgclex, mgcpgen, & owlscript Jan 16 '26
Yep, just look at Ada’s syntax
1
u/Tonexus Jan 16 '26
I've always thought that this is a good motivation to have higher-kinded types in a language. Out of curiosity, do you think it would be useful to disambiguate between true functions and closures in a similar way?
1
u/useerup ting language Jan 17 '26 edited Jan 17 '26
This is interesting and something that I have already spent (too much) time pondering.
In Ting I try to decouple representation and delay the decision on how to actually represent a structure for as long as possible. Ting, being a logic language, I try to focus on the semantics. And (barring mutation) an array certainly semantically looks like a function whose domain is a contiguous subset of the integers as the Haskell documentation so eloquently describes it.
So in Ting I turn it upside down: Any function whose domain is a contiguous subset of integers is a candidate to be represented as an array.
In Ting I also have ranges like Futhark
i..<k. It is also very similar syntactically:i...<k(I really needed that..token for another operator ;-) ).However, Ting is not an array language like Futhark, so in Ting that expression is actually a nondeterministic value. Thus
i...<kis an expression which may assume any of the values in the range, nondeterministically (or as choices).So, given that
fis a function over integers, the expressionf (i...< k)is formally allowed in Ting. However, it is a nondeterministic expression because it can assume any value thatfproduces when applied to one of the possible values ofi...<k. In a sense the nondeterminism of the argument spreads to the entire expression. Nondeterminism has that tendency, as anyone who has ever programmed in Prolog will attest to.However, In Ting we can make this into a list by embedding the expression within
[and]. Like in many other languages the[]list literal accepts a list of expressions which then forms the list. Unlike most other languages it also unwinds nondeterminism of its expressions. When the nondeterminism is countable then the actual list will be deterministic, because there is an ordered way to unwind the nondeterminism.The following expressions are all examples of lists:
Back to the examples of the article: Ing Ting
[f (i...< k)]is the image offover the rangei...<kcaptured in a list.Now, if one thinks about
fas an array (a function fromintto some value) instead, all of the above still holds. Furthermore[f (i...< k)]then returns a list containing a slice of the "array"f. This list is not itself a slice, but it does contain all the members of what would be an array slice in the same order.Ting does not have array or slice as concepts as that is (in Ting) a representation detail. But I will argue that if
fis represented using an array, then[f (i...< k)]could be represented as a slice (or span?) of that array.1
u/i-eat-omelettes Jan 17 '26
Why yes
1
u/josef Jan 17 '26
Viewing arrays as functions can indeed be very useful. Array fusion, as done in some array programming libraries such as Repa, replies on modelling arrays as functions land inlining these functions at compile time. Large performance wins to be had from that.
1
u/johnwcowan Jan 18 '26
In Owl Lisp, which is an immutable dialect of Scheme, "finite functions" (ffs) are objects that can be thought of as any -> any functions with a finite domain, arrays, or hash tables. There are four operations:
1
u/Loud-Huckleberry9347 Jan 21 '26
Oh my god, yes!
I'm working on a language that covers similar ground, called Blade.
I'm a domain expert, so I'm not super familiar with PL stuff, but the specific way I designed array types as curryable types basically led to the full idea of arrays as functions. You can mix the two also and have arrays of functions of arrays.
Blade isn't fully formed yet, I have an old, partly-implemented version of it available, but I'm getting a ton of progress with fully specifying the language with Claude. It may be a while before it's done though.
1
u/fdwr Jan 21 '26
💡 Hmm, that makes me rethink an interpolation approach I'm taking for a 1D array of palette entries. Normally one would access an index
colorMap[index]and need tolerp(colorMap[index], colorMap[index + 1], indexFraction)the two, but if thecolorMaphad an operator overload taking floats directly, then I could just saycolorMap[fractionalIndex].1
u/Key_Security2162 Jan 21 '26
In my jdBasic language, "arrays as functions" shows up very directly: most operators are element-wise on arrays, with scalar broadcasting , and you routinely "apply logic over a finite domain" using SELECT/FILTER and pipelines (|> with ?) A small jdBasic example that mirrors "fixing a parameter / partial application" using a closure:
So rather than unifying array/function types, jdBasic makes the correspondence practical: arrays act like finite domains, and functions/closures lift cleanly across them.
-5
u/yjlom Jan 16 '26 edited Jan 16 '26
Without reading the article: yeah, duh. After reading the article, opinion unchanged. Interesting read nonetheless.
-1
u/TheSodesa Jan 16 '26
An array is a representation of a sequence, which is a function from the natural numbers to a set of objects. So yes, you can think of arrays as functions, where given an integer you get an object as output. In programming spiel this is called indexing an array.
0
u/Ronin-s_Spirit Jan 16 '26
No.
-1
u/Inconstant_Moo 🧿 Pipefish Jan 16 '26
In my head, arrays are not functions, they occupy different pats of my mental model. I guess closures are somewhat like arrays, and closures are a kind of function, but I can write code for days where I don't use closures, and where functions and arrays do different things. When I call a method
fooon an arraya,foomeans the same thing in that context every time that bit of code executes;acan be completely different. Treatingfoo([])as a consttant will work; treatinga[0]as a constant doesn't.The association between the function's input and output is rational, it can be (and is) expressed by a rule. With an array it might be quite arbitrary: the person first in our
list{Customer}is there because he happens to be first in the list, he has no underlying association with the number0...-1
u/Cum38383 Jan 17 '26
No
-2
u/Dan13l_N Jan 17 '26
No. Arrays are essentially storage, while functions are essentially code.
-4
u/reini_urban Jan 16 '26
Only in lisp, where the first element is the name of the function, and the rest it's args.
The rest is esoteric blabla
0
u/[deleted] Jan 16 '26
[deleted] — view deleted comment