Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_
Edward Kmett
ekmett at gmail.com
Tue Aug 6 20:26:01 CEST 2013
On Tue, Aug 6, 2013 at 2:09 PM, Milan Straka <fox at ucw.cz> wrote:
> Hi Edward,I am not suggesting we should change the behaviour of existing
> functions
> and traverseWithKey_ should definitely use the same order as
> traverseWithKey. Changing semantics without changing type signatures is
> really suspicious and usually plainly wrong.
>
I wholeheartedly agree. =) I was just basing that on the code Ryan posted:
> traverseWithKey_ f = go
> where go Tip = pure ()
> go (Bin _ k v l r) = f k v *> go l *> go r
>
>
... which visits the key/value pairs out of order unlike, say:
go (Bin _ k v l r = go l *> f k v *> go r
> Nevertheless, I was wondering whether we should have a monadic fold
> (foldrM and foldlM) which would process the elements in a given order
> (ascending and descending, analogously to foldr and foldl). From one
> point of view, we can implement foldrM and foldlM using foldr and foldl,
>
Sure, foldrM is typically implemented in terms of foldl and foldlM is
typically implemented in terms of foldr.
Do the usual definitions like that leak on a Map?
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m
bfoldrM f z0 xs = foldl f' return xs z0 where f' k x z = f x z >>= k
foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m
afoldlM f z0 xs = foldr f' return xs z0 where f' x k z = f z x >>= k
nevertheless using linear heap space complexity compared to constant
> heap space complexity we can achieve with specialized implementations.
> This is the same situation as traverseWithKey_ -- we can implement it
> using traverseWithKey, but the heap space complexity increases.
>
traverseWithKey_ would normally be implemented with an appropriate newtype
and foldMapWithKey, rather than traverseWithKey. Does that also leak?
-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130806/bdac3e7c/attachment.htm>
More information about the Libraries
mailing list