January 2006 - Libraries

using cabal? add your package to the list!
by Isaac Jones 15 Jan '06

15 Jan '06

I started a list of packages using cabal (including those uplaoded to Hackage). Please either upload your packages to hackage, or add it here. I want this list so that I can try to figure out things like how much a given modification to Cabal will break stuff: http://hackage.haskell.org/trac/hackage/wiki/CabalPackages To add your package to the list, hit "Edit Page" at the bottom of the page. Feel free to make the page into a table, add links for the packages already there, reorganize, etc. peace, isaac

1 0

Cabal compatibility redeux
by Robert Dockins 09 Jan '06

09 Jan '06

I'd just like to reseruct the conversation from here (http://www.haskell.org//pipermail/libraries/2005-December/004692.html) for a quick moment if I might. At the time I wrote: >>>> This would greatly simplify the Distribution.Simple.UserHooks >>>> structure bringing it from 34 fields to 14 fields, or so. >>>> >>>> Downsides: Making pre and post hooks would now be slightly harder, and >>>> it would break existing hooks-using code. >>> >>> I just want to mention that these kind of changes represent represent a >>> VERY big problem. I discussed that issue at some length in an email I >>> intended to send to this list very recently, but it seems to have gotten >>> lost. >> >> Are you sure they represent a very big problem in practice and not >> just in theory? > > [snip] > > Well, obviously it isn't a practical problem yet. If it was we'd have > people screaming about it on the lists. I would now like to add to the theoretical arguments I made then the evidence that the HSQL driver package for MySQL uses the user hooks of Cabal and I have just experienced a case of Cabal version skew breaking a build system, because this package will not build for me using Cabal 1.1.3. I am unsure at the moment if this is because my Cabal is too new or too old, and I now face the prospect of 1) hacking on the build system to match my cabal, 2) trying random cabal upgrades/downgrades or 3) pinging the package maintainers to figure out how to build this package. Rob Dockins

2 1

Re: Left-bias and non-structural equality.
by Jean-Philippe Bernardy 08 Jan '06

08 Jan '06

On 1/8/06, Adrian Hey <ahey(a)iee.org> wrote: > On thing that occurred to me was that calling the AVL tree based sets > "Set" might be the wrong thing to do anyway. If we want to allow for > future implementations to be based on other data structures then we > probably shouldn't usurp the name "Set", but rather call it SetAVL or > something. (To allow a consistent naming scheme to be used if someone > ever produces SetRedBlack say). Both SetAVL and SetRedBlack would > be instances of the "Set" type constructor class (presumably). > > So maybe the thing to do would be to keep Data.Set (with biasing specified) > for the present, but just put a pointer there in the Haddock to a new > module Data.SetAVL (which does not specify biasing). This scheme would > also allow the current Set implementation to be retained if it turns > out to have some advantages over AVL (seems a bit rash to discard it > completely anyway), but it would be called Data.SetAdams (or something..) As I was writing to Adrian this morning, that's exactly what I am proposing. :) To clarify things, I've put up some more explanations on the wiki: http://haskell.org/hawiki/StandardCollectionLibraries Cheers, JP.

2 1

Left-bias and non-structural equality.
by Jean-Philippe Bernardy 08 Jan '06

08 Jan '06

On 1/2/06, Adrian Hey <ahey(a)iee.org> wrote: > On Sunday 01 Jan 2006 3:28 pm, Jean-Philippe Bernardy wrote: > > Yes, union suffers from the same problem; both in Set and Map as well. > > The testing code can now detect problems of left-biasing in presence > > of non-structural equality. (That's what I wanted to implement before > > applying the fix). > > Actually I was wondering whether or not the term "left-biasing" was > particularly useful. It could be misleading for some functions. > > For example.. > -- | /O(n*log n)/. Create a set from a list of elements. > fromList :: Ord a => [a] -> Set a > fromList xs = foldlStrict ins empty xs > where ins t x = insert x t > > My interpretation of left biasing would be that if the input list contains > multiple occurences of "equal" values then the first occurence is the one > which is inserted in the Set and the rest are discarded. But AFAICS the > this is not the case with the current Data.Set implementation (or with the > clone I just produced). Both are right biased (at least according to my > intuitive understanding of the term). There is a "definition" of left-bias here: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Set.html -- Note that the implementation is /left-biased/ -- the elements of a -- first argument are always perferred to the second, for example in -- 'union' or 'insert'. Of course, left-biasing can only be observed -- when equality is an equivalence relation instead of structural -- equality. ...which says nothing about biasing inside a list. > BTW, I think I would prefer the default behaviour of insert > to be to retain existing elements because this allows the > optimisation of not updating the data structure representing > the set at all (which should help keep heap burn rate down). > But I guess this is in effect assuming equality implies > structural equality so others may not like it. Sigh... The biggest problem with this is that Map.insert changes the value corresponding to the inserted key inside the map, and since it is observable even with structural equality, you can be certain that quite some people rely on that behaviour. Making Set do the opposite is rather counter-intuitive. In summary, left-biasing is important even in with well-behaved equality, in the case of Maps. > <whine> > I really wish this whole issue of how to properly deal with "things > that are equal but may still be different somehow" would just go > away :-) It's hard to be precise about what choice you've made, and > whatever choice you do make usually seems arbitrary. Even when > it doesn't make any semantic difference, the choice you make may > well have an observable effect on space and time behavior. > </whine> I really wish it too. BTW, the fact that Map and Sets had many problems with non-structural equality and biasing is quite revealing that this is not such a big problem in practice. (For the record I had to fix union and intersection in Set, and union*, intersection*, differenceWith* and insertWith* in Map) Non structural equality seemed not to have many proponents the last time I discussed it. (See http://www.haskell.org//pipermail/libraries/2004-March/001833.html and following messages) Yet, since haskell doesn't rule it out, I guess we have to provide a consitent behaviour, if only to minimize the user's suprise. On the other hand, I wish to deprecate all functions that implicitly promote non-structural Equality, in order not to lead the unsuspecting user to a dangerous path. Interestingly enough, this brings us back to the origin of this thread, namely insertWithKey. Changing it to follow the left-bias rule, it now doesn't depend on the keys present in the map; and hence becomes deprecated, for the reason David mentioned. Cheers, JP.

6 20

how to contact me (sorry)
by Isaac Jones 07 Jan '06

07 Jan '06

Sorry for sending this to the whole list, but I correspond with a lot of you, so I thought I should mention what's up. In case anyone has been trying to contact me, I thought I'd mention that my syntaxpolice email has been down for a while now, though it will be coming back up soon. In the meantime, please contact me at ijones(a)debian.org :) peace, isaac

1 0

Re: Left-bias and non-structural equality.
by Okasaki, C. DR EECS 05 Jan '06

05 Jan '06

I've been having this argument with people for close to 10 years now. There are two similar but separate notions: equality and equivalence, where equality means "equivalent in all contexts" and equivalence means "equal in some contexts but not necessarily in others". (I'll leave it to others to give the base case of this recursive definition. :-) The problem is that Haskell has only a single Eq class, and it seems safe to assume that that is not going to change anytime soon. So which should it be, equality or equivalence? Many people want it to be equality, for reasons of mathematical purity, while many others want it to be equivalence, because it is so bloody useful. As I see it, if you are going to restrict yourself to only one of the two, equivalence is the better choice. Why? Because code designed to work with equivalence will still work if you happen to give it an equality relation, but code designed to work with equality can break if you happen to give it an equivalence relation. Another issue is that many *many* data structures can inherently only provide equivalence. The essential difference between equality and equivalence has to do with being able to substitute "equals for equals". For most data structures that have internal invariants, you can freely substitute equals for equals *outside* the abstraction boundary, but not *inside* the abstraction boundary. For example, you can't replace the left subtree of a balance binary search tree with another subtree with the same elements but a different shape, and expect the whole tree to still be balanced. The only way around this problem is to have an extra "wrapper" type and explicitly wrap/unwrap your data every time it crosses the abstraction boundary. The way I dealt with this in Edison was to provide two versions of many operations, such as insert and insertWith, where insert is designed with equality in mind and insertWith is designed with equivalence in mind. I have some sympathy for the argument that this pollutes the API, but in a way that is easy to understand if you understand the equality/equivalence issue. You might think that assuming equality will simplify the API, but your users would still need to understand the equality/equivalence issue or they are going to accidentally give you equivalence relations. -- Chris

1 0

Data.Version.parseVersion
by Einar Karttunen 04 Jan '06

04 Jan '06

Hello What is the correct way to use Data.Version.parseVersion? It seems to start with the "wrong" result and the last one is the intended one. e.g. "1.2.3" is parsed as: [(Version {versionBranch = [1], versionTags = []},".2.3"), (Version {versionBranch = [1,2], versionTags = []},".3"), (Version {versionBranch = [1,2,3], versionTags = []},"")] This is different from the usual read instances. Is the behaviour intended? Should I just use that as: filter (null . snd) $ readP_to_S parseVersion "1.2.3" :: [(Version,String)] - Einar Karttunen

2 1

Re: [Haskell-cafe] strange stack overflow with Data.Map
by David Roundy 04 Jan '06

04 Jan '06

On Thu, Dec 29, 2005 at 01:42:29PM +0100, Christian Maeder wrote: > David Roundy wrote: > >>stats elems = foldl add_elem Map.empty elems > >>add_elem m x = Map.insertWith (+) x 1 m > > > >>main = print $ stats $ take 1000000 $ repeat 1 > > > >This program has a space leak and runs out of stack space. I'm guessing > >that I'm being bit here by an unnatural amount of laziness in > >Map.insertWith, but I can't see how to fix this. :( I'm sure it's > >something elementary... > > try: > > stats = foldl' add_elem Map.empty > add_elem m x = myinsertWith (+) x 1 m > > myinsertWith f k v m = > case Map.lookup k m of > Nothing -> Map.insert k v m > Just w -> let r = f v w in r `seq` Map.insert k r m Thanks, that does it! I had tried something like that, but without the foldl', and had tried foldl', but without the myinsertWith. The reason I didn't spend much time using this implementation is that for large maps, it will take twice as long as Map.insertWith, so I assumed (incorrectly) that Map.insertWith should be written so that it behaves in a non-leaky manner. Should the Map modules have an additional Map.insertWith' that behaves strictly, or might it be the case that you always want strict behavior when using insertWith? -- David Roundy http://www.darcs.net

9 19

Cabal and Hooks?
by Dimitry Golubovsky 03 Jan '06

03 Jan '06

I am developing an extension to HSFFIG to create Haskell packages out of C header files. Before I start reinwenting the wheel, I would like to reuse as much of Cabal functionality as possible. I am trying to figure out whether the following can be done with user hooks using Distribution.Smple. 1. I need to extend the Setup command line syntax with custom options (esp. Setup configure). For example, I need to specify locations for the imported C headers and libraries they relate to. The package description file does not seem to be a good place for them because on different systems these locations may be totally arbitrary. Results of parsing of those options must be visible to subsequent package building phases. These options also must appear in the help message. 2. I need to override the build process completely. The package build process is pretty much straightforward [1], but differs from the "standard" ghc --make: module dependencies are pregenerated by running GHC -M; all source files are compiled with the split_objs option one by one (when compiling tens/hundreds of modules with --make, memory used by GHC exceeds reasonable limits). Does the buildHook do the job (looks like it does, but just to make sure...)? 2a Another problem with build/install is that while the names of exposed-modules are known in advance (basically there is only one module to expose which re-exports the rest), names of other-modules are only known after the build completes. The source splitter may leave tens or even hundreds of separate modules (see HSFFIG tutorial: for example, a single module is created for every structure/union). It is impossible to specify them all in the package description file. Provided that the location of those modules is known, is there any way to state in the package description file that all modules at the given location should be "other-modules" (kind of a regexp)? I see the possibility to use Distribution.Make as a last resort. However it delegates too much functionality to the make and configure utilities; I would be happy to have more Cabal on my side ;) Thanks for any ideas. --------------- [1] http://haskell.org/hawiki/HsffigLinkageOptimization -- Dimitry Golubovsky Anywhere on the Web

1 0

Data.Set clone available
by Adrian Hey 01 Jan '06

01 Jan '06

Hello folks, I've put and AVL tree based clone of Data.Set here.. http://homepages.nildram.co.uk/~ahey/HLibs/AvlSet/AvlSet.html This should make it easy to do comparitive test/measurements between the two and maybe experiment with any wishlist extensions you want for the revised API (which is WIP I believe), using the underlying AVL implementation. I'll do the same thing for Data.Map soon, though it'll probably have to wait until next weekend now. This module is completely untested but the underlying AVL library has been pretty thouroughly tested. So it should work OK. If you use it and find any problems please let me know. Regards -- Adrian Hey

1 0