Use `SmallArray#`
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.
We have SmallArray#
in 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 MonadPrim
instead).
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
IsList
instance -
Functor
+Foldable
+Traversable
(maybe evenApplicative
) instance - an indexing function
- (
Binary
+Outputable
instance)
That should do.
Ideas where to use SmallVec
(feel free to add more):
- Product
Demand
s - Syntax elements, such as
MatchGroup
s - (basically everything which is a syntax-dependent list and thus constant in length by construction)