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
[EMAIL PROTECTED]
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.
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
