Containers and strictness

[Felipe Lessa]

On Wed, Jun 30, 2010 at 8:02 PM, Johan Tibell <johan.tibell at gmail.com> wrote:
> On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka <fox at ucw.cz> wrote:
>> After suggestions by others I am thinking about
>>  data Some elem = Single {-# UNPACK #-} !elem | More (Set elem)
>> or
>>  data Some elem = Single {-# UNPACK #-} !elem | More {-# UNPACK #-} !elem
>> (Some elem)
>
> Unfortunately unpacking doesn't work for polymorphic fields (the new warning
> for ineffective unpack pragmas in GHC head should warn about this). Given
> this you might as well use a standard list.

However strictness information does work.  But I don't know the answer
for the following questions:

  - Should the elements be strict even while they are not unpacked?
Performance gains?

  - Should the spine of the list be strict? Performance gains? Space leak gains?

My guess, without any benchmarks, is that both elements and the spine
should be strict.  In any case, for the HashMap the following data
type saves the indirection of the tuples:

  data SomePairs key val =
        Pair !key !val
      | MorePairs !key !val !(SomePairs key val)

Cheers,

-- 
Felipe.