I think there are several places in the compiler where lists are the wrong data structure and we are better off using an array, e.g. when storing something for multiple uses, never changing it afterwards.
GHC.Exts and we should use it. The problem is that the only half-way comfortable API I know of is in
primitive, which isn't a boot package. And even that wrapper is far from a feature-complete API to be usable as a drop-in replacement for lists; I think it's merely a compatibility wrapper offering the same API for GHC < 7.10, where it's backed by an
Array# (plus it uses
So I propose to add our own module
GHC.Data.SmallVec that offers a few key pure functions for a persistent API around
SmallArray#. I hope for the following instances:
- A fusing
- an indexing function
That should do.
Ideas where to use
SmallVec (feel free to add more):
- Syntax elements, such as
- (basically everything which is a syntax-dependent list and thus constant in length by construction)