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

3 Sep 2010


      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

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

Ian Lynagh