On Fri, Jul 9, 2010 at 11:56 AM, Milan Straka wrote:

Hi all,

for my work on the containers I need to settle some questions about strictness. Thank you very much for your opinions.

Discussion ends: 23. July 2010.

1) Strictness of keys and values in the datatype.

Currently we have the following strictness flags in the datatypes: - IntMap: !key value - IntSet: !key - Map: !key value - Set: key

I vote for changing Set to store keys also strict.

Storing values as nonstrict probably makes sense.

2) Strictness of keys and values in the method definitions.

The IntMap.lookup (lookup k t = ... seq k ...) evaluates the given key even if it is not needed (when searching empty tree). Some methods are more carefull.

I vote for all IntMap, IntSet, Map and Set methods that are given a key value (insert, delete, member, ...) to be strict in the keys. This a) would be consistent with 1) b) would be a bit more efficient (~5% in the IntMap.lookup case)

3) Strict folds

Currently there are no strict folds.

I vote for adding strict folds (fold', foldWithKey' when appropriate) to all Map, Set, IntMap, IntSet.

I agree on all points. I've looked into the core generated for lookup, insert, etc and it looks better when the key is strict. It's hard to actually make use of the fact that some function aren't strict in the key, as they are only non-strict in the case of an empty data structure (so they're conditionally non-strict). Johan

+1 across the board You may also want to look at adding monadic inserts/adjusts/etc in the sense that there is currently no way to insertWith and extract any information in one pass. This means a lot of otherwise trivial operations on tries built out of Map/IntMap take twice as long as would be otherwise necessary. Sent from my iPhone On Jul 9, 2010, at 5:56 AM, Milan Straka wrote:

Hi all,

for my work on the containers I need to settle some questions about strictness. Thank you very much for your opinions.

Discussion ends: 23. July 2010.

1) Strictness of keys and values in the datatype.

Currently we have the following strictness flags in the datatypes: - IntMap: !key value - IntSet: !key - Map: !key value - Set: key

I vote for changing Set to store keys also strict.

Storing values as nonstrict probably makes sense.

2) Strictness of keys and values in the method definitions.

The IntMap.lookup (lookup k t = ... seq k ...) evaluates the given key even if it is not needed (when searching empty tree). Some methods are more carefull.

I vote for all IntMap, IntSet, Map and Set methods that are given a key value (insert, delete, member, ...) to be strict in the keys. This a) would be consistent with 1) b) would be a bit more efficient (~5% in the IntMap.lookup case)

3) Strict folds

Currently there are no strict folds.

I vote for adding strict folds (fold', foldWithKey' when appropriate) to all Map, Set, IntMap, IntSet.

Cheers, Milan Straka

PS: I will be unavailable and not reading mail till 19. July 2010. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

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