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

[Johan Tibell]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100903/f0d1be7c/attachment.html