Libraries for strict data structures in Haskell [closed]

Question

What libraries do exist that implement strict data structures? Specifically, I am looking for strict lists and strict sets.

Disclaimers:

1. I am aware of deepseq. It's very useful, but it adds the overhead of traversing the whole data structure every time you use deepseq (which might be more than once).

2. I am aware that a strict container-like data structure does not ensure everything it contains will be fully evaluated, but the structure itself should be strict, e.g.:

   data StrictList a = !a :$ !(StrictList a) | Empty
   

   (Here, the contained elements are in WHNF, and possibly not fully evaluated, but the structure of the list is. For example, infinite lists will be non-terminating values.)

3. I know about the 'strict' package on hackage, but it has a very limited set of strict data structures. It does neither contain strict lists nor sets.

4. Writing strict lists myself seems amazingly easy (I love ghc's extensions to derive Functor, Traversable and Foldable, btw.), but it still seems like it would be better done in a separate library. And efficient implementations of sets don't seem that trivial to me.

Answer 1

The containers package (shipped with ghc) will soon have strict Set and Map variants (I'm not sure they will be included with ghc-7.4, but there's reason to hope). So an efficient implementation of strict Sets and Maps is on the way. Strict lists are, as you say easy, still a package on hackage providing them would be nice, so not everybody has to do it themselves. What else do you need?

Answer 2

For your second point, the term I've seen most often is spine-strict.

For a spine-strict list, you could probably use Data.Seq.Sequence (from containers) or Data.Vector (from vector). Neither one is a list, however depending on what you're doing one (or both) are likely to be better. Sequence provides O(1) cons and snoc, with very fast access to either end of the structure. Vector's performance is similar to an array. If you want a more list-like interface to Sequence, you might consider the ListLike package (there's a ListLike interface for vectors too, but it's less useful because Vector provides a fairly comprehensive interface on its own). Both are spine-strict.

For strict sets, you might try unordered-containers, which also provides a strict map.