- Libraries - Haskell.org

Re: Heirarchical name space allocation /Trees
by Okasaki, C. DR EECS 02 Apr '04

02 Apr '04

> Who doesn't get at least a bit uneasy when looking at all the redundancy, > in e.g. Edison's code? Okasaki has written some generic functions, but > they have to be renamed manually in each module. All for the sake of > efficiency! Bertrand Meyer did not propose to handle this via inheritance > without ensuring that the compiler would eliminate all the indirections. > And that was in 1985! I may be misunderstanding what you are saying here, but I think you are complaining that Edison has a lot of redundancy because it doesn't use default definitions. And I think you are attributing that avoidance of default definitions to a concern about avoiding indirections. But indirections and "efficiency" (in the sense I think you mean) have nothing to do with it! The redundancy you are referring to comes from two sources. First is the desire for Edison to support *both* the class-based style and the module-based style of accessing the data structures. As other posts in this thread have shown, both styles have their strong supporters, and I didn't see any reason that the library should dictate one style over the other. Because the module-based style doesn't support inheritance, you have to put in explicit definitions for every operation, even if many of those definitions are one-liners that refer to generic functions. The second source of redundancy is that default definitions are largely useless for this kind of library. The problem is that there is rarely *one* generic function that makes sense as the default. Instead, there are often two or three or more functions that are all equally good candidates to be the default. So which one do you choose? If there is one that is appropriate, say, 80% of the time, then sure go ahead and make that one the default. But if there are three, and each is appropriate about 33% of the time, then I think it is more clear not to have a default, and have every implementation state explicitly which of the "defaults" it is using. -- Chris

1 0

RE: State of DData
by Simon Marlow 02 Apr '04

02 Apr '04

> > Arguably then, anything which is an instance of Monad > should be a monad. > > I would certainly argue strongly for that. > > If it ain't true, then small, irrelevant changes in a piece > of code could > break. For example, is it safe to make this change: > > do > f y > ==> > do > x <- f y > return x > > I'd hope it would be. (And the change might be useful if I > want to insert a check or a debugging printf in the code.) I'm afraid it isn't true that all instances of Monad respect the monad laws, due to our old friend seq. See: http://www.haskell.org/pipermail/haskell/2002-May/009622.html I don't want this discussion to get out of hand. The only point I'm making here is that the Haskell definition doesn't *require* that every instance of (==) be equality, in the same way that it doesn't *require* that all Monad instances are monads, and all '+'s are additions etc. Libraries might rely on properties of these methods, but as far as is practical those assumptions should be documented. Cheers, Simon

4 3

RE: Heirarchical name space allocation
by Graham Klyne 02 Apr '04

02 Apr '04

At 10:19 30/03/04 +0100, Simon Marlow wrote: > > > Who's in charge of allocating names in the hierarchical > > modules for publicly released libraries these days? > > > > This page lists (some) allocated names.. > > http://www.haskell.org/~simonmar/libraries/layout.html > > > > But I can think of a few that aren't listed there. > > What's the policy? > > Is there a master reference or register somewhere? > >At one stage we thought that having a single global registry for names >was the way to go. Now I think that a free-for-all, with good package >management tools, is probably better. > >Names and hierarchy locations will still be discussed on this list, but >anyone is free to publish a library using any names in the hierarchy >they please. If there is overlap, then the compiler should prevent you >from using two overlapping packages at the same time. In fact, there's >one good reason for allowing overlap: versioning of libraries. > >Of course, if your library uses names that are consistent with the >general policy, then there's a greater chance that your library will be >included in future "collections" of libraries, bundled with compilers, >and so on. The idea is that community self-organisation replaces strict >central registration of library names. I think this is an improvement, >but perhaps it's a cop out. What do others think? I like it. It might be appropriate for designers to document module names they use in the wiki? #g -- PS: the "provisional registry" of "Registration procedures for message header fields" [1] is almost a similar free-for-all. The general idea is to give developers a pretty free hand in choosing names, but provide a common listing for the purposes of coordinating activities. [1] http://www.ietf.org/internet-drafts/draft-klyne-msghdr-registry-07.txt ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: Heirarchical name space allocation /Trees
by Simon Peyton-Jones 02 Apr '04

02 Apr '04

| specific optimisations). Of course anyone may disagree. (Btw, | documenting all the really innovative stuff in official publications will | take some time, so if you want to wait...). Robert, let me encourage you to do this writing. Debates on the Haskell libraries list have a narrow audience; a paper has a far wider audience. Furthermore, the process of writing a paper often has an incredibly beneficial effect on the ideas being described. And the paper will still be read long after the implementations it describes have turned to dust -- papers infect people's brains which is the most powerful form of software propagation of all. The Haskell workshop might be a good venue. Simon

1 0

RE: Heirarchical name space allocation
by Simon Marlow 31 Mar '04

31 Mar '04

> Who's in charge of allocating names in the hierarchical > modules for publicly released libraries these days? > > This page lists (some) allocated names.. > http://www.haskell.org/~simonmar/libraries/layout.html > > But I can think of a few that aren't listed there. > What's the policy? > Is there a master reference or register somewhere? At one stage we thought that having a single global registry for names was the way to go. Now I think that a free-for-all, with good package management tools, is probably better. Names and hierarchy locations will still be discussed on this list, but anyone is free to publish a library using any names in the hierarchy they please. If there is overlap, then the compiler should prevent you from using two overlapping packages at the same time. In fact, there's one good reason for allowing overlap: versioning of libraries. Of course, if your library uses names that are consistent with the general policy, then there's a greater chance that your library will be included in future "collections" of libraries, bundled with compilers, and so on. The idea is that community self-organisation replaces strict central registration of library names. I think this is an improvement, but perhaps it's a cop out. What do others think? Cheers, Simon

4 3

RE: State of DData
by Simon Marlow 31 Mar '04

31 Mar '04

> > > In my opinion, even "advanced users" should adhere to The > > > Haskell Report which says that (==) means equality. > > > > Where does the report say that? As far as I can see, the > closest quote is > > this: > > > > The Eq class provides equality (==) and inequality (/=) methods. > > > > (section 6.3.1). The report doesn't explicitly say > anywhere that any > > assumptions about the properties of == are ever made. > > If the Report calles (==) an equality method then (==) should > implement equality for every Eq instance. Arguably then, anything which is an instance of Monad should be a monad. And '+' should be addition. etc. etc. Haskell doesn't require any of these to be true, and similarly it doesn't require that every instance of '==' is equality. Cheers, Simon

4 3

RE: Heirarchical name space allocation
by Simon Marlow 30 Mar '04

30 Mar '04

> Have you given any thought to adding some security to go along with > library versioning? I'm thinking of something like the C# > repository, > where the version of the library you compile against has a digital > signature, and the signature is embedded in the app. The point is to > prevent an attack where someone substitutes another library, with the > same version information and public interface, and hijacks your code. I haven't thought about it, but my guess is that in the absence of any other security infrastructure it wouldn't be of much use. Could you outline some scenarios in which you think this would be helpful? Cheers, Simon

1 0

Heirarchical name space allocation
by Adrian Hey 30 Mar '04

30 Mar '04

Hello, Who's in charge of allocating names in the hierarchical modules for publicly released libraries these days? This page lists (some) allocated names.. http://www.haskell.org/~simonmar/libraries/layout.html But I can think of a few that aren't listed there. What's the policy? Is there a master reference or register somewhere? Regards -- Adrian Hey

1 0

Bug in the proof of Data.FiniteMap and DData.Map
by Robert Will 29 Mar '04

29 Mar '04

hi, both of the data structures are based on Adams' balancing algorithm which contains a bug -- at least in its proof. (Perhaps it is correct, but I don't know anyone that knows if.) Instead of fixing the bug I have re-derived the algorithm from the invariant together with a (now hopefully correct) proof. The new algorithm is contained in Dessy: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/ more specifically in the file: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/WeightedTrees.hs The derivation, proof (and hint to Adam's bug) are in: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/democratic/sequence.hs (The so-called hedge-union, -intersection, and -difference is also implemented: function 'x_merge_width' does all three: http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/Dessy.hs ) A paper which presents the new (much simpler) algorithm and its proof putting it in scientific context is in preparation. Users that prefer proven algorithms over tested ones are free to use my implementation instead of the existing ones. (At moment, there is no proven and tested implementation. Of course this will change soon.) As for the maintenance of Data.FiniteMap and DData.Map, I don't know whether it is worth "fixing" the implementations or one would better replace them by a completely new design. Anyway, algorithms have no copyright and everyone is free to use the new "weight-balancer according to Will" to implement his own data structures. Oh, by the way, some of the other balancers in Dessy (or DData) might be more efficient than weight-based balancing anyway, I'll make some measurements later this year. good time, Bob

4 6

Patch for System.Console.GetOpt to align multi-line option descriptions
by Martin Sjögren 27 Mar '04

27 Mar '04

As the subject says, the attached patch will align multi-line option descriptions. I find this very useful since I typically write long option descriptions and having too long lines and having descriptions that muddle up the option columns suck equally bad in my opinion. I hope others find it useful too. Cheers, Martin Sjögren

2 1