New language feature: array-types

[Lennart Augustsson]

You can code array types with static bounds with the existing Haskell
type system.

On Sun, Aug 17, 2008 at 3:45 PM, Ramin <ramin.honary at gmail.com> wrote:
> 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 operation.
>
>  -- 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)
>
> -- COMPILE-TIME ERROR
> -- 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
>
> _______________________________________________
> Haskell-prime mailing list
> Haskell-prime at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-prime
>