New language feature: array-types

Ramin ramin.honary at
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 
"initial-A" value
   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)

-- Arrays.hs:8:16:
--     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 mailing list