April 2008 - Haskell-Cafe

GSoC accepted projects
by Malcolm Wallace 22 Apr '08

22 Apr '08

Haskell.org is pleased to announce that we received 7 funded student slots from Google for this year's Summer of Code. Of the 30 proposals we received, the mentoring group chose the following 7: * GHC API Improvements by Thomas Schilling, mentored by Simon Marlow * Dynamically Loaded Plugins for the Glasgow Haskell Compiler by Maximilian Conroy Bolingbroke, mentored by Sean Seefried * Haskell API Search as an interface to Hackage by Neil Mitchell, mentored by Niklas Broberg * Language.C, a standalone parser/pretty printer library for C99 by Benedikt Huber, mentored by Iavor S. Diatchki * Cabal 'make-like' dependency framework by Andrea Vezzosi, mentored by Duncan Coutts * #1560 Efficient maps using generalised tries by Jamie Brandon, mentored by Adrian Charles Hey * Data parallel physics engine by Roman Cheplyaka, mentored by Manuel M. T. Chakravarty Slightly fuller details at http://code.google.com/soc/2008/haskell/about.html Congratulations to these students! Before coding begins officially at the end of May, there is a "community bonding period", where the students and community are encouraged to interact and further refine the work that will be done. To those students that did not get funding: do not be disheartened. Almost all of the proposals were good, and we had some difficult choices to make. What's more, since this is Open Source, you can continue to work on your projects anyway! Many of them will be useful to the community. In fact, Google have said that if any GSoC applicant manages (in the judgement of the mentors) to complete their project by the end of the summer, despite not receiving a funded place, they will send you a goodie-bag of Google swag (including a standard Google T-shirt, not the special GSoC one). Regards, Malcolm

1 0

Re: [Haskell] ANNOUNCE: Galois web libraries for Haskell released
by Henrique Ferreiro García 21 Apr '08

21 Apr '08

> * feed > Interfacing with RSS (v 0.9x, 2.x, 1.0) and Atom feeds Great! I had planned to make a feed reader using gtk2hs and this was exactly what I was waiting for. I have just seen that it is released as BSD3. Anyone knows if is there any problem in making use of it to develop a GPLv3 application? -- Henrique Ferreiro García <hferreiro(a)udc.es>

2 1

Wrong Answer Computing Graph Dominators
by Denis Bueno 21 Apr '08

21 Apr '08

I'm using the Data.Graph.Inductive.Query.Dominators library (http://haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-…) with GHC 6.8.2. The library is a bit spare on comments, so I may or may not be using it correctly. My goal is to compute the set of nodes that dominate two different nodes of a DAG, with respect to one initial node. My approach is: import qualified Data.Graph.Inductive.Graph as Graph import qualified Data.Graph.Inductive.Query.Dominators as Dom uips = intersect domConfl domAssigned :: [Graph.Node] -- my goal domConfl = fromJust $ lookup conflNode domFromLastd -- dominators of first node domAssigned = fromJust $ lookup (negate conflNode) domFromLastd -- dominators of second node domFromLastd = Dom.dom conflGraph lastd -- source node I compute the dominators individually and my answer is their intersection. When I call the dom function, my assumption is that I need to pass it the source node, and it tells me, for any node x to which there is a path from the source, the list of nodes for which *any path* from source to x must touch, i.e., the list of dominators of x. The DAG in question is attached as a postscript file, which is generated by `dot -Tps` using the output of the Graphviz module directly from the graph object. The nodes for which I'm computing dominators are labeled -2 and 2 (that is, conflNode = 2). The problem is that I think the answer is wrong. In particular I think the set of dominators for -2 is {20, -2}, and the set for 2 is {20, 2}. Their intersection is {20}, which is what I expect. But what I am getting is: --> uips = [-9,20] --> domConfl = [2,-9,20] --> domAssigned = [-2,-9,-12,20] --> lastd = 20 But -9 is not a dominator for 2, since 20,-7,8,6,2 is a path from 20 to 2 that does not touch 9. -9 is also not a dominator for -2, since 20,-7,8,6,-2 is a path from 20 to -2 not touching 9. Am I missing something? I've simplified the code above slightly from the original code in order to ignore some irrelevancies. The original code is for computing a learned clause in a SAT solver. The code in the state that will reproduce the error above is available via a git clone: git clone http://fid.stygian.net/dpllsat Build via cabal, configuring with --disable-optimization in order to enable assertions, then run: ./dist/build/dsat/dsat ./tests/problems/uf20/uf20-0226.cnf The graph should be saved in conflict.dot and with `dot -Tps -o conflict.ps conflict.dot` you should be able to turn it into the ps file attached. The problematic code referenced above starts on line 759. -- Denis

6 13

Hoogle
by Galchin, Vasili 21 Apr '08

21 Apr '08

Hello, I tried d to use Hoogle to find openFd's signature and more importantly FileMode. I found FileMode which is a type synonym with CMode. I don't understand what are the "values" for FileMode (so I can call openFd). ?? Thanks, Vasili

6 9

Functional board games
by Dougal Stanton 21 Apr '08

21 Apr '08

I'm having a go at making a functional board game (the back-end logic for one, at least) and as with all good projects it raises lots of questions. But I'll keep it to one this time. Does anyone know of functional-style implementations of chess/draughts/go/anything else that might give me ideas? I am writing a game of Thud (yes, from the Terry Pratchett book...) but I don't hold much hope of their being a functional-style Thud game already in existence! Cheers, D. -- Dougal Stanton dougal(a)dougalstanton.net // http://www.dougalstanton.net

6 6

Help with associated types
by Emil Axelsson 21 Apr '08

21 Apr '08

Hello! I'm trying to rewrite some FD classes to use associated types instead. The Port class is for type structures whose leaves have the same type: class Port p where type Leaf p type Struct p toList :: p -> [Leaf p] fromList :: [Leaf p] -> p (Leaf p) gives the leaf type, and (Struct p) gives a canonical representation of the structure regardless of leaf type. Here we just instantiate two leaf types: instance Port Int where type Leaf Int = Int type Struct Int = () toList a = [a] fromList [a] = a instance Port Bool where type Leaf Bool = Bool type Struct Bool = () toList a = [a] fromList [a] = a There's also a function for mapping over ports: mapPort :: ( Port pa , Port pb , Struct pa ~ Struct pb ) => (Leaf pa -> Leaf pb) -> (pa -> pb) mapPort f = fromList . map f . toList The equality constraint makes sure that we're mapping between equal structures. When I try to run this, I get: *Main> mapPort even (5::Int) <interactive>:1:8: No instance for (Integral (Leaf Int)) ... because as it stands, mapPort is not able to infer (pb = Bool) from (Struct pb = ()) and (Leaf pb = Bool). What's the easiest way to encode that pb can be inferred from (Struct pb) and (Leaf pb)? Thanks, / Emil PS. I used to have a class class SameStruct pa a pb b | pa -> a, pa b -> pb, pb -> b, pb a -> pa In the example above, we'd have pa=Int and b==Bool, so the second dependeny would infer pb=Bool.

2 3

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

5 6

letting go of file handles and Data.Binary
by Ben 20 Apr '08

20 Apr '08

hi all -- using binary 0.4.1 on ghc 6.8.2, vista 64 sp1. consider the following program: import System.Directory import Data.Binary main = do let dat = [1..10]::[Int] fname = "foo.dat" encodeFile fname dat dat2 <- decodeFile fname print (dat == dat2) removeFile fname this throws a permission denied exception, presumably because the file is still open when the removeFile is called. i've grovelled the source of Data.Bytestring.Lazy and all but i can't seem to understand the "right" way to make this work. note that i've forced the evaluation of dat2 and presumably therefore the filehandle is at least half-closed. any suggestions? take care, Ben

4 9

ANN: HXQ: An XQuery Compiler/Interpreter for Haskell
by Fegaras, Leonidas 20 Apr '08

20 Apr '08

Dear Haskell cafe members, I would like to announce the release of an XQuery compiler/interpreter for Haskell, called HXQ. You can get more info and download it at: http://lambda.uta.edu/HXQ/ HXQ is a fast and space-efficient translator from XQuery (the standard query language for XML) to embedded Haskell code. The translation is based on Haskell templates. HXQ takes full advantage of Haskell's lazy evaluation to keep in memory only those parts of XML data needed at each point of evaluation, thus performing stream-based evaluation for forward queries (queries that do not contain backward steps). This results to an implementation that is as fast and space-efficient as any stream-based implementation based on SAX filters or finite state machines. Furthermore, the coding is far simpler and extensible since its based on XML trees, rather than SAX events. For example, a complex XQuery against the DBLP bibliography (420MB XML) runs in 39 seconds on my laptop (using 18MB of max heap space in ghc). To contrast this, Qexo, which compiles XQueries to Java bytecode, took 1 minute 17 seconds (using no less than 1400MB of heap space). Also XQilla, which is written in C++, took 1 minute and 10 secs (using 1150MB heap). Current Status: HXQ supports most essential XQuery features, although some system functions are missing (but are easy to add). HXQ has little support for backward step axes, such as /.. (parent). Some, but not all, parent axis steps are removed using optimization rules; all others cause a compilation error. Finally, HXQ does not comply to the XQuery semantics that requires duplicate elimination and sorting by document order for every XPath step, which is very expensive and unnecessary in most cases. Please email me any suggestions for improvements or extensions you'd like to see. My plan is to use it as a base for various XQuery projects, such as adding SQL connectivity, as well as native storage and indexing. Best, Leonidas Fegaras U. of Texas at Arlington http://lambda.uta.edu/

1 0

Parallel weirdness
by Andrew Coppin 20 Apr '08

20 Apr '08

OK, so just for fun, I decided to try implementing a parallel merge sort using the seq and par combinators. My plan was to generate some psuedo-random data and time how long it takes to sort it. To try to account for lazy evaluation, what the program actually does is this: 1. Write the input data to disk without any sorting. (This ought to force it to be fully evaluated.) 2. Sort and save the data to disk 8 times. (So I can average the runtimes.) This is done with two data sets - one with 1 million items, and another with 2 million rows. Each data set is run through both the purely sequential algorithm and a simple parallel one. (Split the list in half, merge-sort each half in parallel, and then merge them.) The results of this little benchmark utterly defy comprehension. Allow me to enumerate: Weird thing #1: The first time you sort the data, it takes a few seconds. The other 7 times, it takes a split second - roughly 100x faster. Wuh? Weird thing #2: The parallel version runs *faster* than the sequential one in all cases - even with SMP disabled! (We're only talking a few percent faster, but still.) Weird thing #3: Adding the "-threaded" compiler option makes *everything* run a few percent faster. Even with only 1 OS thread. Weird thing #4: Adding "-N2" makes *everything* slow down a few percent. In particular, Task Manager shows only one CPU core in use. Adding more than 2 OS threads makes everything slow down even further - but that's hardly surprising. Can anybody explain any of this behaviour? I have no idea what I'm benchmarking, but it certainly doesn't appear to be the performance of a parallel merge sort!

7 22