August 2005 - Libraries

Re: argument ordering (was: Re: Priority Queues, or lack thereof)
by Okasaki, C. DR EECS 19 Aug '05

19 Aug '05

Malcolm Wallace wrote: >> This style supports multiple operations nicely, especially with combined >> with the $ operator. > > But note that the version with $ is actually longer than the one > with nested parens! Only because I put in the third $, which wasn't necessary, and which most people using this style would probably omit. Without that $, they're the same length. And of course I could make the first one shorter by leaving out some of the whitespace, but I would never recommend that. Character counts are mostly irrelevant anyway -- what matters is ease of reading. To my eye, the version with the $ is slightly easier in this case, but opinions can certainly vary. I think the $ style becomes much easier to read as you (1) add more operations, and (2) start mixing operations (eg, some inserts and some deletes). For example, compare insert 1 $ delete 2 $ delete 3 $ insert 4 $ delete 5 someset and insert (delete (delete (insert (delete someset 5) 4) 3) 2) 1 In the latter style, how easy is it to tell whether 3 is being inserted or deleted? In the former style, it is obvious that 3 is being deleted. Of course, I will freely admit that such examples are fairly rare in real programs. > And where the operands are not statically known, > the different orderings do simply come down to > foldl/foldr preference: > > insert 1 $ insert 2 $ insert 3 $ someSet > == foldr insert someSet [1,2,3] > > insert (insert (insert someSet 3) 2) 1 > == foldl insert someSet [3,2,1] > > In some sense the foldl variant is more 'obvious' about the order in > which elements are actually inserted. Yes, I agree that the order of operations in the $ style is somewhat counter-intuitive (in exactly the same way that "foo . bar . baz" is). This rarely seems to be a problem in practice, however. The most common examples where I've seen this style used are things like initializing the dictionary of an interpreter with the "built-ins", in which case you know that none of the keys overlap so the order doesn't matter. -- Chris

1 0

Re: argument ordering (was: Re: Priority Queues, or lack thereof)
by Okasaki, C. DR EECS 19 Aug '05

19 Aug '05

In response to questions about why the convention of putting the data structure as the last argument... This style supports multiple operations nicely, especially with combined with the $ operator. For example, to insert 3 elements into a set, you can say insert 1 $ insert 2 $ insert 3 $ someSet (the last $ is optional). With the other argument ordering, you would say insert (insert (insert someSet 3) 2) 1 -- Chris

3 2

RE: cabal design
by Simon Peyton-Jones 19 Aug '05

19 Aug '05

| First of all I want to thank Isaac Jones for his work on Cabal. | | There are a few issues I would like to raise. Seconded -- Isaac you are doing a great job. As are lots of other contributors. One rather vexed question is the issue of whether a single program can contain two modules with the same name. Currently that is absolutely ruled out, and as a result packages are fundamentally non-modular: every package must use a distinct space in the global namespace. Simon Marlow and I have gradually become convinced that we have to fix this, and the only sensible way to fix it is to relax the language design so that a module name must be unique within its package (only) That means that module A.B.C could exist *both* in package P1 and in P2. And both packages could be linked into the same program. Some kind of 'grafting' or 'mounting' scheme would be needed to bring a package into the package namespace. One might say ghc -c Foo.hs -package gtk-2.3 Graphics.GTK to mount the gtk-2.3 package at Graphics.GTK in the name space. Outside the package one would need to import Graphics.GTK.M, but *within* the package one just imports M. That way the entire package can be mounted elsewhere in the namespace, if desired, without needing to change or recompile the package at all. The exact details of the mounting scheme, and whether it is done at build time, at install time, or at compilation time, or all of the above, are open to debate. We don't have a very fixed view. However, the fundamental thing GHC needs to do is to include the package name into the names of entities the package defines. That means that when compiling a module M you must say what package it is part of: ghc -C M.hs -package-name my-package-2.3 Then M.o will contain symbols like "my-package-2.3.M.f" etc. In effect, the "original name" of a function f in module M of package P is <P,M,f>. The purpose of this message is a) To advertise our willingness to implement this in GHC b) To ask whether doing so would be welcome, and if so to invite the Cabal afficionados to come up with a specific design for the programmer's interface c) To ask what the Hugs story might be. That is, are any of the Hugs folk willing to implement the necessary? The thing about (c) is that it'd be a Big Pity if new-style packages couldn't be used with Hugs because they don't obey the unique-module constraint. Ditto nhc. Simon

4 3

Priority Queues, or lack thereof
by Sebastian Sylvan 18 Aug '05

18 Aug '05

I've been puzzled by the lack of a priority queue implementation in the hierarchical libraries for some time. Sure, you could use a Data.Map as a priority queue, but something about having to pay O(log n) to find the smallest element bugs me. So, I decided to implement my own priority queue with optimal asymptotic time complexity. That is: insert : O(1) findMin : O(1) meld : O(1) deleteMin : O(log n) It's based heavily on the strategy detailed in the paper "Optimal Purely Functional Priority Queues" by Gerth StØlting Brodal and Chris Okasaki. This is asymptotically better than other, simpler, data structures, but the "constant factor" is likely very high (I haven't done any sort of serious benchmarking). I figured that if you have a small data set, the speed isn't going to matter much anyway, and if you have a large enough data set the asymptotically better data structure is faster. Anyway This was just something I threw together when I had some spare time. There may be misstakes in there, there's probably tons of room for improvement, but at least it's a priority queue! Download at: http://www.dtek.chalmers.se/~sylvan/PriorityQueue/ ----------------------------------------------------------------------------------------------------------- File Description ----------------------------------------------------------------------------------------------------------- PrimPQ.hs The internal workings of the skewed binomial tree PriorityQueue.hs The main priority queue module PriorityQueueTests.hs Some quickcheck properties ----------------------------------------------------------------------------------------------------------- /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

3 4

RE: cabal design
by Simon Peyton-Jones 17 Aug '05

17 Aug '05

| The thing that really annoys people is when some package they're using | internally uses some random utility module eg "C2HS.hs" then they cannot | use that same module name in their program. This is the case even when | the functions from that little utility module is not exposed in the | interface of the package. Yes -- but remember that what is exported from one package may become an internal detail of another. | detail but it exposed the cairo api directly to user programs. Now I | believe that with the ELF linking format it is possible to set things up | such that if you link with Gtk+ (which links with libpng) you can still | use symbols in your top level program that are exported by libpng and | you will not get linker errors. Perhaps. But it's leans more on linker cunning-ness, which is often not very portable across platforms, in my limited experience. And the simple expedient of adding the package name to the "original name" does the job once and for all. So why not use the simple expedient, that relies on no linker magic, and has stronger properties than what you suggest? Of course the programmer never sees this! He just sets up a module name space in which when he says "import A.B.C" it's clear which module A.B.C he means. Simon

1 0

RE: cabal design
by Simon Peyton-Jones 17 Aug '05

17 Aug '05

| > Some kind of 'grafting' or 'mounting' scheme would be needed to bring a | > package into the package namespace. | | I disagree that this necessarily mandates a grafting or mounting | scheme. Whilst it might be useful, even desirable, it is a separate | question. I agree that it's a separate question. Hence (b) of my message. If you want to import module A from package P and import module A from package Q into a single module M of a program, you can always do this: make a new module AP, that imports A and re-exports it all; compile AP with package P visible and Q hidden ditto for AQ make M say "import AP; import AQ" That's essentially what you suggested. Of course it means that any "import A.B.C" has to be understood wrt a namespace that may change from module to module. I guess that one merit of the grafting scheme is that you could make a single package-grafting configuration that would apply to the whole of a program, so that within that program modules were consistently and uniquely named. But yes it's a separate question. Simon

1 0

AVL library updated
by Adrian Hey 16 Aug '05

16 Aug '05

Hello, I've just updated the AVL library to 2.2: http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/ This version has.. * A few more set manipulation functions. * A kind of cheap but extremely limited zipper which uses node indexing instead of building a path structure on the heap. * Some functions which may end up not modifying a tree (e.g. deletion of non-existing element) now return the original tree (rather than an identical copy with nodes on the search path duplicated). Regards -- Adrian Hey

1 0

Foreign language parsers
by Dominic Fox 15 Aug '05

15 Aug '05

I'm trying to collate a list of currently extant Haskell projects that include parsers for foreign languages such as PHP and C. To this end, I've created a wiki page at http://haskell.org/hawiki/ParsingForeignLanguagesInHaskell. Has anyone looked at positioning foreign language parsing modules in the standard libs, or specifying a common framework or contract for such modules? Dominic Fox -- Perhaps (but not likely) I may be still a whizz at ordinary language and you mishear things. -- Geoffrey Hill, Discourse: For Stanley Rosen

3 2

Gtk2Hs 0.9.9 released
by Axel Simon 15 Aug '05

15 Aug '05

Dear all, A new release for Gtk2Hs, namely version 0.9.9 is now available. This is a bug-fix release which is meant to fix various issues in the 0.9.8 release. The tarball is available from at Sourceforge. The md5 checksum is 3276545190248d40c683cd42f51a1b6e. Changes since 0.9.8: * many documentation fixes * documentation builds with the new haddock 0.7 * fixed an intolerant parser in c2hs, the C header-file scanner * fixed segfaults when disconnecting signal handlers * fixed segfaults in signals that pass TextIters * add Pixmap from Gdk (not gtk_pixmap which is deprecated) * added ChildAttributes to all containers * minor fixes to our Makefile Please report any problems with this release to our emailing list, gtk2hs-users(a)lists.sourceforge.net . Axel (on behalf of the Gtk2Hs team).

1 0

RE: Extending the dependency syntax
by Simon Marlow 12 Aug '05

12 Aug '05

On 11 August 2005 04:38, Isaac Jones wrote: > "Simon Marlow" <simonmar(a)microsoft.com> writes: > > (snip) >> build-depends: >> --enable-ghc? ( >> ghc>=6.4 ? [ghc64] | >> ghc>=5.04 ? [ghc-old]) >> | --enable-hugs? [hugs] >> | true ? true, -- other compilers are allowed >> --enable-debug? (HUnit-1.0, [debug]) | true? [release] >> --enable-gnome? ( >> libglade >= 2, >> gtksourceview >= 0.6, >> gconf >= 2, [gnome] ), >> --enable-mozilla? ( mozilla >= 1.4, [mozilla] ), >> --enable-doc? ( haddock >= 0.6 ) > > What happens now with the issue that Duncan mentioned, where the built > system picks up configuration information from the build / configure > environment that's different from the user's environment? It could > either pick up too much or too little. For "too little" we could use > the --enable flags to override the detection mechanism, and maybe a > --disable-all-detection mechanism similar to the -fhide-all-packages > mechanism would be useful. One problem is that --enable-foo doesn't > necessarily exist for optional dependencies. The example I wrote above is deterministic: it doesn't pick up dependencies from the environment and change its configuration automatically (this isn't accidental). I'm going with the derministic-dependencies-by-default approach, which seems better. It's possible to write non-deterministic dependencies with this scheme. Perhaps that's a problem. A few messages back I mentioned that we might have an --auto-enable switch to get back the handy non-deterministic behaviour. I can't immediately see how to make it work (eg. we don't want --enable-debug enabled automatically if HUnit is available). But I don't consider the lack of --auto-enable to be a big deal - good OS packaging systems like Gentoo provide this anway. > Another point: The dependency syntax you show mixes packages and > pseudo-packages like GHC, alex, etc... I don't think we should use the > same syntax / field for this, since in reality, they have separate > namespaces. In fact you might be insane enough to want to talk about > them separately: maybe you have the haxml library installed, but not > the haxml toolchain... maybe you want the ghc executable, but not the > ghc package... Ok, but separating these dependencies will mean that you can't combine them. eg. you can say "if I have GHC 6.4 and wxHaskell then ... else ...". And separating them seems to make the system more complicated rather than less... but I don't feel that strongly. > We used to have a distinction between depends and build-depends, but > we threw that away, I think because we weren't using the > non-build-depends stuff at all... I note that having separate depends > vs build-depends fields doesn't actually fix the above problems. BTW, > are you suggesting that we change the meaning of depends and really > adding a build-depends field? I'm just suggesting extending the syntax of build-depends in a backwards-compatible way. > There are at least four kinds of simple dependencies, not taking into > account configurations: > > 1) build-depending on packages - which is what depends: means now. > This is always a build-time dependency. > > 2) build-depending on executables like GHC - that the simple build > infrastructure knows about / needs. It would also be nice if we > had a more sensible way of adding --with-foo= flags, > extra-foo-opts, and configure-time detection for stuff in this > category. I put some thought into the --with-foo thing too, and Dimitry's suggestion, but again I think we should deal with one thing at a time. > 3) run-time depending on executables like gpg, gnome, etc. These are > likely to be executables that Simple has never heard of before. > > 4) build-depending on stuff that the simple build infrastructure > doesn't know about. This may not be very common, but folks not > using Distribution.Simple may want to use this field to express > dependencies too, so it would be nice if we could express > build-time dependencies on non-package tools which we don't already > know about. > > In reality, there are even more kinds :( > > The original request, I believe, was for better support of > tool-depends mainly 2, but perhaps 3 and 4 are also important? 3 is a > very common situation in Debian, and 4 is important for completeness > for systems that don't want to use Distribution.Simple, and maybe for > stuff like libglade? My feeling is that Cabal's build-depends should deal with dependencies that it needs to know about in order to build, install and register the package. Everything else should be pushed into the OS-level packager. > I have been thinking that Cabal should worry about 1 and 2 only, and > let the OS package system worry about 3 and 4, bingo :) > but Duncan's > requirements open the door to 3, and it's not going to be obvious to > people that they can't talk about tools that Simple doesn't know > about. In fact, it snuck into the above example. How the heck does > Distribution.Simple know what version of Mozilla is installed? Maybe > you didn't really mean that? > > But I do think that if we're overhauling the dependency syntax, we > should think about all kinds of dependencies so we don't paint > ourselves into a corner. 1 is the only kind that currently has a > flexible infrastructure; 2 is done now, but can be sloppy sometimes; > as I haven't always added --with-foo= flags when we need them and > such. > > But how can we be flexible about 3 and 4? Are they important? ... > Am I being too much of a perfectionist in trying to be complete here? > Should we really just allow 1 and 2 and punt on the rest? Is it > important to distinguish between 1 and 2? They're definitely important when building an OS package from a Cabal package, and we'd like to automate this process as much as possible. Therefore it might be useful to have a consistent way to specify hints to the OS packager, extra dependencies and so on. This might take the form of a naming scheme for OS-packaging hint files, or extra sections in the .cabal file. I vote for punting on (3) and (4), but allowing hints to be provided for passing these dependencies to the OS packager. > Also, I'm not sure we're really doing gentoo a favor by making the > dependency syntax so complex. I think Duncan wanted to be able to > automatically parse the cabal file and figure out the dependencies for > alex and such, but now he's faced with: > > --enable-mozilla? ( mozilla >= 1.4, [mozilla] ), This one's easy: "mozilla? (>=mozilla-1.4)" (if I got the ebuild syntax right). The GHC section reduces to >=ghc-5.04. The --enable-debug section reduces to "debug? ( HUnit-1.0 )", or goes away entirely if you don't care about debugging in the OS package. Basically, the existing build-depends syntax is a subset of what Gentoo allows, and I'm proposing a superset (modulo the lack of depdencies on C libraries etc.). The .cabal->.ebuild generator would have to fail on dependencies that it didn't understand - I don't think this is a huge problem, since complex dependencies will be rare, and there will be a way for the Cabal packager to provide hints to the .cabal->.ebuild generator. I don't think we should restrict ourselves to the lowest common denominator of Gentoo, Debian, FreeBSD, RPM, etc. Duncan, does this sound plausible? Cheers, Simon

2 1