Containers and strictness

[Claus Reinke]

>> >  As Claus wrote, right now it is undocumented and inconsistent (both in
>> >  the methods of one container and also in the same methods of different
>> >  container).
>>
>> Just as it is sometimes important to be able to do strict inserts, it
>> is important sometimes that we have maps that are lazy in the
>> elements. There are important use cases both ways.
>
> I thought we are talking only about keys/elements. I would leave the
> values untouched.

There are problems at several levels:

1 it needs to be documented/specified to what extent one can
    rely on strictness; usually, Maps are
    - strict in keys and structure (so forcing the Map forces all keys),
    - not strict in values

2 it needs to be documented to what extent operations preserve
    or enforce strictness;

3 when the default strictness does not match the needs of the
    application, the library needs to provide sufficient hooks for
    enforcing different strictness policies (there might be a
    relation to the recent strategies work, btw);

All three points are currently undocumented, though 1 is assumed.
2 and 3 are terribly inconsistent at the moment: not only are there
missing strict-in-values versions of most operations, and some
versions only in Map, not in IntMap; the real problems start when
the existing operations simply do not provide the means to
enforce different strictness policies.

Things one wants to be able to do include:

- pass strict operations to higher-order API functions and have
    the strictness information propagated through the strictness
    analyser

- tie value evaluation to key availability (since the Map is strict
    in the latter, it would then become strict in the former, too)

- preserve/push strictness policies through all API operations
    (don't have foldl's accumulating Maps blow up because of
    non-strictifiable Map combination operators; don't have
    inserts sometimes evaluate values, sometime not; don't
    have Map traversal operations in the API that give no handle
    for adding strictness)

As Duncan points out, both strict and non-strict versions
have their uses. Non-strict in values is a useful default, IMHO,
but one needs to be able to introduce strictness where required
(some have argued for strict in values as default, with a data
type indirection to re-introduce non-strictness).

The blowups I've seen usually involve values not being
evaluated through Map/IntMap operations (insert, fold,
union, ..). But as with foldr/foldl/fold', that does not mean
that everything should be strict, just that users need to be
able to specify as much or as little strictness as is appropriate
for their application.

Claus