headers
Johan Tibell | 29 Aug 2010 15:34
Picon
Gravatar

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

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.


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Permalink | Reply |
headers
Thomas Schilling | 3 Sep 2010 03:00
Gravatar

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

+1

On 29 August 2010 14:34, Johan Tibell <johan.tibell <at> gmail.com> 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 <at> 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.
Permalink | Reply |
headers
Brian Bloniarz | 3 Sep 2010 08:46
Picon

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

On Sun, 29 Aug 2010 15:34:29 +0200
Johan Tibell <johan.tibell <at> gmail.com> 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?
Permalink | Reply |
headers
Johan Tibell | 3 Sep 2010 16:14
Picon
Gravatar

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

On Fri, Sep 3, 2010 at 8:46 AM, Brian Bloniarz <brian.bloniarz <at> gmail.com> wrote:

On Sun, 29 Aug 2010 15:34:29 +0200
Johan Tibell <johan.tibell <at> gmail.com> 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
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Permalink | Reply |
headers
Ian Lynagh | 3 Sep 2010 17:34
Picon
Gravatar

Re: 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 <brian.bloniarz <at> gmail.com>wrote:
> 
> > On Sun, 29 Aug 2010 15:34:29 +0200
> > Johan Tibell <johan.tibell <at> gmail.com> 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
Permalink | Reply |
headers
Johan Tibell | 3 Sep 2010 18:00
Picon
Gravatar

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

On Fri, Sep 3, 2010 at 5:34 PM, Ian Lynagh <igloo <at> earth.li> 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 <brian.bloniarz <at> gmail.com>wrote:
>
> > On Sun, 29 Aug 2010 15:34:29 +0200
> > Johan Tibell <johan.tibell <at> gmail.com> 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

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Permalink | Reply |

Gmane