Need principled approach to strictness properties in Data.Map.Strict

wren ng thornton wren at freegeek.org
Mon Nov 21 00:14:12 CET 2011


On 11/19/11 2:39 AM, Bardur Arantsson wrote:
> On 11/19/2011 12:03 AM, Johan Tibell wrote:
>> Without the extra strictness there are degenerate cases that can
>> catch people off guard. For example,
>>
>> insertWith (\ old new -> if old == maxValue then old else new + 1) k v m
>>
>> is lazy in 'v' because there's a rare case (old == maxValue) where
>> 'new' isn't evaluated.
>
> For me, this behavior would really violate the POLA.
>
> If I'm passing something to an API which "is strict" (as indicated by
> Data.Map.Strict), then I'd certainly expect everything I pass in to be
> evaluated.

Though this behavior can be quite useful. Say that v is some big hairy 
computation. By deferring evaluation until after we know that (old /= 
maxValue) we can avoid it, and yet if it turns out that we do need it 
then we will be sure to evaluate it before putting it into the map. This 
is particularly useful if we know that the values are going to be 
hitting the maxValue pretty regularly, so we can save on computing v 
pretty regularly.

It's not clear that this combination of laziness and strictness can be 
achieved through the lazy map interface. Whereas we can clearly get the 
strict version from this semilazy version, by just adding bangs to the 
arguments of the lambda. That doesn't say anything about POLA, though 
personally I don't find the behavior too astonishing so perhaps I'm not 
the best to judge.

Overall I don't care whether the property (1) holds for all the 
functions in the strict map interface, so long as it is documented 
whether it does or not for each function. The things I do care about are 
the efficiency of the loops (which votes for full strictness), and the 
expressivity of the complete interface (e.g., as with the example above; 
which votes for semilaziness/semistrictness somewhere in the API).

-- 
Live well,
~wren



More information about the Libraries mailing list