Re: Set, Map libraries
On Thursday 02 Jun 2005 10:18 am, Jean-Philippe Bernardy wrote:
The definition of the Set datatype being
data Set a= Tip
| Bin {-# UNPACK #-} !Size a !(Set a) !(Set a)
type Size = Int
It seems your're out of luck when it comes to very large sets.
Also, since the structure is strict, it makes little sense to support
4-million-element sets.
I'd be interested to know why you say that. What would you use instead
if you needed 4-million-element sets?
The AVL trees in my implementation are strict and perfectly capable
of supporting such sets. Same should be true of Data.Set too AFAICS.
Regards
--
Adrian Hey
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Set, Map libraries
On Saturday 04 Jun 2005 1:33 am, Jan-Willem Maessen wrote: Replace 4 million by, say, 2^32 or 2^64 and I think the point stands. The set must fit in your addressable memory, and can thus be counted by a similar-sized Int. Note also that set implementations which cache the size locally will have this property in general, whether the rest of the structure is strict or not---we'll at least have to compute how many insertions and deletions have occurred, and left the thunks kicking around if we haven't actually performed them completely yet. I'm afraid I still don't really understand point we're debating, so can't comment on whether or not it stands (unless the point is that you can't deal with sets that won't fit in available memory :-) Is that all we're discussing here? Or maybe it's a point about word size used to represent Ints? JPB's remarks about strictness led me to suspect there might be some unstated algorithmic insight behind them (like a lazy implementation would not be so limited, or would offer better performance or space behaviour perhaps). But maybe I was wrong. Regards -- Adrian Hey ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Set, Map libraries
1. elems :: Set a - [a] setToList :: Set a - [a] These two look like synonyms, but have different comments. Am I missing something? Both functions compute the same list, and IMHO the comments state the same. 2. size :: Set a - Int-- O(1) ... And for large sets, the user needs to program genericSize :: Set a - Integer genericSize = genericLength . Data.Set.elems ? Is this possible to make it O(1) too? No, 'genericSize' cannot work in O(1) time, but by looking at the source you will see that a 'Set' contains an element representing its size, so 'size' can work in constant time. Regards, Jens ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Set, Map libraries
Any reason the libaries don't define: class HasNull a where null::a-Bool class HasEmpty a where empty::a I find that I sometimes switch between using lists, sets, or tables as my collection type and the forced import qualifification for generic collection operations seems annoying. -Alex- On Thu, 2 Jun 2005, Robert van Herk wrote: 6. My module applies Data.Set.null (s :: Set a), and null (xs :: [a]). Why ghc reports of the clash with GHC.List.null ? Is GHC.List same as old List library module? Should I write import GHC.List (genericLength, null) instead of import List (genericLength) ? As the documentation reads: This module is intended to be imported qualified, to avoid name clashes with Prelude http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html functions. eg. import Data.Set as Set So, you should write: import qualified Data./x/ as /y/ Now, no name clashes will occur. However, you will have to write /y/.null to access null in /x/, for example: import qualified Data.Set as Set if (Set.null ...) then ... else ... Regards, Robert ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users __ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Set, Map libraries
On Thu, Jun 02, 2005 at 05:03:26PM -0400, S. Alexander Jacobson wrote: Any reason the libaries don't define: class HasNull a where null::a-Bool class HasEmpty a where empty::a I find that I sometimes switch between using lists, sets, or tables as my collection type and the forced import qualifification for generic collection operations seems annoying. HasEmpty should be a superclass of Monoid. I have wanted that split out on various occasions. John -- John Meacham - repetae.netjohn ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
