21

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.

shahn
  • 577
  • 2
  • 13
  • Why do you need a strict structure? – fuz Nov 14 '11 at 16:17
  • 1
    @FUZxxl ensuring that things are evaluated without delay can often reduce space usage and make computations much faster. It can also have the reverse effect, so lazy structures are important too. For efficient code, you need both (and have to know/find out which to use where). – Daniel Fischer Nov 14 '11 at 16:25
  • @FUZxxl: I was doing state-monad-like things on a Set where I would insert and delete elements from the set very often but not evaluate the Set for some time. This resulted in a space leak, which could be fixed by spine-strict (thanks, John L) data structures. – shahn Nov 15 '11 at 10:16

2 Answers2

13

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?

Sven Koschnicke
  • 6,523
  • 2
  • 34
  • 49
Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
7

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.

John L
  • 27,937
  • 4
  • 73
  • 88
  • 1
    Does spine-strict mean, that elements will be evaluated to WHNF (like in my StrictList example above)? So, could you remove the first exclamation mark and still call it spine-strict? – shahn Nov 15 '11 at 10:29
  • 1
    @shahn: spine-strict means that the structure of the container will be fully evaluated, but the elements may not be evaluated at all. So yes, you can remove the first exclamation mark in your example and still be spine-strict. – John L Nov 15 '11 at 17:29