Thanks to people for the explanations. To my question
1. elems :: Set a -> [a] setToList :: Set a -> [a]
These two look like synonyms, but have different comments. Am I missing something?
Jens Fisseler
Both functions compute the same list, and IMHO the comments state the same.
I meant the description in the ghc-6.4 documentation. Data.Set.html says " elems :: Set a -> [a] O(n). The elements of a set. setToList :: Set a -> [a] O(n). Convert the set to a list elements. " What is the difference? If they are really equivalent, then, it is natural either to remove `elems' or to follow the general GHC policy and to move setToList to the `Obsolete' list section in documentation, like it was done with many other functions for Set and FiniteMap. - ? ----------------- Serge Mechveliani mechvel@botik.ru
I meant the description in the ghc-6.4 documentation. Data.Set.html says " elems :: Set a -> [a] O(n). The elements of a set.
setToList :: Set a -> [a] O(n). Convert the set to a list elements. " What is the difference? If they are really equivalent, then, it is natural either to remove `elems' or to follow the general GHC policy and to move setToList to the `Obsolete' list section in documentation, like it was done with many other functions for Set and FiniteMap. - ?
Well, seems like both of us have messed something up. The ghc-6.4 documentation for 'setToList' says "Obsolete equivalent of elems", whereas the documentation for 'toList' (that what I was referring to) says "O(n). Convert the set to a list of elements." But, by looking at the source code, one can easily see that 'setToList' if defined in terms of 'elems' setToList :: Set a -> [a] setToList = elems which in turn is defined as elems :: Set a -> [a] elems s = toList s So, both 'setToList' and 'elems' do the same, and 'setToList' is marked as obsolete, so use 'elems'. Regards, Jens
As Jens Fisseler notes, I have made a confusion about Set.elems, Set.toList, Set.setToList. Docs on setToList occurs all right (`Obsolete' item). And for some reason, Data.Set.html shows the pair
" elems :: Set a -> [a] O(n). The elements of a set.
toList :: Set a -> [a] O(n). Convert the set to a list elements. "
Hm, let it be. I do not know, maybe the documentation could say why there are two of them. ----------------- Serge Mechveliani mechvel@botik.ru
Serge D. Mechveliani wrote:
As Jens Fisseler notes, I have made a confusion about
Set.elems, Set.toList, Set.setToList.
There is even Set.toAscList (although one may argue that should be Set.toDistinctAscList) I think the right choice is Set.toList (replacing setToList) Is Set.elems just a (nicer?, useless?) synonym for Set.toList? There are also Map.assocs and Map.toList being synonyms. But Map.elems is different from Map.toList and Set.elems would only correspond to Map.elems for some identity maps (not for the old set implementation using maps with dummy elements "()") Cheers Christian P.S Map.insert indeed replaces existing values (and should be used instead of addToFM with changed argument position for the input map)
This being the topic, I'll list the issues I ran into with the new Data.Map library: 1. The function Map.union is left-biased whereas the old FiniteMap.unionFM was right-biased. The change seems rather arbitrary. There are also other changes of this kind, the following two notable among them: 2. The functions passed to Map.insertWith and Map.insertWithKey expect their arguments in opposite order from the old FiniteMap.addToFM_C. To make matters worse, the correct order is not documented so the user is forced to guess. When I converted my source to use Data.Map instead of FiniteMap, I guessed wrong and it took me a while to find what was wrong. 3. The Data.Map looks much better than the FiniteMap library, and its export list is very complete. There are, however, two (or four) more functions that would be really nice to have in there, as they are impossible to write efficiently with the functions currently provided: mapFilter :: (a -> Maybe b) -> Map k a -> Map k b mapFilter f = map Maybe.fromJust . filter Maybe.isJust . map f mapPartition :: (a -> Either b c) -> Map k a -> (Map k b, Map k c) mapPartition f = removeTags . partition isLeft . map f where isLeft (Either.Left _) = True isLeft (Either.Right _) = False removeTags (leftMap, rightMap) = (map (\ (Left x) -> x) leftMap, map (\ (Right x) -> x) rightMap) For completeness, mapFilterWithKey and mapPartitionWithKey could be thrown in too.
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 mapPartition f = Map.foldWithKey ( \ k v (l, r) -> either ( \ x -> (Map.insert k x l, r)) ( \ x -> (l, Map.insert k x r)) $ f v) (Map.empty, Map.empty) Could it be more efficient? Cheers Christian
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.
On Jun 2, 2005, at 10:29 AM, Mario Blazevic wrote:
... 3. The Data.Map looks much better than the FiniteMap library, and its export list is very complete. There are, however, two (or four) more functions that would be really nice to have in there, as they are impossible to write efficiently with the functions currently provided:
mapFilter :: (a -> Maybe b) -> Map k a -> Map k b mapFilter f = map Maybe.fromJust . filter Maybe.isJust . map f
mapPartition :: (a -> Either b c) -> Map k a -> (Map k b, Map k c) mapPartition f = removeTags . partition isLeft . map f where isLeft (Either.Left _) = True isLeft (Either.Right _) = False removeTags (leftMap, rightMap) = (map (\ (Left x) -> x) leftMap, map (\ (Right x) -> x) rightMap)
Having worked on implementing, eg. IntSet in terms of FiniteMap-type code + UInt32 bitmaps at the nodes, I eventually hit on a basic set of functions which seem to let you do everything. Here in a descriptive (but possibly buggy) notation: data Found a = Keep | Modify a | Delete data Missing a = Omit | Insert a lookupLike :: (Ord k) => (r, Missing a) -> -- What to do to map when the key is not found (a -> (r, Found a)) -> -- What to do to map when the key is found k -> Map k a -> (r, Map k a) lookupLike can be used to do arbitrarily nasty update, insertion, and deletion actions. The "Keep" and "Omit" actions allow fast return without re-allocation if nothing changes. It can also be used to perform pure lookup of all kinds, though it'll generally be unacceptably clunky. We really should add a "k" argument to both the found and not found actions to be completely general---but this only matters if equality throws away information that is actually important, for example if we're being perverse and stashing our value in the key. type MapOrFilter k a b = k -> a -> Maybe b mapFilterLike :: (Ord k) => MapOrFilter k a b -> Map k a -> Map k b This is basically the mapFilter from above, with the key argument thrown in. From this we can get arbitrary generalizations of map and filter. mapPartition from above, again with an additional key argument, should be the only splitter you ever need. data UpdateAction k a b where Discard :: UpdateAction k a b NoUpdate :: UpdateAction k a a UpdateWith :: MapOrFilter k a b -> UpdateAction k a b joinLike :: (Ord k) => UpdateAction k a c -> -- What to do with elements only in first map UpdateAction k b c -> -- What to do with elements only in second map (k -> a -> b -> Maybe c) -> -- How to combine elements in both maps Map k a -> Map k b -> Map k c This can be used to implement union, intersection, difference, union with combine, and so forth. Alas, the complexity of an UpdateAction is required, since NoUpdate and Discard can change the asymptotic complexity of the join relative to doing everything using MapOrFilter. Technically, of course, we can replace the type UpdateAction k a b with an equivalent function Map k a -> Map k b, but that doesn't clearly convey the intention. So, anyone bold enough to put these "most general possible" functions into a Map implementation? I'm guessing there won't be general agreement on the names / types of the actions, but the general idea is tested and sound. -Jan-Willem Maessen
participants (5)
-
Christian Maeder -
Jan-Willem Maessen -
Jens Fisseler -
Mario Blazevic -
Serge D. Mechveliani