containers: to be or not to be (strict, in this case)?

[John Meacham]

On Wed, Mar 04, 2009 at 07:45:18PM -0500, Isaac Dupree wrote:
> Claus Reinke wrote:
> > The idea being to abstract over every application of the container
> > constructors to the element type, then to supply either strict or
> > non-strict application. Ultimately, one might prefer a
> > type-constructor-based abstraction instead, to gain additional performance,
> > but this should be at least as good as the current situation (perhaps with
> > an INLINE on the parameterised versions), without the duplication.
> 
> the "Box" approach is attractive but performance-unoptimal...
> 
> we can try that type-constructor stuff.  Is it like:
> 
> data IntMap_ strictness a = ... --(not including "strictness" values)
> data Strict
> data Lazy
> class Strictness s where ...
> 
> well, it turns out to have similar performance issues to passing around ($) or 
> ($!), except they'd be resolved in the compiler by SPECIALIZE rather than 
> INLINE stuff (I guess).
> 
> Anyway, the compiler basically can't optimize away Box at all.
> 
> And changing the strictness of a Box-based IntMap, would be linear time rather 
> than constant (zero) time for a purely newtype-based solution (if indeed they 
> need to be separate types, rather than just different modules with different 
> implementations of e.g. insertWith for the same data-type).

Hmm.. would it make sense to want to use both lazy and strict operations
on the same data type? It seems like it could be useful which argues against
making them distinct types. 

Actually, how many of the standard operations do we need strict versions
of? most are strictness agnostic to begin with, it seems that just
providing insert' alternatives for those ones that matter would be
enough and leaving the implementation of the strict versions to the
internals of the library. parameterizing by the application function and
pervasive inlining like you said seems like a reasonable way to go about
it.

for Data.Set it seems like we would only need alternate versions of not
more than a half dozen or so functions. Since only a few actually add
elements to the set and the other operations are strictness preserving
(as in, a union of strict sets is a strict set).

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈