Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

Johan Tibell

29 Aug 2010 29 Aug '10

1:34 p.m.

http://hackage.haskell.org/trac/ghc/ticket/4278 Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map This proposal depends on #4277 [1]. The current Data.Map API lacks two important functions: * A strict left (pre-order) fold -- needed to e.g. sum all the values in a map efficiently. * A strict insertLookupWithKey' -- needed to e.g. update an integer counter and retrieve the previous value in a single traversal. The benchmark we ran indicates that foldlWithKey' is 95% faster than its lazy counter part.insertLookupWithKey' is only 6% faster, but the speedup is highly dependent on how many times each element is update. Each element was only updated once in our benchmark so real speedups should be larger. The consideration period is 3 weeks. 1. http://hackage.haskell.org/trac/ghc/ticket/4277

Attachments:

attachment.html (text/html — 1.1 KB)

Show replies by date

Thomas Schilling

3 Sep 3 Sep

1 a.m.

+1 On 29 August 2010 14:34, Johan Tibell wrote:

...

http://hackage.haskell.org/trac/ghc/ticket/4278 Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map This proposal depends on #4277 [1].

The current Data.Map API lacks two important functions:

* A strict left (pre-order) fold -- needed to e.g. sum all the values in a map efficiently.

* A strict insertLookupWithKey' -- needed to e.g. update an integer counter and retrieve the previous value in a single traversal.

The benchmark we ran indicates that foldlWithKey' is 95% faster than its lazy counter part.insertLookupWithKey' is only 6% faster, but the speedup is highly dependent on how many times each element is update. Each element was only updated once in our benchmark so real speedups should be larger.

The consideration period is 3 weeks.

1. http://hackage.haskell.org/trac/ghc/ticket/4277

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

-- If it looks like a duck, and quacks like a duck, we have at least to consider the possibility that we have a small aquatic bird of the family Anatidae on our hands.

Brian Bloniarz

6:46 a.m.

On Sun, 29 Aug 2010 15:34:29 +0200 Johan Tibell wrote:

...

Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

+1, insertLookupWithKey' I could have used recently. Is there some reason why all the other WithKey functions don't require strict variants? Asked another way, suppose I want to build a Map via foldl' (unionWith (+)) without space leaks, is that possible?

Johan Tibell

2:14 p.m.

On Fri, Sep 3, 2010 at 8:46 AM, Brian Bloniarz wrote:

...

On Sun, 29 Aug 2010 15:34:29 +0200 Johan Tibell wrote:

...
Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

+1, insertLookupWithKey' I could have used recently.

Is there some reason why all the other WithKey functions don't require strict variants? Asked another way, suppose I want to build a Map via foldl' (unionWith (+)) without space leaks, is that possible?

No reason, expect that I didn't have a need for it. Every function that takes a higher-order argument that combines two values needs a strict variant. I would like to go over the whole API at some point and see if it could be simplified somehow, without breaking any packages. The API is overly complicated an provides lots of functions with overlapping behavior. To do this properly I need to first build all of Hackage and create an index which I can use to find all calls to function in Data.Map. Any function that's not called at all would be a candidate for removal. Cheers, Johan

Ian Lynagh

3:34 p.m.

New subject: Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

On Fri, Sep 03, 2010 at 04:14:41PM +0200, Johan Tibell wrote:

...

On Fri, Sep 3, 2010 at 8:46 AM, Brian Bloniarz wrote:

...
On Sun, 29 Aug 2010 15:34:29 +0200 Johan Tibell wrote:

...
Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

+1, insertLookupWithKey' I could have used recently.

Is there some reason why all the other WithKey functions don't require strict variants? Asked another way, suppose I want to build a Map via foldl' (unionWith (+)) without space leaks, is that possible?

No reason, expect that I didn't have a need for it. Every function that takes a higher-order argument that combines two values needs a strict variant.

Adding foldlWithKey' but not foldrWithKey' seems particularly odd to me.

...

-- | /O(n)/. A strict version of 'foldlWithKey'. foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b foldlWithKey' f = go where go z Tip = z go z (Bin _ kx x l r) = z `seq` go (f (go z l) kx x) r

As discussed in the thread for your previous proposal, I think the (go z l) should be forced too: http://www.haskell.org/pipermail/libraries/2010-August/014091.html

...

-- | /O(log n)/. A strict version of 'insertLookupWithKey'. insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) insertLookupWithKey' f kx x = kx `seq` go where go Tip = x `seq` (Nothing, singleton kx x) go (Bin sy ky y l r) = case compare kx ky of LT -> let (found, l') = go l in (found, balance ky y l' r) GT -> let (found, r') = go r in (found, balance ky y l r') EQ -> let x' = f kx x y in x' `seq` (Just y, Bin sy kx x' l r)

I'm not sure whether it makes more sense to always force x here. I guess it probably doesn't. Thanks Ian

Johan Tibell

4 p.m.

On Fri, Sep 3, 2010 at 5:34 PM, Ian Lynagh wrote:

...

On Fri, Sep 03, 2010 at 04:14:41PM +0200, Johan Tibell wrote:

...
On Fri, Sep 3, 2010 at 8:46 AM, Brian Bloniarz
...
On Sun, 29 Aug 2010 15:34:29 +0200 Johan Tibell wrote:

...
Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

+1, insertLookupWithKey' I could have used recently.

Is there some reason why all the other WithKey functions don't require strict variants? Asked another way, suppose I want to build a Map via foldl' (unionWith (+)) without space leaks, is that possible?

No reason, expect that I didn't have a need for it. Every function that takes a higher-order argument that combines two values needs a strict variant.

Adding foldlWithKey' but not foldrWithKey' seems particularly odd to me.

Will add foldrWithKey' as as well (these are terrible names btw).

...

...
-- | /O(n)/. A strict version of 'foldlWithKey'. foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b foldlWithKey' f = go where go z Tip = z go z (Bin _ kx x l r) = z `seq` go (f (go z l) kx x) r

As discussed in the thread for your previous proposal, I think the (go z l) should be forced too: http://www.haskell.org/pipermail/libraries/2010-August/014091.html

I'll fix that.

...

...
-- | /O(log n)/. A strict version of 'insertLookupWithKey'. insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) insertLookupWithKey' f kx x = kx `seq` go where go Tip = x `seq` (Nothing, singleton kx x) go (Bin sy ky y l r) = case compare kx ky of LT -> let (found, l') = go l in (found, balance ky y l' r) GT -> let (found, r') = go r in (found, balance ky y l r') EQ -> let x' = f kx x y in x' `seq` (Just y, Bin sy kx x' l r)

I'm not sure whether it makes more sense to always force x here. I guess it probably doesn't.

I'll look at whatever insertWithKey' does and do the same for consistency. Thanks for the feedback. -- Johan

5419

Age (days ago)

5424

Last active (days ago)

List overview

Download

5 comments

4 participants

participants (4)

Brian Bloniarz
Ian Lynagh
Johan Tibell
Thomas Schilling