Opened 9 years ago

Last modified 2 years ago

#2200 new feature request

big static random access arrays

Reported by: jsnx Owned by:
Priority: normal Milestone:
Component: Core Libraries Version: 6.8.2
Keywords: static array Cc: SamB, core-libraries-committee@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


These would be unlike StorableArrays because they would be available at compile time, and would be pure values. They would amount to arrays of bytes, of course, but it'd be nice if they could be (Storable a) => StaticArray a and we could walk down them or randomly access them to get the a values out of them. They should be capable of storing hundreds of thousands of Ints.

What are some functions that work on these arrays? We need just one:

indexInto :: (Storable a) => StaticArray a -> Word -> a

Then we can make a Monad to walk up and down the array. It will be some State hybrid. No IO. A bright person could implement static Tries, RoseTrees and other things using this Monad -- storing the offsets mixed in with the data in an unholy mess and skipping forward or backward, leveraging "the world’s most beautiful imperative language."

It's been suggested (SamB) that this should be implemented in Template Haskell.

Important features of this array relative to other arrays and lists in Haskell:

Specificity of Index
A machine Word since that contains the finest grained pointer. When indexing into a Storable a, the index is multiplied by sizeOf (undefined :: a).
Static Nature
Exists to facilitate large static constants. The array does not support any append or delete operations, there is no way to change any of its values and it can not be copied.

Change History (6)

comment:1 Changed 9 years ago by dons

See this recent thread on compile time data structures,

In particular, the solutions using Data.Binary to encode data structures.

comment:2 Changed 9 years ago by igloo

difficulty: Unknown
Milestone: _|_

I don't think that this is very high on our list of priorities, but if someone else wanted to attempt it then we would certainly be able to give advice if you get stuck.

I'm not sure exactly what design you envisage, but it may not require changes to GHC at all; I would certainly expect that to be the case for something implemented with TH.

comment:3 Changed 9 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:4 Changed 9 years ago by simonmar

Operating System: MultipleUnknown/Multiple

comment:5 Changed 3 years ago by thomie

Cc: core-libraries-committee@… added
Component: CompilerCore Libraries
Owner: set to ekmett
Type of failure: None/Unknown

comment:6 Changed 2 years ago by thomie

Owner: ekmett deleted
Note: See TracTickets for help on using tickets.