Haskell Performance: List of Manual Unpackers?

Question

According to the Haskell documentation, you cannot pass a primitive value to a polymorphic function or store it in a polymorphic data type. This eliminates things like [Int #] .

Does it make sense to create an implementation of a custom list, say, IntList , and is it just a list type specialized for Int s? Does it already exist?

Answer 1

Yes, that makes sense, because there are interesting hybrid lazy / strict data structures that have better complexity than strict, flat, unpacked arrays, but are more efficient than lazy structures in a box.

I describe these types of data and how to create them without resorting to manual unpacking:

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 a similar lazy structure using a universal view for polymorphic elements):

In an "equivalent" structure that specializes node in representing the type of an element, removing a few references to node:

In particular, the spiny-lazy, node-strict / unboxed data types, which are polymorphic but specialize in container for each element type, are denser and have significantly faster constant factors than the general data types in the box (polymorphic).

This is due to the complexity of compiling and generating instances, but this is a fruitful area of ​​research that I think. They are similar to specialized data types.

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

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