GitLab

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 even Applicative) instance
• an indexing function
• (Binary+Outputable instance)

That should do.

Ideas where to use SmallVec (feel free to add more):

• Product Demands
• Syntax elements, such as MatchGroups
• (basically everything which is a syntax-dependent list and thus constant in length by construction)