New language feature: array-types
ramin.honary at gmail.com
Sun Aug 17 10:45:21 EDT 2008
I am new to both the Haskell language, and to this group, but I have
recently become obsessed with the mathematical precision of Haskell, and
I want to help improve it, if members of the group could bear with me.
The one thing I dislike about the Haskell language is it's treatment of
arrays. I don't understand how things work internally to the system, and
perhaps array-manipulating code can be efficiently optimized, but I
would prefer to have a language feature for explicitly creating and
modifying arrays in a way that does not require the entire array be
copied on every update.
My idea is this: a fixed-width mutable array can be declared as a type,
much like a list, but can be evaluated more like a bitwise-integer
-- in an array of A's set the 5th item in the array with an
changeArrayFunc :: a^10 -> a^10
changeArrayFunc ar = (ar:5 <- initA) -- returns an array which is
that same as the old array, except the value at index 5 is different.
-- select the 5th item of an array
getArrayItemFunc :: a^10 -> a
getArrayItemFunc ar = (ar:5)
Here, I use the caret (^) operator to indicate an "array-10" type. I
used caret because it is typically used for exponents -- as in, if your
data type has N possible values, an array with 10 units would have N^10
possible values. Then, I use the colon (:) operator to do indexing. I've
seen the various proposals for indexing operators and honestly I don't
care which operator is chosen; I just use the colon operator because
that is how lists are treated in pattern matching.
The important thing is that an array-type exists, that way all
bounds-checking can be done at compile-time by the typing system. Using
arrays of different lengths would result in a compile-time error:
Obviously, this will increase the complexity of the typing system.
data Something = Array Int^10
change5Array :: Int^5 -> Int^5
change5Array ar = ((ar:4) <- 0)
-- Something has an array of type Int^10, but calls "change5Array"
which expects an Int^5
badFunc :: Something -> Int
badFunc (Array x) = (change5Array x)
-- COMPILE-TIME ERROR
-- Couldn't match expected type `Int^5' against inferred type `Int^10'
-- In the first argument of `change5array', namely `x'
-- In the expression: (change5array x)
-- In the definition of `badFunc':
-- badFunc (Array x) = (change5Array x)
...or something like that.
An efficient implementation of array access would make Haskell very
useful for a much wider variety of computationally intensive
applications. Haskel could be used to efficiently model memory access,
provided that the interpreter knew not to "copy" arrays upon update, but
simply to update a value within an array. If arrays were a language
feature of Haskell, then this optimization could be guaranteed.
If anyone takes the time to consider this idea, or to tell my why this
isn't necessary, I would be most greatful.
-- Ramin Honary
More information about the Haskell-prime