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@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.