Haskell performance: Manual unboxed list?

Question

According to Haskell documentation, you can't pass a primitive value to a polymorphic function or store one in a polymorphic data type. This rules out things like [Int#].

Does it make sense to create a custom list implementation, say, IntList, that is simply the list type specialized to Ints? Does one exist already?

Answer 1

Yes, it does make sense, as there are interesting hybrid lazy/strict data structures that have better complexity than strict, flat, unboxed arrays, but are more efficient than lazy, boxed structures.

I describe such data types, and ways to build them without resorting to manual unboxing in:

http://donsbot.wordpress.com/2009/10/11/self-optimizing-data-structures-using-types-to-make-lists-faster/

Naively, you can turn a lazy linked list (or similar lazy structure using a univeral representation for polymorphic elements):

Into an "equivalent" structure that specializes the node on the representation of the element type, removing several indirections per node:

In particular, spine-lazy, node-strict/unboxed data types that are polymorphic, but specialize the container for each element type are denser and have significantly faster constant factors than generic boxed (polymorphic) data types.

This comes at a cost of compile-time complexity, and instance generation, but it is a fruitful area of research i think. These are analogous to template-specialized data types.

The adaptive-containers package is an implementation of these ideas for type-indexed specialization of polymorphic data types.

The biggest benefits will be for trees / dictionaries / sets and other purely functional container types.