Map library

[Mario Blazevic]

Christian Maeder wrote:

>Mario Blazevic wrote:
>  
>
>>  mapFilter :: (a -> Maybe b) -> Map k a -> Map k b
>>  mapFilter f = map Maybe.fromJust . filter Maybe.isJust . map f
>>    
>>
>
>How about using Map.foldWithKey (and adding "Ord k =>" to the type
>signature)?
>
>mapFilter f = Map.foldWithKey ( \ k -> maybe id (Map.insert k) . f)
>    Map.empty
>  
>
    That's what I ended up doing, more or less. Not having seen the
library source code, I can't be completely sure. Maybe ghc can perform
some deforestation wonder and make it more efficient than the sum of its
parts. Otherwise, here's how it works out:

    Map.filter has O(n) complexity, and I don't see any reason to expect
library-provided mapFilter to be any worse.

    Map.foldWithKey is O(n)
    Map.insert is O(log n), and gets executed as many times as f returns
True. That's O (n log n)

    The complexity of user implementation of  mapFilter is O (n + n
log(n)) = O(n log n)

-- 
Mario Blazevic
mblazevic at ca.stilo.com
Stilo Corporation

This message, including any attachments, is for the sole use of the
intended recipient(s) and may contain confidential and privileged
information. Any unauthorized review, use, disclosure, copying, or
distribution is strictly prohibited. If you are not the intended
recipient(s) please contact the sender by reply email and destroy
all copies of the original message and any attachments.