Containers and strictness continued

[Claus Reinke]

> for my work on the containers I need to settle some questions about 
> strictness.

Thanks again for driving this.

+1 for consistent strictness in keys
+1 for adding strict folds

Since I've been wondering about this problem for a while,
I would like to add two closely related suggestions:

(a) the useability of several higher-order functions in the API
    can be improved by splitting them into wrapper and worker
    (the wrapper gets inlined away, leaving an inlined worker
    for which the functional parameter is fixed, so that the
    strictness analyser can do a better job; see GHC's
    implementations of list folds)

(b) the only reason not to add strict-in-value versions of
    (Int)Map has been code duplication; it turns out that
    it might be possible to use the standard SPECIALIZE
    pragma to do most of the work for us, using nothing
    more than FlexibleInstances and MultiParamTypeClasses
    (no functional dependencies, no type families).

    The idea would be to provide both IntMap and IntMap',
    the latter being strict in the keys. There would be one
    type class abstractly representing IntMap constructors
    and (pattern match) views, and each of the API functions
    would be implemented once, in terms of this class. Then
    each of these abstract implementations would be
    specialized to both IntMap and IntMap'.

    Appended below is a concrete example of this abstract
    idea, a module with both strict (L1) and non-strict (L2)
    lists, an abstract interface (L) and a single definition
    of map (mapL) that is specialized for both use cases.
    For comparison, handcoded versions of mapL1 and
    mapL2 are also included.

    This module is small enough that one can compare
    the core output (-ddump-simpl), and it looks as if
    the -O2 compiled core for the specialized versions
    of mapL matches that for the handcoded versions.
    No manual duplication, just pragmas, same code
    and API, just different types for the two use cases.

(a) could be included directly, (b) is just offered for
discussion at the moment. If there are no hidden
traps in (b), I would like to see it implemented as
well, to reduce the frequent space issues with Maps
and large datasets.

Note that the combination of (a) and (b) could
replace some of the proposed special-purpose
strict functions, keeping the API simpler.

Claus

-----------------

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module Main(mapL1,mapL2,mapL,main) where

data L1 a = N1 | C1 !a (L1 a) deriving Show

-- mapL specialised to L1 should be as good as mapL1
mapL1 f N1       = N1
mapL1 f (C1 a l) = C1 (f a) (mapL1 f l)

data L2 a = N2 | C2 a (L2 a) deriving Show

-- mapL specialised to L2 should be as good as mapL2
mapL2 f N2       = N2
mapL2 f (C2 a l) = C2 (f a) (mapL2 f l)

class L l a where
  -- constructors
  n :: l a
  c :: a -> l a -> l a
  -- view (abstract pattern match)
  v :: l a -> b -> (a -> l a -> b) -> b

mapL :: (L l a,L l b) => (a -> b) -> l a -> l b
{-# SPECIALIZE mapL :: (a -> b) -> L1 a -> L1 b #-}
{-# SPECIALIZE mapL :: (a -> b) -> L2 a -> L2 b #-}
mapL f l = (v l) n (\x xs->c (f x) (mapL f xs))

instance L L1 a where
  n = N1
  c = C1
  v N1       n c = n
  v (C1 a l) n c = c a l

instance L L2 a where
  n = N2
  c = C2
  v N2       n c = n
  v (C2 a l) n c = c a l

main = do
  print $ mapL (+1) $ C1 0 $ C1 1 $ C1 2 $ N1
  print $ mapL (+1) $ C2 0 $ C2 1 $ C2 2 $ N2

  print $ mapL1 (+1) $ C1 0 $ C1 1 $ C1 2 $ N1
  print $ mapL2 (+1) $ C2 0 $ C2 1 $ C2 2 $ N2