Arrays and general functions
Ken Sailor writes: >On the other hand, general functions and arrays are typically mixed in >a program. If the distinction between the two is limited to type >declarations, then from my perspective it becomes difficult to read >and understand programs. The difference between functions as rules >and arrays to me is much more significant than the difference between >adding reals and adding integers. From your perspective, maybe any >distinction gets in the way. In practice, I have not had this >problem. The distinction indeed gets in the way; however, this may well be a product of the application area in which I am working (I *did* admit my bias in all this). If we define the behavior of an engineering component in a microwave system by a function, the distinction between whether that function is defined by an array (table of values) or a rule (a function definition in the present Haskell sense) had better be hidden! We want very much to treat these independent of the mechanism of defining them. I am interested in how the lack of a distinction gets in the way of your reading and understanding programs, however. After all, I do want to make sure we are not introducing problems here! Granting that this is a somewhat theoretical discussion, could you elaborate a bit here? What kind of expression would become difficult to understand if the distinction between arrays and rule-defined functions was hidden? I don't want to impose on your time unreasonably, but a couple of small examples might be helpful. Dave Barton [EMAIL PROTECTED]
Arrays and general functions
Reginald Meeson writes: >Interesting discussion, but it seems to me that Haskell already >provides the best of both worlds, namely > > a. Efficient implementation of arrays as data objects, with indexing > as a projection function; and > > b. Definition of functions with (Ix a) domains by indexing an array > behind the scenes or by any other rule. > >Arrays satisfy the needs of an important user community. Is there >something more needed to satisfy the general-function community? For the same reason that the features of parametric functions and type classes in general are useful: in some cases, you want to treat the object like an array (for instance, building and updating), and in some cases you want to treat the object like a function (accessing, currying, functional composition). At least part of my argument is a theoretical one: arrays are functions, and should look like them. A much larger part is practical: I am working in an environment where there are a lot of different function representations, of which Haskell-type functions, arrays, dual arrays (domain and range) with an interpolation function, and specific triples which assume an underlying sine function are only a few. These functions need to be specified in accordance with their representations; however, outside the original specification, they are used as functions (with an entire class structure, similar to the type strucuture in the standard prelude. of functions that are applicable on them). To specify both the object and a separate function that incorporates the object is at least extremely inconvenient. Dave Barton [EMAIL PROTECTED]
Re: Arrays and general functions
David Barton writes: > >And finally, it makes sense to have separate syntax for arrays and > >general functions, because different behavior is expected for the two. > > Here, I may be exposing my cluelessness, but this seems a (search for > a better word --- none found) silly statement. There are many cases > where we want different behavior to be expressed by the same syntax. Well, perhaps behavior is the wrong word. Also, I find your approach interesting. On the other hand, general functions and arrays are typically mixed in a program. If the distinction between the two is limited to type declarations, then from my perspective it becomes difficult to read and understand programs. The difference between functions as rules and arrays to me is much more significant than the difference between adding reals and adding integers. From your perspective, maybe any distinction gets in the way. In practice, I have not had this problem. Ken
Re: Arrays and general functions
Ken Sailor writes | Reginald Meeson writes | | > Interesting discussion, but it seems to me that Haskell already | > provides the best of both worlds, namely | | > a. Efficient implementation of arrays as data objects, with indexing | > as a projection function; and | | (Actually, efficient seems a little hopeful here). Agreed, although any reasonable implementation should at least be able to provide o(1) indexing. | Rats, my Haskell manual is home, so correct me if the following | is wrong... Actually, let me pose this as a question (then I | don't have to get so embarrassed later!) | | Let's say I have an array arr and at some index i I want to update | it to be x. That is, I want to define | | upd arr i x | | to return a new array equal to arr everywhere except i where the | value of the result is x. It seems to me that there is no | way to write this function without decomposing arr into a list | and rebuilding an array. Am I right? (I will be pleased to be wrong!) Wrong! :-) (or maybe half-right) Incremental update is provided, your example being written arr//[i:=x] . The Standard Prelude does define (//) in more or less the terms you describe above, but note the comment at the beginning of PreludeArray, which can be paraphrased, "Dont't even _think_ about actually implementing arrays this way." The expectation is that a compiler that is serious about array performance will do something more clever, such as static sharing analysis for update-in-place and/or dynamic techniques like version arrays. | >From the APL/Nial/Array Theory world, it is a travesty to be forced | to perform such a decomposition. There are enough optimization problems | without mixing lists into it. I, for one, would be very interested in seeing APL/Nial/Array-Theory ideas considered for incorporation in some future version of Haskell. (We haven't been talking about Haskell 2 much lately.) | This, of course, is not to say that it is not convenient or perhaps | necessary to be able to convert lists into arrays. It is very convenient | for monolithic array operations, such as building tables for lookup | functions, etc, but it also seems like there ought to be some kind | of support for incremental array operations, like update. | | Dave Barton writes: | | > I am interested in how the lack of a distinction gets in the way of | > your reading and understanding programs, however. | | (where the distinction is between arrays as rules and arrays | as general functions). This may be painfully obvious, as well as syntactic and superficial, but since nobdoy's mentioned it up to now: If you want to treat an array a as a function, just use (a!) , e.g., f . (a!) . g | My apologies for not being more sensitive to your application | before my first response. I have an interest in the | optimization of incremental array operations (see above) and | don't tend to think of arrays as fixed tables. | | The first area that pops into mind where I am more comfortable | with having the distinction is graph theory. Now perhaps | it has something to do with the way it was taught to me, but | I like thinking of the arrays as data objects rather than functions, | and it helps me in thinking about what an algorithm is doing and | how much the algorithm costs. This, indeed, is the attitude toward arrays taken by the Haskell committee. At the beginning of the Report section on arrays, we say that although in the abstract arrays should be regarded as functions, there are pragmatic reasons for treating them as data. | On the other hand, I am not sure how important this is or how | long it would take me to forget or drop my dependence on the | distinction. | | Ken The opinion prevailing at the time we decided to distinguish array indexing syntactically from function application was that it would be difficult in general for a compiler to generate efficient code for an array access without the distinction. --Joe
Re: Arrays and general functions
Interesting discussion, but it seems to me that Haskell already provides the best of both worlds, namely a. Efficient implementation of arrays as data objects, with indexing as a projection function; and b. Definition of functions with (Ix a) domains by indexing an array behind the scenes or by any other rule. Arrays satisfy the needs of an important user community. Is there something more needed to satisfy the general-function community?
