No, not in a programming language sense, because arrays are a notation for address offsetting, whereas functions change the execution context of the machine, which is critical to processing performance (think Horner's method).
Not even in a functional sense because, even though functions are input-output maps we define, the inputs are dimensionally rich, it's nowhere close to equivalent to jerry rig a contiguous input space for that purpose.
I remember I got a little confused when I was first learning TLA+, because what you normally call "functions" are "operators" [1], and what you'd normally call "maps" or "lists" are called "functions".
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>>
or like this:
Fact[n \in Nat] ==
IF n = 0 THEN 1
ELSE n * Fact[n - 1]
in both cases, if you wanted to get the factorial of 5, you'd call Fact[5], and that's on purpose because ultimately from TLA+'s perspective they are equivalent.
[1] At least sort of; they superficially look like functions but they're closer to hygienic macros.
I remember having a similar sort of realization early in my career when trying to implement some horribly convoluted business logic in SQL (I no longer remember the actual details of what I was trying to do, just the epiphany which resulted; I think it had something to do with proration of insurance premiums and commissions): I realized that if I simply pre-computed the value of the function in question and shoved it into a table (requiring "only" a couple million rows or so), then I could use a join in place of function application, and be done with it. An obvious idea in retrospect, but the sudden dredging of the set-theoretic formulation of functions--that they are simply collections of tuples--from deep within my memory was certainly startling at the time.
> 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".
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.
Reminds me of many years ago when people were fascinated by the discussion about whether closures are objects or objects are closures. Yes... Yes they are.
Very similar, referential transparency is the ability to replace a function call (or expression, generally) with its result (or value). So using an array (or other tabling mechanism) you can take advantage of this to trade off space for time.
The definition of a function is that for any given input A, I give you an output B. In fact anything that encodes a kind of transformation and yield new information based an input could be seen as a function. From that point of view, array is a function that when "touched", it gives you the information about its items.
In fact, from wikipedia:
```
In mathematics, a tuple is a finite sequence or ordered list of numbers or, more generally, mathematical objects, which are called the elements of the tuple. An n-tuple is a tuple of n elements, where n is a non-negative integer. There is only one 0-tuple, called the empty tuple. A 1-tuple and a 2-tuple are commonly called a singleton and an ordered pair, respectively. The term "infinite tuple" is occasionally used for "infinite sequences".
Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2, 7, 4, 1, 7) denotes a 5-tuple. Other types of brackets are sometimes used, although they may have a different meaning.[a]
An n-tuple can be formally defined as the image of a function that has the set of the n first natural numbers as its domain. Tuples may be also defined from ordered pairs by a recurrence starting from an ordered pair; indeed, an n-tuple can be identified with the ordered pair of its (n − 1) first elements and its nth element
When it says "arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers", is it saying that this:
const list = ['a', 'b', 'c']
is syntactic sugar for expressing something like this:
function list(index) {
switch (index) {
case 0: return 'a'
case 1: return 'b'
case 2: return 'c'
}
}
No. Quick version: They have the same type. Both take an integer and return a string, so their type would be Integer -> String in your example.
They are computationally equivalent in the sense that they produce the same result given the same input, but they do not perform the exact same computation under the hood (the array is not syntactic sugar for the function).
For the distinction there, consider the two conventional forms of Fibonacci. Naive recursive (computationally expensive) and linear (computationally cheap). They perform the same computation (given sufficient memory and time), but they do not perform it in the same way. The array doesn't "desugar" into the function you wrote, but they are equivalent in that (setting aside call syntax versus indexing syntax) you could substitute the array for the function, and vice versa, and get the same result in the end.
Can you? Yes, and TFA demonstrates this quite clearly.
Should you?
This is where I'd be more careful. Maybe it makes sense to some of the langs in TFA. But it reminds me of [named]tuples in Python, which are iterable, but when used as tuples, in particular, as heterogeneous arrays¹ to support returning multiple values or a quick and dirty product type (/struct), the ability to iterate is just a problem. Doing so is almost always a bug, because iteration through a such tuple is nigh always nonsensical.
So, can an array also be f(index) -> T? Sure. But does that make sense in enough context, or does it promote more bugs and less clear code is what I'd be thinking hard about before I implemented such a thing.
¹sometimes tuples are used as an immutable homogeneous array, and that case is different; iteration is clearly sane, then
In Clojure, vectors literally are functions. You can supply a vector (~= array) or map any place that a single parameter function is expected. So for example:
(map v [4 5 7])
Would return you a list of the items at index 4, 5, and 7 in the vector v.
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.
In Haskell specifically, arrays really do allow for the more general definition. This makes the library documentation[1] quite a bit more intimidating to newcomers (speaking from personal experience), but saves you the boilerplate and hassle of figuring out the mapping yourself if you're indexing your array by some weird nonsense like `[(False, 'a', 5000, 0)..(True, 'z', 9001, 4)] :: (Bool, Char, Integer, Int8)`.
That is typical in most languages, but Haskell's Data.Array is actually parametric over both the index type and the element type, with the index type required to provide a mapping to contiguous integers. This makes it similar to eg. a hashmap which is parametric over both key and element types, with the key type required to provide hashing.
IIRC, K rationalizes arrays and dictionaries with functions, e.g. you see arr[x;y] and fun[x;y]. Interestingly, this also highlights the connection between currying and projection, i.e. we can project/curry the above like arr[x] and fun[x].
Any expression-value can be a function, if you simply define the meaning of applying the the expression-value to another expression-value to be something compatible with your definition of a function.
For the downvoters, I think giving examples of what's NOT a function would start an interesting conversation, especially if you don't know how it could possibly be interesting!
I think it depends on what you mean by "is a function". You can think of a constant, `x` as `x_: () -> {x}` (i.e. everything can be indirected). It could be argued that this is "philosophically" "useful" since getting (using) the value of `x`, even as an actual constant, requires at the least loading it as an immediate into the ALU (or whatever execution unit).
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`)
For me, a x86 interrupt service routine that services a hardware interrupt[1] doesn't strike me as something I'd consider a function. It shouldn't return a value, and it typically has side effects. So why is it 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.
not a downvoter (actually, an upvoter), so grain of salt, but in my experience people cannot stand this framing. my best guess is that they dislike how impractical it is. obviously it's too abstract to be useful for most practical application. but that doesn't make it any less true.
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 didn't downvote but I'd be interested to know what the domain is here -- I'm not going to play dumb and be like, 'rocks are not functions', but I'm not sure exactly what class of thing you're asking for examples of.
The analog of a dot product of vectors is an integral over the product of functions.
The matrix multiplication of vectors - or a row and a column vector - which is then just taking the dot product is called an inner product. So for functions the inner product is an integral over where the functions are defined -
< f, g> = \int f(x) g(x) dx
Likewise you can multiply functions by a "kernel" which is a bit like multiplying a vector by a matrix
No, the best thing you can do for simplicity is to not conflate concepts. The perpetual idea of mixing data and execution is a misguided search for a silver bullet and it never makes things better in the long term.
This is cleverness over craftsmanship. Keeping data and execution as separate as possible is what leads to simplicity and modularity.
The exception is data structures which need the data and the functions that deal with it to expose that data conveniently to be closely tied to each other.
Everything else is an unnecessary dependency that obscures what is actually happening and makes two things that could be separated depend on each other.
> No, the best thing you can do for simplicity is to not conflate concepts.
This presumes the framework in which one is working. The type of map is and always will be the same as the type of function. This is a simple fact of type theory, so it is worthwhile to ponder the value of providing a language mechanism to coerce one into another.
> This is cleverness over craftsmanship. Keeping data and execution as separate as possible is what leads to simplicity and modularity.
No, this is research and experimentation. Why are you so negative about someone’s thoughtful blog post about the implications of formal type theory?
It makes obvious sense to consider an array as a function with the index as its input argument and the element its output, i.e. f(x) = A[x]... but this isn't the first time I've encountered this and I still don't see the practical benefit of considering things from this perspective.
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?
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 think this is an after-the-fact connection, rather than an intuitive discovery. I wouldn't explain memoization this way. Memoization doesn't need to specifically use an array, and depending on the argument types, indexing into the array could be very unusual.
>Well for example this insight explains Memoization
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.
There are some appealing-sounding arguments for designing languages around functions. Having given this a very fair shot with things like Erlang... turns out this optimizes for rare use cases at the expense of common ones. There's no 100% general-purpose language, they all have use cases in mind, and I guess some people are still trying to find a way around that.
Similar conclusion for using a graph DB for something you'd typically do in a relational DB. Just because you can doesn't mean you should.
In Object Oriented programming, yes, arrays are objects and the functions are a property of another object that can perform instructions on the data of the Array Object.
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.
> Similarly in Lisp, (a list-oriented language) both functions and arrays are lists.
In which Lisp? Try this in Common Lisp and it won't work too well:
(let ((array (make-array 20)))
(car array))
What is the car of an array? An array in Lisp (since Lisp 1.5 at least, I haven't read earlier documentation) is an array, and not a list. It does not behave as a list in that you cannot construct it with cons, and you cannot deconstruct it with car or cdr.
To quote John McCarthy
"Since data are list structures and programs are list structures, we can manipulate programs just like data."
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.
Yeah I guess a c++ programmer might say `std::array::operator[]` is a function (or method, whatever), just like `std::array::size` is. And that identifying the array with just one of those functions (or even the collection of all methods offered) is to miss the point -- not just contiguous indices, but contiguous storage. A red-black tree with added constraints is not an array.
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.
No - An array is a data structure that stores pre-calculated values in memory, whereas a function is executable logic that computes a result only when it is called.
There are two opposing philosophical viewpoints here. Some view mathematics as a model for understanding the real world. Some see the real world as instantiation of mathematics.
Is an array a function? From one perspective, the array satisfies the abstract requirements we use to define the word "function." From the other perspective, arrays (contiguous memory) exist and are real things, and functions (programs) exist and are something else.
> 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.
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.
Not even in a functional sense because, even though functions are input-output maps we define, the inputs are dimensionally rich, it's nowhere close to equivalent to jerry rig a contiguous input space for that purpose.
reply