March 2004 - Libraries

RE: DData in hierarchical libraries
by Simon Marlow 15 Mar '04

15 Mar '04

> > The breakage to code will be fairly minimal: > Data.FiniteMap can be left > > in place but deprecated, many of the operations from > Data.Set can also > > be provided by the new Data.Set (but deprecated, of > course). The other > > modules don't conflict. > > By the way, is there already a mechanism for marking > deprecated code? Will > deprecated code be removed some time or will it pollute the > libraries until the end of time? GHC has a DEPRECATED pragma: http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#DEP RECATED-PRAGMA There really ought to be a way in Haddock to indicate deprecated interfaces too. As a rule of thumb, something that is DEPRECATED will last for at least two major releases of GHC (DEPRECATED in one major release, still available in the next, then removed). We sometimes keep things longer than this, though. There have been instances where things have been removed early too - this should only happen in libraries that are marked "experimental" though. Cheers, Simon

1 0

RE: version control and LIP
by Simon Peyton-Jones 15 Mar '04

15 Mar '04

I don't have any opinion about the relative merits of different VC systems (except selfish reluctance to learn a new one) but whatever you choose *must* work flawlessly on Windows as well as Unix. Lots of people use Haskell on Windows machines. With Gour's encouragement I managed to build GHC quite easily using MSYS, a lightweight cousin of Cygwin. When I install the MSYS developer toolkit I get CVS and ssh. I'm certain I don't get arch/darcs etc. It's not a big deal to install something else, but the something else should be guaranteed available for Windows and (strong preference) not require Cygwin. Simon | -----Original Message----- | From: libraries-bounces(a)haskell.org [mailto:libraries-bounces@haskell.org] On Behalf Of Isaac Jones | Sent: 15 March 2004 02:51 | To: Krasimir Angelov | Cc: libraries(a)haskell.org | Subject: Re: version control and LIP | | Krasimir Angelov <ka2_mail(a)yahoo.com> writes: | | > Does the arch works under Windows? | | It seems that there is some support, as you've already discovered. | Apparently, cygwin is only one out of 3 options: | | http://wiki.gnuarch.org/moin.cgi/Native_20WIN32_20Support | | I hope you can solve this problem. Perhaps this is another reason I | should move to darcs? How's darcs support in windows? | | | peace, | | isaac | _______________________________________________ | Libraries mailing list | Libraries(a)haskell.org | http://www.haskell.org/mailman/listinfo/libraries

1 0

DData in hierarchical libraries
by JP Bernardy 13 Mar '04

13 Mar '04

Dear Haskell Librairies Mailing List, Some time ago we discussed the inclusion of DData in hierachical libraries. I remember Simon Marlow proposing someone "thrashes out the details" and present the result for review. So, I've played with the code, to come up with a list of proposed changes. The rationale behind most of these changes is better consistency (so enventually the library can use overloading), simplicity, and readability. I understand that most of these are trival, mostly naming issues, and therefore, open the door to potentially endless and futile disscussions. My goal is just to pinpoint potential flaws, and have your opinions. Then, I would propose a complete revised code, unless Daan wishes to do so. Here comes the changes: * remove the Scc module Seems to be redundant with SCC in Data.Graph * foldL, foldR, foldI -> foldl, foldr, foldi to match Prelude.fold[lr] * remove find, favouring (!) and lookup. avoids incoherency with Data.List.find * rename "single" to "singleton" more explicit, more usual. * remove (Queue, Seq).append (favouring "<>") Unneeded redundancy; addtitonally, the name doesn't suit well partial application. (implicit infix meaning) >map (append q1) listOfQueues means that q1 is "prepended" to each queue. * Rename subset & friends. Similarly, they have an implicit infix meaning. >filter (subset s1) listOfSets actually keeps sets that are supersets of s1. Is there an agreed-upon (operator) name for this? * Make maps look more like collections of couples. This involves changing some functions, as such: > filter f = Map.filterWithKey (curry f) > > partition f = Map.partitionWithKey (curry f) > > member (k,a) m = > case Map.lookup k m of > Nothing -> False > Just a' -> a == a' Similarly for fold, etc. Most debatable issues: * rename (<>) to (++) * Make some types instances of Ord and Functor. Additionnaly, a root name in the hierarchy must be chosen. A simple "DData" looks good to me. Or Data.Aux is better? Cheers, JP. __________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools

7 8

RE: [Haskell] Re: RFC: DData in hierarchical libraries
by Simon Marlow 13 Mar '04

13 Mar '04

> I did not follow the Edison guidelines, nor the GHC "guidelines". > I tried different variations but in the end I sticked to the > most consistent set I could think of: > > 1) The structure (i.e. Map, Set, Queue) is always the last argument. > 2) All operations are left-biased. > > I noticed that the last point is rather important, it means that > "insert key x map" will replace the current value of "key" with "x" > if it is already present, and that "union map1 map2" will prefer > elements of "map1" instead of "map2". Just as a matter of personal preference, I find a right bias to be more intuitive. Also, if the map argument comes first in 'insert map key x', then partial application is more likely to be useful (you're more likely to be inserting several things in the same map, rather than the same thing in several maps). Cheers, Simon

5 4

RE: [Haskell] Re: RFC: DData in hierarchical libraries
by Simon Marlow 12 Mar '04

12 Mar '04

> Personally, at the moment, I like "right-bias with structure arguments > coming first" > more -- so if many others like it better too, I might be persuaded to > adapt > the implementation. +1 Simon

1 0

DData benchmark
by Daan Leijen 12 Mar '04

12 Mar '04

Simon Marlow wrote: > > However, I have never tested this with proper benchmarks. > > (now that I think > > about it, I might have tested it with improper benchmarks... I'll try > > to find on my computer when I get home). > > Great, I'd be really interested to see some numbers. I have found the benchmark code again, but unfortunately I have never tested against Data.FiniteMap... but I can adapt the sources and do some testing next week. A word of warning though, the tests are not necessarily honest, precise, and scientifically responsible. However, they may give a good intuition. I ran some common operations like "union", "member", and "fromList" on ordered and on random data and compared their wall-clock performance. All data was explicitly forced with performGC's in between to make an as honest as possible comparison. For a *real* test however, one should probably use specialized tools and specialized data sets. Here are the unscientific results for some DData structures. (ST) DData.Set: size balanced tree (PT) DData.IntSet: big-endian patricia tree ST(msec) PT(msec) relative ..timing: fromlist ordered0: 546 - 125 - 4.4 ..timing: fromlist ordered1: 531 - 125 - 4.2 (descending order) ..timing: fromlist xordered0: 78 - 125 - 0.6 (known to be ordered) ..timing: fromlist xordered1: 109 - 140 - 0.8 (known to be in reverse order) ..timing: fromlist random0: 281 - 156 - 1.8 ..timing: fromlist random1: 281 - 156 - 1.8 ..timing: fromlist random2: 609 - 359 - 1.7 ..timing: union random0 : 578 - 250 - 2.3 ..timing: union random1 : 656 - 296 - 2.2 ..timing: union random2 : 671 - 296 - 2.3 ..timing: union tangled : 281 - 125 - 2.2 ..timing: union disjoint1: 218 - 93 - 2.3 ..timing: union disjoint2: 296 - 156 - 1.9 ..timing: member0: 546 - 468 - 1.2 ..timing: member1: 484 - 484 - 1.0 ..timing: member2: 484 - 484 - 1.0 Here we can see that an IntSet is always faster than a "Set Int" except for known ordered data (= xordered) Here is an interesting bench mark for an unreleased version of DData that included "Treaps": these are trees where each node is associated with a random priority that determines the position of the node. As these are random, the tree will be balanced without doing explicit rebalancing. The functional Treap uses clever hash functions to get semi random priorities. Here is a Treap set compared to "Set Int". ST(msec) Treap(msec) relative ..timing: fromlist ordered0: 531 - 234 - 2.3 ..timing: fromlist ordered1: 531 - 203 - 2.6 ..timing: fromlist xordered0: 93 - 234 - 0.4 ..timing: fromlist xordered1: 109 - 203 - 0.5 ..timing: fromlist random0: 296 - 312 - 0.9 ..timing: fromlist random1: 281 - 312 - 0.9 ..timing: fromlist random2: 609 - 671 - 0.9 ..timing: union random0 : 578 - 593 - 1.0 ..timing: union random1 : 687 - 687 - 1.0 ..timing: union random2 : 687 - 687 - 1.0 ..timing: union tangled : 265 - 296 - 0.9 ..timing: union disjoint1: 203 - 203 - 1.0 ..timing: union disjoint2: 296 - 296 - 1.0 ..timing: member0: 546 - 468 - 1.2 ..timing: member1: 484 - 484 - 1.0 ..timing: member2: 468 - 484 - 1.0 ..timing: unions: 140 - 78 - 1.8 >From this data, I got the suspicion that every set implementation based on balanced trees will do about as good as any other. I hope to do some fresh testing against Data.FiniteMap soon, as it will be quite important to know about there absolute efficiency. All the best, Daan.

1 0

RE: [Haskell] Re: RFC: DData in hierarchical libraries
by Simon Marlow 12 Mar '04

12 Mar '04

> Am Freitag, 12. März 2004 10:34 schrieb Simon Marlow: > > [...] > > > Also, if the map argument comes first in 'insert map key > x', then partial > > application is more likely to be useful (you're more likely > to be inserting > > several things in the same map, rather than the same thing > in several maps). > > If you look at one concrete function, you probably use > insert, lookup etc. > several times with the same map argument and not with the > same key argument. > But IMO, this isn't a place where partial application is > typically used. Don't want to drag this point out too much, but I just looked through the GHC sources and there are a few places where we do something like: map (lookupFM fm) [ ... ] Cheers, Simon

1 0

RE: [Haskell] Re: RFC: DData in hierarchical libraries
by Simon Marlow 12 Mar '04

12 Mar '04

> > I did not follow the Edison guidelines, nor the GHC "guidelines". > > I tried different variations but in the end I sticked to the > > most consistent set I could think of: > > > > 1) The structure (i.e. Map, Set, Queue) is always the last argument. > > 2) All operations are left-biased. > > > > I noticed that the last point is rather important, it means that > > "insert key x map" will replace the current value of "key" with "x" > > if it is already present, and that "union map1 map2" will prefer > > elements of "map1" instead of "map2". > > Just as a matter of personal preference, I find a right bias > to be more > intuitive. Also, if the map argument comes first in 'insert > map key x', > then partial application is more likely to be useful (you're > more likely > to be inserting several things in the same map, rather than the same > thing in several maps). oops, I don't really mean "inserting several things in the same map", I mean "looking up several keys in the same map", i.e. it makes sense for the map argument to lookup to come first. Cheers, Simon

2 1

Re: [Haskell] RFC: DData in hierarchical libraries
by Christian Maeder 11 Mar '04

11 Mar '04

Hi Daan, >> Set.toAscList is not really necessary as it is the same as Set.toList. > > Not necessarily: the lists from Set.toList will be equal for equal > Set's, but may be unordered. Use "toAscList" or "toDescList" if you > want an ordered variant. That really surprises me. I think that toList must return a sorted list (to properly abstract the Set data type), and anything unsorted should only be for debugging purposes. >> The functions Set.fromAscList and Set.fromAscDistinctList should be >> marked as "unsafe" > > I think so too, although I like "unchecked" better? Good, I agree. >> Map.keySet = Set.fromDistinctAscList . Map.keys > Yes, we could do that -- but the circular dependency is terrible, and a > wrapper module > would need to look at the internal representation of Map/Set :-( I don't see the circular dependency. Map imports Set (but not vice versa?). In any case, I would prefer a wrapper (possible revealing some more "unchecked" functions). Christian

3 3

Re: [Haskell] Re: RFC: DData in hierarchical libraries
by Daan Leijen 11 Mar '04

11 Mar '04

On Thu, 11 Mar 2004 09:56:45 +0100, Johannes Waldmann <waldmann(a)imn.htwk-leipzig.de> wrote: > * nice work. I might start using it (instead of Data.FiniteMap) > just because the function names look better :-) Thanks. > * argument ordering: > the existing Data.FiniteMap mostly has > f :: FiniteMap -> ... -> FiniteMap > while the proposal uses > f :: ... -> FiniteMap -> FiniteMap > > I think the Edison guidelines are quite nice: > http://www.haskell.org/ghc/docs/edison/users004.html#toc10 > > Did you follow them? What exceptions? I did not follow the Edison guidelines, nor the GHC "guidelines". I tried different variations but in the end I sticked to the most consistent set I could think of: 1) The structure (i.e. Map, Set, Queue) is always the last argument. 2) All operations are left-biased. I noticed that the last point is rather important, it means that "insert key x map" will replace the current value of "key" with "x" if it is already present, and that "union map1 map2" will prefer elements of "map1" instead of "map2". Note that the GHC FiniteMap implementation is ambigious about its bias and the bias is documented per function (note: a thing that may bite us in particular is that GHC "plusFM" is right-biased and can thus not be replaced by DData "union" with a search-and-replace.) However, I do not have a strong opinion about this and maybe the Edison guide lines are better. However, I do believe that a "bias" rule like (2) is very important when you are using the library. A strong rule like (1) is maybe less convenient for fulltime users (especially in the context of partial applications), but much easier for sporadic users. > * types: some functions are not declared at their most > general type (I checked by commenting out the decl. and asking ghci) This was by purpose, for example: > difference :: forall a1 k a. > (Ord k) => > Map k a1 -> Map k a -> Map k a1 It is kind of strange to take the difference between to maps with different elements, so I thought it better to disallow that situation. However, it is a bit 1984 to disallow it, and I may be wrong here. All the best, Daan.

2 1