- Haskell-Cafe - Haskell.org

Anyone mind proofing a short monad transformers explanation?
by Jack Kelly 22 Apr '08

22 Apr '08

I sent this to a friend who asked me about monad transformers and he reckons it should be saved somewhere. If anyone feels up to giving it a quick fact-check, that'd be great. I'm not sure what to do with it, though. It doesn't seem to be made of the right stuff for a tutorial but I'm not sure what to do with it. --- SNIP --- Basically it's like making a double, triple, quadruple, ... monad by wrapping around existing monads that provide wanted functionality. You have an innermost monad (usually Identity or IO but you can use any monad). You then wrap monad transformers around this monad to make bigger, better monads. Concrete example: Suppose I was writing a server. Each client thread must be of type IO () (that's because forkIO :: IO () -> IO ThreadID)). Suppose also that this server has some configuration that (in an imperative program) would be global that the clients all need to query. > data Config = Config Foo Bar Baz One way of doing this is to use currying and making all the client threads of type Config -> IO (). Not too nice because any functions they call have to be passed the Config parameter manually. The Reader monad solves this problem but we've already got one monad. We need to wrap IO in a ReaderT. The type constructor for ReaderT is ReaderT r m a, with r the shared environment to read from, m the inner monad and a the return type. Our client_func becomes: > client_func :: ReaderT Config IO () We can then use the ask, asks and local functions as if Reader was the only Monad: (these examples are inside do blocks) > p <- asks port (Assuming some function port :: Config -> Int or similar.) To do stuff in IO (or in the general case any inner monad) the liftIO function is used to make an IO function work in this wrapped space: (given h :: Handle, the client's handle) > liftIO $ hPutStrLn h "You lose" > liftIO $ hFlush h IO is once again special. For other inner monads, the lift function does the same thing. Note also that IO has no transformer and must therefore always be the innermost monad. This is all well and good, but the client_func now has type ReaderT Config IO () and forkIO needs a function of type IO (). The escape function for Reader is runReader :: Reader r a -> r -> a and similarly for ReaderT the escape function is runReaderT :: ReaderT r m a -> r -> m a: (Given some c :: Config that's been assembled from config files or the like) > forkIO (runReaderT client_func c) Will do the trick. Monad transformers are like onions. They make you cry but you learn to appreciate them. Like onions, they're also made of layers. Each layer is the functionality of a new monad, you lift monadic functions to get into the inner monads and you have transformerised functions to unwrap each layer. They're also like a present in that regard: in this example we unwrapped the outer wrapping paper to get to the present: an object of type IO (), which lets us make haskell do something.

3 2

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 21 Apr '08

21 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