Lambda the Ultimate

iSUB is trying to fix a language design fault. It's nothing more than a weird function definition. If the language was designed properly, arrays and functions could have been used interchangebly. They have the same "signature": a tuple as input and one value as output.

Now that I think about it, I can't recall a language that allows this. Is there a language where you can write a factorial function and slice it like a list: fac[1:20]

Table[Factorial[n],{n,1,20}]

Factorial[Table[n,{n,1,20}]]

Functional languages can do these things.

Do higher order functions that expect functions as argument, also allow arrays, and vice versa?

See this PDF, Maeder's books and articles, and Wolfram.

There is sample code all over the Internet and you can install the free MathReader on any platform to inspect it.

Most functions have the attribute Listable (look it up). The documentation includes a section on FP, and a rundown on programming paradigms.

For more help please appeal to Google.

It's all very cool! But listable means that functions automatically map over lists. That's not what I mean.

Let's take a particular example from those pages. NestList is a higher order function. The first argument is a function. Can I use a list instead?

NestList[{1,3,4,2,3}, 0, 6] -> {0, 1, 3, 2, 4, 3, 2, 4}

The use cases proposed are not higher order. Factorial is not a higher-order function in the first place. Feeding numerical parameters (or arrays of same) into a function is not a higher-order operation; it is a straight function call. Higher order means that a function appears somewhere in the parameter list. I see no function parameter in the calls that you propose. Rethink what you are asking and why. Do you really care about HOFs, or is it something else that you want? If you feed an array into NestList, how is NestList supposed to know what function you want applied to the list, unless you supply it as a parameter?

I'm signing off now, but you can ask the various user groups or Google for more help.

If you feed an array into NestList, how is NestList supposed to know what function you want applied to the list, unless you supply it as a parameter?

No, no, no! I want the the list to *be* the function.

A function is a mapping from values from its domain to values from its range. Similarly, a list is a mapping from indexes to values. A list can therefore be considered a function. Similarly, multidimensional arrays are mappings from a tuple of indexes to values, just like functions with multiple arguments. I want to know if there are programming languages that acknowledge this, in any way.

Ruby sort of does, in that it lets you overload the [] operator, and that a[i] = a.at(i) for an array and a.call(i) for a proc. I've seen code written that let you pass in whatever parameter you wanted, as long as it supported the [] operation, so it definitely does support the idiom. However, it doesn't have built-in multidimensional arrays, and methods are treated differently from proc objects.

Hmm, to use a list as a function you need an
infinite list, i.e. a stream. Indeed Streams over A are
"isomorphic" to Nat -> A. What is isomorphic to
functions over binariy trees? I wrote a paper about
this a few years ago.

You're in a bog of terminology confusion that seems more complicated than the actual task, which still eludes me. The whole presentation abuses standard terminology. HOF means HOF; you mean something else, but want to cram it into HOF with elliptical reasoning. That penny tutorial about function domains was nice, but bears no relation to HOF in computer science. I would drop the term HOF.

You picked NestList. NestList returns a list of iterated function applications to a seed expression. We know what f[x] means - f is a function. Replace f with the list {1,2,3}. How shall an array be applied to an expression? What is {1,2,3} of argument [4]? Is it {4,8,12} or {5,6,7} or something else? What is {4,5,6} of argument ["A"]? Not only do you abuse the meaning of HOF, you abuse the meaning of function.

Mathematica allows nonsense inputs; it grants formal manipulations. So Mathematica accepts NestList[{1,2,3},x,6] and produces the expected (nonsense) output: {x, {1,2,3}[x], {1,2,3}[{1,2,3}[x]], ... }.

There is a mathematical sense in which an array represents mathematical function samples, or let us say, delta functions at index coordinates. For these purposes Mathematica offers treatments like interpolating functions, curve fits, and DiracDelta. I don't think those are what you want, but they are the only things that make rational sense of your (mathematical) definition of arrays-as-functions. Otherwise, asserting that "arrays are functions!" is neither a problem statement nor a behavioral specification. It's just meaningless noise.

Mathematica enables fantastic varieties of array manipulation and functional programming, and I have already pointed you in the right directions. It is highly dubious that you can find any problem which cannot be coded elegantly and optimally in Mathematica. Guessing, some hints: Apply replaces the head List with whatever you like, turning arrays into anything. Arrays of functions are possible. Anonymous functions are possible. If you want to consider index values as implicit data, MapIndexed passes them as auxiliary parameters to the mapped function. You can also make index values explicit by various array constructions, e.g. defining each array element as an {index, value} couplet. Probably you should look at MapIndexed, Apply, Thread, level specifications, or maybe Outer and Inner for all I know. Read the friendly help files, Wolfram's are good.

Or, try doing the magic in Lisp, which is more familiar to LtU readers.

There is a mathematical sense in which an array represents mathematical function samples, or let us say, delta functions at index coordinates.

No, arrays are functions, not function samples or whatever. The array (or list) [1, 2, 3] is a function from the domain {0, 1, 2} into the set {1, 2, 3}. [1, 2, 3] of [4] is a "type error" because 4 is not on the domain; it's the same as log(-4). The same goes for [4, 5, 6] of ["A"].

You seem to find the idea outrageous, but it's just standard mathematics.

I was beginning to think I had got it completely wrong. This is exactly what I was thinking.

Andrei Formiga: The array (or list) [1, 2, 3] is a function from the domain {0, 1, 2} into the set {1, 2, 3}. Sjoerd Visscher: This is exactly what I was thinking.

The conventional term is array subscript. The need for math, HOFs, or how this latest statement counters my demonstration of NestList gibberish, I fail to see. Sjoerd picked NestList as a test case, and I showed the actual nonsense result. Are you saying that because I missed something about arrays as functions, the NestList result is sensible? I don't see it.

Math is not our disagreement. Modulo formalisms, we said the same thing, that CS arrays can have mathematical interpretations. The choice of formalism (set isomorphisms, delta functions, function samples) is irrelevant. Computer science is our disagreement. Sjoerd seeks vague HOF magic by (a) giving arrays a mathematical function interpretation and (b) eliding the distinction between math and CS to (c) feed arrays-as-functions into HOFs. It doesn't work, guys, and it doesn't even make sense. I did not pick NestList as the test case; Sjoerd did, and I showed the resulting nonsense. Mathematics doesn't define a "type error" (that's a CS concept), and incidentally, log(-4) equals ((i * pi) + log(4)) in mathematics.

An array in CS is a piece of data, like a string or file. A CS array can represent many things (stacks, queues, file sizes, years of employment on successive jobs, etc.). Math functions are one more category of things they can represent; pick your favorite formalism. I do not quibble that mathematical interpretations exist. I quibble over sleight-of-hand re-interpretations as CS functions, and subsequent usefulness in accomplishing Sjoerd's mysterious task (which begs for concrete examples; I can't make heads or tails of his NestList case; it seems bogus to me, and doesn't reflect actual Mathematica output, which I demonstrated.)

Look at a simpler case. I can define a CS function that returns 5 for all inputs. This thing is a CS function, although boring. I can pass this CS function to a HOF. What have I gained? I may as well just use 5 as a straight argument to a plain function, and stop deluding myself that I need or want a HOF.

The situation with arrays is the same. Follow your interpretation faithfully. Take a 3-element array {10,11,12}. We baptise it as a function per your spec. This "function" maps the (array subscript) domain {0,1,2} to the (pseudo-function) range {10,11,12}. We pass this "function" to a HOF per Sjoerd (he wants the HOF, remember). We do that by passing the range {10,11,12} to the HOF. Surprise, we just passed an array to a function.

Call a spade a spade. We passed an array to a function. The recipient may interpret it as a stack, queue, math function, or years of employment, but no such interpretation makes the recipient a HOF in the CS sense, or requires that it be one. What do these weird HOF incantations buy us? What are we really trying to do?

Whatever Sjoerd wants to do, it probably falls into the category of standard array manipulations, functional programming, list comprehensions, or something similar, for which stock tools exist in Mathematica and other packages. So far Sjoerd has not clarified his task or how a mathematical-function interpretation helps it. If we are talking about array subscripts, why can't we just use standard terminology?

Take NestList[{1,3,4,2,3}, 0, 6]

You say then that this produces:

{0, {1,3,4,2,3}[0], {1,3,4,2,3}[{1,3,4,2,3}[0]], ...}

My point is that {1,3,4,2,3}[0] is (almost obviously) reducible to 1. And {1,3,4,2,3}[1] to 3, etc.

That's why I think the result should be {0, 1, 3, 2, 4, 3, 2}

I don't see the point in keeping {1,3,4,2,3}[0] unreduced, and I don't see another valid meaning of the expression.

This answer is what I mean about terminology circles. It begs your question about 'function calling' an array. If the only possible interpretation is array subscript, then just use array subscripts directly (with syntax sugar that suits your fancy). Don't complain that we have a language design problem. See my longer remarks below.

Function[x, Function[y, x[[y]]]]

You could also wrap any array x like this:

(x[[#1]])&

and turn the array into a function.

The only detail to correct your example is that Mathematica starts the index at 1, while 0 indexing an object returns the type (it's actually interesting indexing non-arrays).

NestList[({1, 3, 4, 2, 3}[[#1 + 1]]) &, 0, 6] -> {0, 1, 3, 2, 4, 3, 2}

NestList[({1, 3, 4, 2, 3}[[#1 + 1]]) &, 0, 7] -> {0, 1, 3, 2, 4, 3, 2, 4}

I don't know what Mark's problem is, you must have hit a nerve.

So arrays don't support the [] operator, and functions don't support the [[]] operator. Just like all other languages I know. (Although usually they are () and [])

There seems to be no language that unites these operators. So I guess there must be a good reason to do that, but I don't see it. Anyone?

In Octave/Matlab, parens serve both these functions. I tend to keep track in my head of which identifiers are functions and which are arrays, suggesting that the indexing distinction makes some sense. Arrays have a dimension/domain that you can query, unlike a typical function, and can only be indexed/called with integers. These additional semantics to me at least make it inconvenient to treat the two as the same sort of thing.

I believe that in Scala the "template class" Array[a] is a subtype of Function[Int,a]. In particular, indexing is done via the apply method of class Function[Int,a].

BTW, concerning HOFs and n-dimensional arrays. Define [n] as {0,1,2,... n-1}. A linear array over (i.e., drawing elements from) A of length n is isomorphic to a function [n]->A. A 2-dimensional m-by-n array is representable as a function [m] * [n] -> A. If you curry this, you get [m] -> ([n] -> A), which is isomorphic to the type of linear arrays over [n] -> A of length m, which is isomorphic to the type of linear arrays over [m] -> A of length n.

In answer to Mark's complaint, "What is the point?": the point is that, if we could write functions generic over isomorphism classes of types, then we could reuse functions defined to operate on A-arrays as functions defined to operate on functions of the form [n]->A, and vice versa, and so obtain a more economical and less redundant programming language.

Suboptimal, because we can't exchange ($) for (.$.) in all of the available libraries, but:

module GenFun where

import Data.Maybe
import Data.Array

class Mapping a b c | a -> b, a -> c where
    (.$.) :: a -> b -> c

instance Mapping (a -> b) a b where
    (.$.) = ($)

instance Eq a => Mapping [(a, b)] a b where
    l .$. el = fromJust $ lookup el l

instance Ix a => Mapping (Array a b) a b where
    (.$.) = (!)

It would be cool if ($) was actually defined like (.$.). There are the obvious interactions with laziness, though. Either way, that's a more general function application. (Mental note: think about this for my fantasy language :)

Sorry for bumping this old thread, but I just came across this section in the pop-11 primer and remembered this discussion:

Arrays are procedures in Pop-11.

Not sure if this is exactly what you were after.

Even in languages that don't have true multidimensioanl arrays it is possible to have an elegant and fully general syntax for slices, e.g., m[1;;] (same as m[1]), m[;1;] and m[;;1] in K, where m is a 3d structure (actually a list of lists of lists).

See Mathematica's documentation for Part and detailed examples to see how All works as a subscript.

(Some of my thoughts on arrays :)

One way to look at (1-dimesional) arrays is like a sequential collection. Sometimes the order matters, sometimes not. The indices doesn't mean much on their own, so one just start indexing at e.g. 0 (or 1 if one likes that better).
Examples : array of subwidgets, array in a queue implementation, array of some kind of collected data (like e.g. user info or experiment result or database record). (Sometimes the indices have specific meaning even though the start index is fixed, of course.)
Language examples : C,Java,Basic,ML,Clean.

Another way is to look at (1-dimesional) arrays is like a partial function from integers to whatever the element type is. A more refined way would then be a total function from a subtype (usually contiguous, from what I know) of integers to the element type. (The implementation of this would then, as we all know, use a memory block as a table instead of how functions are usually implemented.) In this view the indices have a meaning on their own. Here one sometimes also use symbolic constants (e.g. in an "enumeration type") as indices instead of integers in some range. In this case sometimes no special ordering of the constants is intended.
Examples : array indexed by timezone,array holding heap elements (starting from 1,left is 2*i,right is 2*i+1),array indexed by month,array indexed by "paper,scissor and stone",array indexed by lexer/parser token
Language examples : Pascal,Ada,Haskell(*).

For multidimensional arrays, one can have nested (~= curried) arrays, where one index out one array and then from that index out again. In this way, there is a total order imposed on the "axes" of the array, and it gets hard to have slices(**) "across" the axis order, e.g. horizontal slices of a 2-dimensional might work, but not vertical slices. (But one might not need any special support from the language to get this limited form of multi-dimensional array slicing here.)
(Another issue here is whether or not the nested arrays on the same level must have the same shape. E.g. of "must" is C (the arrays described by the array types, not the array of pointers variety), E.g. of "don't have to" is Java)
Language examples : C,Java,Pascal(***),Ada.

Or one can have multidimensional arrays where one index out an element with all indices at once. This though probably requires language support for slicing. (One could of course still have nested multidimensional arrays, as well, in the same language.)
Language examples : Ada,Haskell.

One can view this latter kind of multidimensional arrays as arrays that are indexed by a tuple (vector) of individual indices. (One can easily imagine extending the allowable kinds of index types some more ..)

So, there's probably a use for both collection-arrays and mapping-arrays, IMO.

(*) The type of arrays in Haskell still doesn't tell what range the array indices have.

(**) By slice, I mean either that it should be shared with the array it was taken from, or it should be possible to manipulate (e.g. update) the slice in place, or both. (I.e. just a copy of part of the array would not count in the sense used in this post.)

(***) IIRC, Pascal has syntax that looks like non-nested multi-dimensional arrays, but the type is the same as a corresponding nested one, and one can't slice across the axes.

(Hm, got a bit long)

--
Stefan Ljungstrand

I don't see a good use case. When does both a 12 element array and a 2D 3*4 array with the same data make any sense? Ok, it wouldn't hurt to have as an obscure library function, but why did you want to mention this here specifically? (just curious)

When does both a 12 element array and a 2D 3*4 array with the same data make any sense?

Imagine you have a two-dimensional array of quarterly sales figures. To get the sales for a quarter you index by year (0,1,2...) and then quarter. To get lifetime sales to date, you reshape the array to a single dimension and sum it.

For me the novelty is in minimalistic language design, not utility per se. Take a look at this example:

fib[0] = 1
fib[1] = 1
fib[n] = fib[n-1] + fib[n-2]

You can call this a function definition, or an array definition with some kind of defaulting mechanism.

Comming from Mathematica there may be no good reason to combine functions and arrays. But from a language design perspective I see no good reason to separate them.

Ugh, you had to pick another recursive function. Please I beg you, pick another that isn't.

Let's call things what everyone else calls them, shall we? If fib is an array, what are the array dimensions of fib? It's not an array, it's a function.

I showed that Mathmatica does "combine" them, as you like to phrase it - incorrectly I think, but still. Other languages can do the same tricks. However yours seems not a language design issue, but a syntax sugar issue. On that basis I don't think there is any novelty at all.

The semantics of your proposal are that arrays can be functions - but only under an interpretation of array subscript. That's just syntax sugar for array subscripts. Then we have functions that can be arrays - with semantics identical to mappings across arrays. More syntax sugar.

Still, maybe my code snippets will be helpful in some way. Good luck!