Edward Kmett | 29 Dec 00:36 2012
Picon

Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

I'd like to add foldMapWithKey to Data.Map and Data.IntMap.

Right now you can foldrWithKey and foldlWithKey on Data.Map and Data.IntMap, but you cannot foldMapWithKey.

You can fake this by using fold . mapWithKey but this requires converting the entire structure. 

You can also implement it with traverseWithKey and the use of the Const Monoid in a manner similar to foldMapDefault.

When you have a monoid that can take advantage of the balanced nature of the tree, it'd be nice to be able to not lose the original near balanced parenthesization of the source tree.

We can use this in the lens library for more efficient zippers on these containers, but in general having access to a 'balanced' foldMap is useful for any such container, and it seems odd not to be able to get at the keys in this orientation when you can go so every other way.

A patch that implements the proposed operation is available here:


Discussion Period: 2 weeks

-Edward
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
wren ng thornton | 29 Dec 10:07 2012

Re: Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

On 12/28/12 6:36 PM, Edward Kmett wrote:
> I'd like to add foldMapWithKey to Data.Map and Data.IntMap.
> [...]
> A patch that implements the proposed operation is available here:
>
> https://github.com/haskell/containers/pull/24

I haven't looked at the patch yet, but +1 for the addition.

--

-- 
Live well,
~wren
ezyang | 29 Dec 15:58 2012
Picon

Re: Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

Note that there is relevant discussion on the pull request.

I think that a fold which reflects the underlying tree structure is not
a bad idea, but it is definitely not in-line with what the current 
semantics of
Data.Map.fold are:

    -- | /Deprecated./ As of version 0.5, replaced by 'L.foldr'.
    --
    -- /O(n)/. Fold the values in the map using the given right-associative
    -- binary operator. This function is an equivalent of 'foldr' and 
is present
    -- for compatibility only.
    fold :: (a -> b -> b) -> b -> Map k a -> b
    fold = L.foldr
    {-# INLINE fold #-}

...to be noted as distinct from Data.Foldable.fold, of course!  So we might
need to bikeshed names.  It is too bad that the intermediate structure cannot
be fused away with fold . mapWithKey!

Edward

Quoting wren ng thornton <wren <at> freegeek.org>:
> On 12/28/12 6:36 PM, Edward Kmett wrote:
>> I'd like to add foldMapWithKey to Data.Map and Data.IntMap.
>> [...]
>> A patch that implements the proposed operation is available here:
>>
>> https://github.com/haskell/containers/pull/24
>
> I haven't looked at the patch yet, but +1 for the addition.
>
> -- 
> Live well,
> ~wren
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
Strake | 29 Dec 14:31 2012
Picon

Re: Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

On 28/12/2012, Edward Kmett <ekmett <at> gmail.com> wrote:
> I'd like to add foldMapWithKey to Data.Map and Data.IntMap.

+1

I just lately needed this myself.
Milan Straka | 30 Dec 11:42 2012
Picon

Re: Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

Hi all,

> -----Original message-----
> From: Edward Kmett <ekmett <at> gmail.com>
> Sent: 28 Dec 2012, 18:36
>
> I'd like to add foldMapWithKey to Data.Map and Data.IntMap.
> 
> Right now you can foldrWithKey and foldlWithKey on Data.Map and
> Data.IntMap, but you cannot foldMapWithKey.
> 
> You can fake this by using fold . mapWithKey but this requires converting
> the entire structure.
> 
> You can also implement it with traverseWithKey and the use of the Const Monoid
> in a manner similar to foldMapDefault.

One can implement foldMapWithKey as

foldMapWithKey f = foldlWithKey (\a k b -> a `mappend` f k b) mempty

This is a valid definition which does not create intermediate structure.
The difference to the proposed implementation is, as Edward mentions:

> When you have a monoid that can take advantage of the balanced nature of
> the tree, it'd be nice to be able to not lose the original near balanced
> parenthesization of the source tree.

Both definitions differ in the bracketing of the mappend-s.
This should be mentioned in the documentation of the foldMapWithKey.
However, while the bracketing of foldlWithKey and foldrWithKey is well
defined, the bracketing of foldMapWithKey depends on the internal
structure of the container. But it is probably safe to assume that the bracketing
will be "balanced" in some way for any implementation of the data structure.

Cheers,
Milan
Edward Kmett | 30 Dec 13:41 2012
Picon

Re: Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

If you think about it, traverseWithKey already mimics the bracketing of IntMap internally.

On Sun, Dec 30, 2012 at 5:42 AM, Milan Straka <fox <at> ucw.cz> wrote:
Hi all,

> -----Original message-----
> From: Edward Kmett <ekmett <at> gmail.com>
> Sent: 28 Dec 2012, 18:36
>
> I'd like to add foldMapWithKey to Data.Map and Data.IntMap.
>
> Right now you can foldrWithKey and foldlWithKey on Data.Map and
> Data.IntMap, but you cannot foldMapWithKey.
>
> You can fake this by using fold . mapWithKey but this requires converting
> the entire structure.
>
> You can also implement it with traverseWithKey and the use of the Const Monoid
> in a manner similar to foldMapDefault.

One can implement foldMapWithKey as

foldMapWithKey f = foldlWithKey (\a k b -> a `mappend` f k b) mempty

This is a valid definition which does not create intermediate structure.
The difference to the proposed implementation is, as Edward mentions:

> When you have a monoid that can take advantage of the balanced nature of
> the tree, it'd be nice to be able to not lose the original near balanced
> parenthesization of the source tree.

Both definitions differ in the bracketing of the mappend-s.
This should be mentioned in the documentation of the foldMapWithKey.
However, while the bracketing of foldlWithKey and foldrWithKey is well
defined, the bracketing of foldMapWithKey depends on the internal
structure of the container. But it is probably safe to assume that the bracketing
will be "balanced" in some way for any implementation of the data structure.

Cheers,
Milan

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

Gmane