It was odd to me, because it hadn't really occurred to me before that, given infinite memory (and within a mathematical framework), there's fundamentally not necessarily a difference between a "list" and a "function". With pure functions, you could in "theoretical-land", replace any "function" with an array, where the "argument" is replaced with an index.
And it makes sense to me now; TLA+ functions can be defined like maps or lists, but they can also be defined in terms of operations to create the values in the function. For example, you could define the first N factorials like
Fact == <<1, 2, 6, 24, 120>>
Fact[n \in Nat] ==
IF n = 0 THEN 1
ELSE n * Fact[n - 1]
[1] At least sort of; they superficially look like functions but they're closer to hygienic macros.
You don't even need infinite memory. If your function is over a limited domain like bool or u8 or an enum, very limited memory is enough.
However the big difference (in most languages) is that functions can take arbitrarily long. Array access either succeeds or fails quickly.
And all three are tuple [input, output] pattern matches, with the special case that in “call/select tuples”, input is always fully defined, with output simply being the consequence of its match.
And with arrays, structures and overloaded functions being unions of tuples to match to. And structure inputs (I.e. fields) being literal inline enumeration values.
And so are generics.
In fact, in functional programming, everything is a pattern match if you consider even enumeration values as a set of comparison functions that return the highly used enumerations true or false, given sibling values.
(map v [4 5 7])
> Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers.
with
> Haskell provides indexable arrays, which are functions on the domain [0, ..., k-1]?
Or is the domain actually anything "isomorphic to contiguous subsets of the integers"?
When I'm writing code and need to reach for an array-like data structure, the conceptual correspondence to a function is not even remotely on my radar. I'm considering algorithmic complexity of reads vs writes, managed vs unmanaged collections, allocation, etc.
I guess this is one of those things that's of primary interest to language designers?
https://en.wikipedia.org/wiki/Memoization
If you know that Arrays are Functions or equivalently Functions are Arrays, in some sense, then Memoization is obvious. "Oh, yeah, of course" we should just store the answers not recompute them.
This goes both ways, as modern CPUs get faster at arithmetic and yet storage speed doesn't keep up, sometimes rather than use a pre-computed table and eat precious clock cycles waiting for the memory fetch we should just recompute the answer each time we need it.
I don't think it does.
In fact I don't see (edit: the logcial progression from one idea to the other) at all. Memorization is the natural conclusion of the thought process that begins with the disk/CPU trade off and the idea that "some things are expensive to compute but cheap to store", aka caching.
Whether storing (arrays) or computing (functions) is faster is a quirk of your hardware and use case.
TFA does allude to this. An "array indexing function" that just met the API could be implemented as an if-else chain, and would not be satisfactory.
Similarly in Lisp, (a list-oriented language) both functions and arrays are lists.
This article however is discussing Haskel, a Functional Language, which means they are both functions.
In which Lisp? Try this in Common Lisp and it won't work too well:
(let ((array (make-array 20)))
(car array))
Yes, I know most people consider it to be a functional language, and some variants like 'common lisp' make that more explicit, but the original concept was markedly different.
Even non-functional relations can be turned into functions (domain has to change). Like a circle, which is not a function of the x-axis, can be parameterized by an angle theta (... `0 <= theta < 2pi`)
The answer is pretty much, yes, everything can be a function. e.g. A KV Map can be a function "K -> Maybe V"
P.S. If this style of thinking appeals to you, go read Algebra Driven Design! https://leanpub.com/algebra-driven-design
it's a bit like saying "everything is a process", or "everything is a part of the same singular process that has been playing out since observable history". there's some interesting uses you can get out of that framing, but it's not generally applicable in the way that something like "all programs are unable to tell when a process will halt" is.
but if you really want to harvest the downvotes, I haven't found a better lure than "everything, including the foundations of mathematics, is just a story we are telling each other/ourselves." I know it's true and I still hate it, myself. really feels like it's not true. but, obviously, that's just the english major's version of "everything is a function".
I mean trivially you could say it's a function from (entire machine state) to (entire machine state), but typically we ignore the trivial solution because it's not interesting.
> I found this to be a hilariously obtuse and unnecessarily formalist description of a common data structure.
Well it is haskell. Try to understand what a monad is. Haskell loves complexity. That also taps right into the documentation.
> I look at this description and think that it is actually a wonderful definition of the essence of arrays!
I much prefer simplicity. Including in documentation.
I do not think that description is useful.
To me, Arrays are about storing data. But functions can also do that, so I also would not say the description is completely incorrect either.
> who can say that it is not actually a far better piece of documentation than some more prosaic description might have been?
I can say that. The documentation does not seem to be good, in my opinion. Once you reach this conclusion, it is easy to say too. But this is speculative because ... what is a "more prosaic description"? There can be many ways to make a worse documentation too. But, also, better documentation.
> 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.
I agree that there is a correspondence. I disagree that Haskell's documentation is good here.
> currying/uncurrying is equivalent to unflattening/flattening an array
So, there are some similarities between arrays and functions. I do not think this means that both are equivalent to one another.
> would like to see what it would be like for a language to fully exploit the array-function correspondence.
Does Haskell succeed in explaining what a Monad is? If not, then it failed there. What if it also fails in other areas with regards to documentation?
I think you need to compare Haskell to other languages, C or Python. I don't know if C does a better job with regards to its documentation; or C++. But I think Python does a better job than the other languages. So that is a comparison that should work.