Dear GHC team, I am looking into the .html docs on the libraries of Map and Set. Here follow the questions and notices. 1. elems :: Set a -> [a] setToList :: Set a -> [a] These two look like synonyms, but have different comments. Am I missing something? 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? 3. Data.Map has lookup and findWithDefault. According to name correspondence, a natural name for the latter would be lookupWithDefault - ? 4. Data.Set.intersection. In old library, it was `intersect' -- if I recall correct. So, it is natural to include `intersect' to the `Obsolete' list. 5. Name resolution. ./Prelude0.hs:254:28: Ambiguous occurrence `null' It could refer to either `Data.Set.null', imported from Data.Set at ./Prelude0.hs:50:48-51 or `GHC.List.null', imported from Prelude at ./Prelude0 Could the compiler detect where null applies to list and where to Set ? For this is visible from the types in the user program. 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) ? With kind regards, ----------------- Serge Mechveliani mechvel@botik.ru
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
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
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.net⑆john⑈
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
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. Cheers, JP.
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
On Jun 3, 2005, at 4:47 PM, Adrian Hey wrote:
On Thursday 02 Jun 2005 10:18 am, Jean-Philippe Bernardy wrote:
The definition of the Set datatype being
... [Something strict in all components] It seems you'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?
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. -Jan-Willem Maessen
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
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
On Jun 4, 2005, at 1:28 AM, Adrian Hey wrote:
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.
And thus, genericLength doesn't make particular sense for these sets. There is no risk of overflow.
...
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 :-)
Hopefully the extra sentence clarifies the point? The original debate seemed to focus around the need to measure map size with an Integer, because they might be Really Big or even infinite. That's not actually feasible, since a map with O(1) size measurement is by definition strict. -Jan-Willem Maessen
Is it possible to get GCC to use the intel C compiler (ICC) instead of gcc? Keean.
Keean Schupke wrote:
Is it possible to get GCC to use the intel C compiler (ICC) instead of gcc?
Do you mean is it possible to get /GHC/ to use /ICC/? Otherwise I don't understand the question.
Keean. _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Hello Seth, Sunday, June 05, 2005, 2:05:14 PM, you wrote:
Is it possible to get GCC to use the intel C compiler (ICC) instead of gcc?
SK> Do you mean is it possible to get /GHC/ to use /ICC/? Otherwise I don't SK> understand the question.
yes. or at least link togehther object files created by gcc 3.2 and icc/win32 -- Best regards, Bulat mailto:bulatz@HotPOP.com
Sorry, yes I mean getting GHC to use ICC instead of GCC... is it just a matter of a command line switch to give GHC the path to the compiler? Keean. Seth Kurtzberg wrote:
Keean Schupke wrote:
Is it possible to get GCC to use the intel C compiler (ICC) instead of gcc?
Do you mean is it possible to get /GHC/ to use /ICC/? Otherwise I don't understand the question.
Keean. _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Yes, thats exactly what I mean. Can I switch the compiler to use with a command line switch? ICC is compatible with GCC and can use the same libraries. The main advantage is the automatic vectorisation of loops, to use SSE / MMX. Keean. Seth Kurtzberg wrote:
Keean Schupke wrote:
Is it possible to get GCC to use the intel C compiler (ICC) instead of gcc?
Do you mean is it possible to get /GHC/ to use /ICC/? Otherwise I don't understand the question.
participants (11)
-
Adrian Hey -
Bulat Ziganshin -
Jan-Willem Maessen -
Jean-Philippe Bernardy -
Jens Fisseler -
John Meacham -
Keean Schupke -
Robert van Herk -
S. Alexander Jacobson -
Serge D. Mechveliani -
Seth Kurtzberg