April 2008 - Libraries

darcs patch: Change LICENSE from BSD4 to BSD3
by Lennart Kolmodin 26 Apr '08

26 Apr '08

Sat Apr 26 07:58:06 CEST 2008 Lennart Kolmodin <kolmodin(a)gentoo.org> * Change LICENSE from BSD4 to BSD3 Picking BSD4 over BSD3 is usually by confusion. See http://hackage.haskell.org/trac/hackage/ticket/205.

1 0

darcs patch: Re-export (>>>), (<<<) from Control.Arrow for compatab...
by Duncan Coutts 25 Apr '08

25 Apr '08

It was reported in #haskell that xmonad-contrib does not compile with ghc HEAD. We tracked it down to (>>>) no longer being exported from Control.Arrow. It is now a member of the Category superclass and defined in Control.Category but it is no longer exported from Control.Arrow. It seems that any code that does not define its own arrow instances would still be able to work unchanged if (>>>) and (<<<) were just to be re-exported from Control.Arrow. So here's a completely untested patch to do that. Duncan Fri Apr 25 10:11:13 BST 2008 Duncan Coutts <duncan.coutts(a)worc.ox.ac.uk> * Re-export (>>>), (<<<) from Control.Arrow for compatability They're now defined in Control.Category but all existing code expects them o be exported from Control.Arrow. For example, this should unbreak xmonad-contrib.

1 0

Data.Map improvement patch
by Milan Straka 25 Apr '08

25 Apr '08

Hello, Recently I was going through the Data.Set implementation and I was taken aback by setting the parameter \delta to 4. The implementation is based on Adams' bounded trees and uses ratio \alpha=2, in which case the paper clearly states \delta must be at least 4.646 (which is written in the source file Set.hs several lines above the assignment \delta=4; Map.hs uses \delta=5). So I read that Adams' paper again and found out, that the analysis described there contains two major mistakes [it is good to read the analysis from the paper now if you want to follow, pages 26 to 31]. 1) The analysis assumes that just before the balancing rotation, the heavier subtree of the unbalanced vertex was inserted to, i.e. the balance is ``off by 1''. But when the lighter subtree is deleted from, the balance is ``off by \delta'', which is worse. When taken into account, it results in equation $\delta\le{n\over\alpha}+1$, which must hold for each positive integer n. 2) The cases of empty subtrees are not analysed. When considered, it follows that for \alpha=2 a single rotation can restore balance only when \delta<5. [tree with 1 left vertex and 5 right, delete the left one and voila...] Right now I was puzzled why both Data.Set and Data.Map implementations seem to work. *) Data.Set: The constraint from the paper \delta >= 4.646 comes from the inequality $(1/\alpha) >= {\delta(1+{1\over n})+1\over\delta^2-1}$, which must hold for each positive integer n. The worst case is n=1, which is chosen in the paper. But when using n=2, the resulting constraint is \delta>3.792. The remaining case n=1 can be solved by examining all possible situations for \alpha<=2 and \delta=4, which all reveal to be correctly balanced using a~single rotation. Also the new constraint $\delta\le{n\over\alpha}+1$ can be satisfied for \alpha=2 and \delta=4 by examining small cases separately. The thing is the inequalities from the paper do not contain the floor function. Sure, for general parameters it is difficult to handle, but for the specific parameters the results are much better when truncation is taken into account. *) Data.Map: The constraint \delta<5 for \alpha=2 is not possible to change without changing the algorithm. But it turns out that the Data.Map implementation performs the balancing rotations not when one subtree is more than \delta times heavier than the other as described in the paper, but when one subtree is at least \delta times heavier. So the Data.Map implementation behaves like the analysed implementation with \delta just a bit smaller than 5. Ok, so both 4 and 5 work for the implementation of Data.Map and Data.Set. Which one is better? This parameter affects the height of a tree. With \delta=4 the worst case is 1:4, so the height is log_{5/4}n ~ 3.1 log_2 n. With \delta=5 the height is log_{6/5}n ~ 3.8 log_2 n. In Haskell, lot of operations must copy a whole path in a tree -- so a lower tree means less time and memory needed. There are more rotations, but we have to construct new nodes anyway, so one would expect minor advantage of \delta=4 over \delta=5. It is difficult to measure these things in Haskell for me (just adding a SPECIALIZE of increasing/decreasing heap size can change order of execution time), but anyway, here are times of 50000 sequential inserts, then 800000 lookups and 50000 deletes (the source is attached for the freaks): Data.Set with \delta=4 180 300 72 Data.Set with \delta=5 208 304 76 Data.Map with \delta=4 212 328 84 Data.Map with \delta=5 256 324 88 IntSet 56 356 48 IntMap 56 360 48 So I would suggest to change "delta = 5" to "delta = 4" in the Data.Map.hs and leave "delta = 4" in the Data.Set.hs file. The darcs patch is included :) Any comments are welcome, Milan

4 4

ANNOUNCE: Galois web libraries for Haskell released
by Don Stewart 23 Apr '08

23 Apr '08

Galois, Inc. is pleased to announce the open source release of a suite of web programming libraries for Haskell! The following libraries are available, providing support for a wide range of Haskell web programming scenarios: * json JSON (JavaScript Object Notation) is a lightweight data-interchange format. It is easy for humans to read and write. It is easy for machines to parse and generate. It is based on a subset of the JavaScript Programming Language, Standard ECMA-262 3rd Edition - December 1999. This library provides a validating parser and pretty printer for converting between Haskell values and JSON. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/json * xml A simple, lightweight XML parser/generator. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xml * utf8-string A UTF8 layer for IO and Strings. The utf8-string package provides operations for encoding UTF8 strings to Word8 lists and back, and for reading and writing UTF8 without truncation. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string * selenium Haskell bindings to communicate with a Selenium Remote Control server. This package makes it possible to use Haskell to write test scripts that exercise web applications through a web browser. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/selenium * curl libcurl is a client-side URL transfer library, supporting FTP, FTPS, HTTP, HTTPS, SCP, SFTP, TFTP, TELNET, DICT, LDAP, LDAPS and FILE. libcurl supports SSL certificates, HTTP POST, HTTP PUT, FTP uploading, HTTP form based upload, proxies, cookies, user+password authentication (Basic, Digest, NTLM, Negotiate, Kerberos4), file transfer resume, http proxy tunneling and more! This package provides a Haskell binding to libcurl. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/curl * sqlite Haskell binding to sqlite3 <http://sqlite.org/>, a light, fast database. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sqlite * feed Interfacing with RSS (v 0.9x, 2.x, 1.0) and Atom feeds http://hackage.haskell.org/cgi-bin/hackage-scripts/package/feed * mime Haskell support for working with MIME types. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/mime Together these fill in a big chunk of the web programming stack for Haskell. Get the code! You can find all the cabalised packages on hackage.haskell.org. About: Galois <http://galois.com> researches, designs and develops high assurance technologies for security-critical systems, networks and applications. We use Haskell as a primary development tool for producing robust components for a diverse range of clients. Web-based technologies are increasingly important in this area, and we believe Haskell has a key role to play in the production of reliable, secure web software. The culture of correctness Haskell encourages is ideally suited to web programming, where issues of security, authentication, privacy and protection of resources abound. In particular, Haskell's type system makes possible strong static guarantees about access to resources, critical to building reliable web applications. We hope that the release of this suite of libraries to the community will push further the adoption of Haskell in the domain of web programming. This release brought to you by: Iavor Diatchki Trevor Elliott Sigbjorn Finne Andy Gill Eric Mertens Isaac Potoczny-Jones Don Stewart Aaron Tomb

2 4

proposal: reimplement Data.Graph.Inductive.Query.Dominators
by Bertram Felgenhauer 22 Apr '08

22 Apr '08

Hi, (this is Trac ticket #2227, http://hackage.haskell.org/trac/ghc/ticket/2227) As pointed out at http://www.haskell.org/pipermail/haskell-cafe/2008-April/041739.html ff., Data.Graph.Inductive.Query.Dominators.dom is buggy. Furthermore, it's slow, so instead of submitting the quick fix from that thread, I've rewritten the module from scratch using a more efficient algorithm. The algorithm works by calculating the immediate dominators of the graph nodes first, so the patch also adds a function that returns those. It should be handy for flow graph analysis. Deadline for discussion ... is a week sufficient? That would be April 28th. regards, Bertram

3 4

Announce: bytestring 0.9.1.0
by Don Stewart 21 Apr '08

21 Apr '08

Hey all, I'm pleased to announce a new major release of bytestring, the efficient string library for Haskell, suitable for high-performance scenarios. This release is primarily an (incremental) performance improvement release, though with some notable significant improvements, along with long term test coverage and quality control changes. Highlights: * a long term performance bug with Ord instances, involving very small strings, and Data.Map has been squashed. * everything's a little faster -- shootout problems showed a 1-5% speedup just by switching to the new library. Thanks goes to the Hac4 Haskell Hackathon organisers, in Gothenburg, Sweden, where the majority of this work to create this release took place. Key changes: * Data.Map short key performance greatly improved: - 'words Map' running time: 6.310s bytestring 0.9.0.1 1.071s bytestring 0.9.1.0 * Uses cheaper unsafeDupablePerformIO for allocation. - tail recursive tight loops (fixes obscure stack overflow) * Generally faster: - Shootout sum-file: 1.218s to 1.190s - Shooout fasta: 9.210s to 8.811s * 4-5x faster small substring search (breakSubstring/findSubstring/isInfixOf). * Extensive QuickCheck coverage reporting and improvements: - http://code.haskell.org/~dons/tests/bytestring/hpc_index.html Get the code: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring Note that if you upgrade to the new bytestring release, older packages built against previous releases will still require the old bytestring package. For best results, rebuild any bytestring-depending packages against the new library only. Cheers, Don

2 1

RFC: A standardized interface between web servers and applications or frameworks (ala WSGI)
by Johan Tibell 19 Apr '08

19 Apr '08

Good day hackers, The Python community have been successful in standardizing an interface between web server and applications or frameworks resulting in users having more control over their web stack by being able to pick frameworks independently from web servers, and vice versa. I propose we try to do the same for Haskell. I've written half a draft for a Haskell version of Python's PEP 333 [1]. If you're interested in taking part in this effort please read through the Python spec first (as it is way more complete and you can understand this proposal better by reading it, I've skipped some important issues in my first draft) and then go read the Haskell spec [2]. I'm particularly interesting in feedback regarding: * Doing in this way won't work as it violates HTTP/CGI spec part X, Y and Z (the Python spec takes lots of things from the CGI spec including naming and semantics). * My server/framework could never provide/be run under this interface. * This interface has bad performance by design. * Using a different set of data types would work better. The spec needs to be extended to cover all the corners of HTTP. Some parts need to be motivated better. It is easier for me to motivate things if people would tell me what parts are badly motivated. Note: I'm open to a complete rewrite if needed. I'm not wedded to the current design and/or wording. In fact parts of the wording is borrowed from the Python spec. The parts with bad grammar are all mine. 1. http://www.python.org/dev/peps/pep-0333/ 2. http://www.haskell.org/haskellwiki/WebApplicationInterface -- Johan

8 12

Re: [Haskell] making inits less strict
by Don Stewart 08 Apr '08

08 Apr '08

john.tromp: > The standard definition of inits: > > inits [] = [[]] > inits (x:xs) = [[]] ++ map (x:) (inits xs) > > is unnecessarily strict, evaluating its argument > before yielding the initial [] of the result. > An improved version is: > > inits l = [] : case l of [] -> [] > (x:xs) -> map (x:) inits xs > > This allows one to define for instance > nats = map length (inits nats) > which loops for the standard definition. > Can you forward this to the libraries(a)haskell.org list, and file a proposal to replace the current definition? http://haskell.org/haskellwiki/Library_submissions We noticed this while implementing lazy bytestrings, which had a similar issue, and fixing it is cheap enough. -- Don

1 0

darcs patch: fmt cabal (and 9 more)
by gwern0＠gmail.com 08 Apr '08

08 Apr '08

Mon Apr 7 00:50:28 EDT 2008 gwern0(a)gmail.com * fmt cabal Mon Apr 7 00:50:49 EDT 2008 gwern0(a)gmail.com * .cabal: +category Mon Apr 7 00:53:00 EDT 2008 gwern0(a)gmail.com * .cabal: change homepage and links The original listed website, <http://www.haskell.org/QuickCheck/>, seems to be quite dead. I've replaced it with a link to the haskell wiki and to the old chalmers site. Mon Apr 7 00:57:49 EDT 2008 gwern0(a)gmail.com * improve README Mon Apr 7 00:59:04 EDT 2008 gwern0(a)gmail.com * .cabal: add a real description Mon Apr 7 01:00:18 EDT 2008 gwern0(a)gmail.com * .cabal: BSD4 -> BSD3 license change The 4-clause BSD includes the advertising clause, and is 4 clauses long. The provided LICENSE file doesn't seem to have an advertising clause for anyone, and seems to have only 3 clauses. Which is good, as people don't like the advertising BSD license - why it's deprecated. Mon Apr 7 01:01:46 EDT 2008 gwern0(a)gmail.com * .cabal: +Bringert to copyright Per the license file, which mentions two copyright holders. Mon Apr 7 01:05:34 EDT 2008 gwern0(a)gmail.com * -Wall Monadic.hs Mon Apr 7 11:46:44 EDT 2008 gwern0(a)gmail.com * some misc partial -Wall Mon Apr 7 11:50:03 EDT 2008 gwern0(a)gmail.com * .cabal: don't forget the examples

1 0

Data.Map.toDescList not exported?
by Evan Laforge 04 Apr '08

04 Apr '08

It's in the source, marked as being O(n), but it's not in the export list. Oversight? I'm using ghc-6.8.2. I'm using (reverse.toAscList) but I think running 'head' on that is going to be less efficient than on the real toDescList. Thanks!

1 0