Hi, I think the module Set lacks at least a (partial) function minimum :: forall a. (Ord a) => Set a -> a because "setToList" is the only (though sufficient) function to access the elements of a list. Will "minimum = head . setToList" be correct or do I need to sort the list? I was considering using sorted lists directly, but I thought the functions `elem` and `union` are not as efficient as they could be (under the assumption that the input lists are sorted). Surely balanced trees will be better for large sets. Besides the minimum, also the maximum or the simultaneous splitting of a set into its minimum and the remaining set would be useful (for recursions). Cheers Christian
I think the module Set lacks at least a (partial) function
minimum :: forall a. (Ord a) => Set a -> a
because "setToList" is the only (though sufficient) function to access the elements of a list. Will "minimum = head . setToList" be correct or do I need to sort the list?
Surely "setToList" must yield a sorted list otherwise it was not a (pure) function. (and as I tried out, the above minimum definition is correct.) Christian
Besides the minimum, also the maximum or the simultaneous splitting of a set into its minimum and the remaining set would be useful (for recursions).
There's a lot more missing: Test for disjointness, subset-relation as well as instances for Show and Ord (lexical order, not subset-relation). Also FiniteMap should have these instances (also for Eq), if the elements have. These instances would allow nested sets and maps. Are the sets supposed to be finite, too? (more documentation would help) Christian
As long as we're on the "retrofit FiniteMap" discussion, in addition to splitting, etc, it would be really nice to have: composeFM :: Ord a, Ord b => FiniteMap a b -> FiniteMap b c -> FiniteMap a c defined in the obvious way. Also, something like: modifyFM :: Ord a => FiniteMap a b -> a -> (b -> b) -> FiniteMap ab where the function is applied to element a in the fm if it exists. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Sat, 27 Jul 2002, Christian Maeder wrote:
Besides the minimum, also the maximum or the simultaneous splitting of a set into its minimum and the remaining set would be useful (for recursions).
There's a lot more missing: Test for disjointness, subset-relation as well as instances for Show and Ord (lexical order, not subset-relation). Also FiniteMap should have these instances (also for Eq), if the elements have. These instances would allow nested sets and maps.
Are the sets supposed to be finite, too? (more documentation would help)
Christian _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Hal Daume III wrote:
As long as we're on the "retrofit FiniteMap" discussion, in addition to splitting, etc, it would be really nice to have:
composeFM :: Ord a, Ord b => FiniteMap a b -> FiniteMap b c -> FiniteMap a c
defined in the obvious way.
Also, something like:
modifyFM :: Ord a => FiniteMap a b -> a -> (b -> b) -> FiniteMap ab
where the function is applied to element a in the fm if it exists.
I agree and further propose delSetFromFM :: Ord key => FiniteMap key elt -> Set key -> FiniteMap key elt or generalize minusFM :: Ord key => FiniteMap key elt1 -> FiniteMap key elt2 -> FiniteMap key elt1 because elements in the second map are ignored anyway! Cheers Christian
There's a lot more missing: Test for disjointness, subset-relation as well as instances for Show and Ord (lexical order, not subset-relation). Also FiniteMap should have these instances (also for Eq), if the elements have. These instances would allow nested sets and maps.
Since you had difficulties to supply an instance Ord for FiniteMap (see below), here is my proposal: instance (Ord key, Ord elt) => Ord (FiniteMap key elt) where fm_1 <= fm_2 = if sizeFM fm_1 == sizeFM fm_2 -- quick test (unnecessary) && keysFM fm_1 == keysFM fm_2 then eltsFM fm_1 <= eltsFM fm_2 else keysFM fm_1 <= keysFM fm_2 -- or "<" if you wish That - besides Set - FiniteMap is an instance of Eq may almost be obvious but wasn't documented! ("show . fmToList" for "Show" would be enough for me.) Cheers Christian The sources "/ghc-5.02.2/hslibs/data/FiniteMap.lhs" showed: instance (Eq key, Eq elt) => Eq (FiniteMap key elt) where fm_1 == fm_2 = (sizeFM fm_1 == sizeFM fm_2) && -- quick test (fmToList fm_1 == fmToList fm_2) {- NO: not clear what The Right Thing to do is: instance (Ord key, Ord elt) => Ord (FiniteMap key elt) where fm_1 <= fm_2 = (sizeFM fm_1 <= sizeFM fm_2) && -- quick test (fmToList fm_1 <= fmToList fm_2) -}
participants (2)
-
Christian Maeder -
Hal Daume III