February 2011 - Haskell-Cafe

Unit propagation
by PatrickM 16 Feb '11

16 Feb '11

This is my last part from a project and I need some help with the following function: "If a clause in a propositional formula contains only one literal, then that literal must be true (so that the particular clause can be satisfied). When this happens, we remove the unit clauses (the ones that contain only one literal), all the clauses where the literal appears and also, from the remaining clauses, we delete the negation of the literal (because if P is true, -P will be false). For example, in the formula (P v Q v R) ^ (-P v Q v-R) ^ (P) we have one unit clause (the third clause (P) ). Because this one has to be true for the whole formula to be true we assign True to P and try to find a satisfying assignment for the remaining formula. Finally because -P cannot be true (given the assigned value of P) then the second clause is reduced by eliminating the symbol -P . This simplification results in the revised formula (Q v -R). The resulting simplification can create other unit clauses. For example in the formula (-P v Q) ^ (P) is simplified to (Q) when the unit clause (P) is propagated. This makes (Q) a unit clause which can now also be simplified to give a satisfying assignment to the formula. Your function should apply unit propagation until it can no longer make any further simplifications. Note that if both P and -P are unit clauses then the formula is unsatisfiable. In this case the function" type Atom = String type Literal = (Bool,Atom) type Clause = [Literal] type Formula = [Clause] type Model = [(Atom, Bool)] type Node = (Formula, ([Atom], Model)) ropagateUnits :: Formula -> Formula propagateUnits = filter.something---here I need help Thanks in advance -- View this message in context: http://haskell.1045720.n5.nabble.com/Unit-propagation-tp3384635p3384635.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 4

Haskell GUI
by Mihai Maruseac 16 Feb '11

16 Feb '11

Hi, I'd like to start a new project in Haskell, this time using an user interface. Looking at [1] I found that there are several of them listed there. However, the list there is very long. Right now, I am unsure on what is best to use. Can someone give me any hints on which is the most kept-to-date and most supported GUI library? Basically, I want to display some graphs in a dynamic way, reacting to user input, nothing fancy right now. Thanks, -- Mihai

5 6

coding a queue with reactive
by sam.roberts.1983＠gmail.com 16 Feb '11

16 Feb '11

Hi all, I hope someone is interested in helping me out with the reactive library. I am trying to implement a function "queue" in reactive: queue :: Double -> Event a -> Event a This is a simple queue: events from the event stream coming into the queue, queue up waiting to be processed one by one. Processing an event takes a constant amount of time for every event. The output of the queue function is the stream of processed events. My current (deficient) implementation of the queue function is: queue dt eventsIn = do (a,exitT) <- withExitTime eventsIn _ <- atTime exitT return a where withExitTime = scanlE calcExitTime (undefined, -1/0) . withTimeE calcExitTime (_,prevExitT) (a,inT) = (a, (max inT prevExitT) + dt) I am having three problems. 1 - I find my implementation of the queue is less clear then an imperative description of a queue. 2 - I rely on being able to calculate the exit time of an event when it first arrives at the queue, whereas an imperative queue would simply store the event in queue and only need to calculate the output time once the event was popped off the queue. If I want to do something similar with my function, I think I need to make some sort of recursive definition of a queue which responds to it's own exit events. I've tried to code this up, but have not managed to wrap my brain around the concept. 3 - The code performs horribly! I am guessing that this is because I have not told reactive that the exit events preserve the ordering of the input events, but I'm not sure how to encode that relationship in reactive. (It's worth noting here that I actually have a fourth problem too: I get linker errors while trying to compile a profiling version of the program ... but that's a separate topic.) It's also worth noting, from a performance point of view, that a much simpler "delay" function with similar use of the bind function performs badly as well: delay :: Double -> Event a -> Event a delay dt es = do (e,t) <- withTimeE es _ <- atTime (t+dt) return e I'd appreciate any light that anyone could shed on any of these problems. If there's a better way of structuring my queue function, or if there's a better way of changing event times in reactive, I am open to all suggestions. Many thanks, Sam

2 4

Noob question about list comprehensions
by Tako Schotanus 16 Feb '11

16 Feb '11

Hello, I was going through some of the tuturials and trying out different (syntactic) alternatives to the given solutions and I I got to this line: *length [chain x | x <- [1..100] , length (chain x) > 15]* Now, there's nothing wrong with it, it works of course. But the application of chain x is repeated twice and I wondered if there was a way for a guard in a list comprehension to refer to the item being produced? Like this for example (invented syntax): *length [@c(chain x) | x <- [1..100] , length c > 15]* NB: Just to make clear, I'm not asking if there is an alternative way of preventing the repetition, of course there is, I'm just wondering about this very specific case within list comprehensions. -Tako

4 4

Proving correctness
by C K Kashyap 16 Feb '11

16 Feb '11

Hi Folks, I've come across this a few times - "In Haskell, once can prove the correctness of the code" - Is this true? I know that static typing and strong typing of Haskell eliminate a whole class of problems - is that related to the proving correctness? Is it about Quickcheck - if so, how is it different from having test sutites in projects using mainstream languages? Regards, Kashyap

21 25

On hGetContents semi-closenesscloseness
by Rafael Cunha de Almeida 16 Feb '11

16 Feb '11

From http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html: Computation hGetContents hdl returns the list of characters corresponding to the unread portion of the channel or file managed by hdl, which is put into an intermediate state, semi-closed. In this state, hdl is effectively closed, but items are read from hdl on demand and accumulated in a special list returned by hGetContents hdl. What state is that? It seems to be something related to Haskell. I couldn't find a definition for it in the unix documentation I have laying around. Continuing reading System IO documentation I read: Any operation that fails because a handle is closed, also fails if a handle is semi-closed. The only exception is hClose. A semi-closed handle becomes closed: * if hClose is applied to it; * if an I/O error occurs when reading an item from the handle; * or once the entire contents of the handle has been read. So it looks like hGetContents sets some flag in the handler saying it is in that semi-closed state. So no other operations are valid, but I think the file descriptor to the file is actually kept open. It's only when the contents are entirely consumed that the descriptor gets closed. Is hGetContents responsible for closing the descriptor? Or is it the garbage collector? Who closes the descriptor when the contents are read? Looking at hGetContents function definition, it uses lazyRead to read the contents, but it calls a wantReadableHandle which might or might not close the handle after lazyRead. By looking at the documentation it seems like the only way for us to actively close the descriptor is either reading the whole thing or calling hClose. But one has to be very carefully when to call the handler, because it doesn't matter if it looks like it was consumed, it really has to be consumed. The following code prints the contents of foo file to the screen: openFile "foo" ReadMode >>= \handle -> (hGetContents handle >>= (\s -> putStr s >> hClose handle)) [1] The following code does not: openFile "foo" ReadMode >>= \handle -> (hGetContents handle >>= (\s -> hClose handle >> putStr s)) [2] It is common knowledge that haskell is very lazy, so it only does things when absolutely necessary, otherwise it prefers to write it off in the TODO list. It does that even if writing to the TODO takes longer than the computation would, that's how lazy it is. That's the origin of the often used expression "he is quite a haskell". The question most people doesn't have a good answer is: when does Haskell thinks it is necessary to do something? In [2] the lazyRead inside of hGetContents (or perhaps hGetContents all together) only gets executed after hClose handle. Why is that? How do I figure out the ordering of computation?

6 5

Review request for "platform independent interactive graphics" with VNC
by C K Kashyap 16 Feb '11

16 Feb '11

Hi, I've been working on a Haskell based platform independent graphics rendering using VNC. I'd like it very much if you could take a look at it and give me feedback. Using it is straight forward - git clone git@github.com:ckkashyap/Chitra.git cd Chitra make ./Main 100 100 5900 Main starts off a vncserver listening on port 5900. A standard vncviewer can be used to connect to 'localhost' and you can see a 100 x 100 screen. Clicking on the screen will set the pixel on the click location. What I eventually want to do is somehow integrate this piece with GHCI in such a manner that one can use GHCI to draw things on the VNC buffer. Regards, Kashyap

4 14

Abstracting a Genetic Algorithm
by Alex Good 16 Feb '11

16 Feb '11

I've copied this from http://stackoverflow.com/questions/5010267/haskell-abstracting-a-genetic-al… as someone suggested that it might spark an interesting discussion I'm new to the world of Haskell programming and I'm cutting my teeth on a simple genetic algorithm for finding good solutions to the Travelling Salesman problem. I am representing the solutions as permutations on Integers and so I have this type synonym type Genome = [Int] The algorithm itself is a set of functions which operate on the solutions: mutation :: Genome -> Genome selectParents :: [Genome] -> [Genome] -> [Genome] crossover :: Genome -> Genome -> (Genome, Genome) selectSurvivors :: [Genome] -> [Genome] -> [Genome] I'm not sure how much of my code is relevant to my question so please ask if more details are needed. One thing that might be worth mentioning is that the type signatures above are actually simplified, I am in fact using the State monad to carry around an StdGen so all of these functions actually return stateful computations. There are several things which I would like to do with this but can't quite get my head around. I want to make it possible to choose different representations for the solutions, it seems to me that this would be a natural place to use a type class, so that Genome would be the type class and [Int] a specific instance of this Genome. Now, I want to be able to experiment with the implementations, and I want to be able to use the code in other projects. Using a type class like this would require that every new algorithm I create would require me to create another instance of Genome, is this a good way to go about creating a library? One bonus question, just a thing that's been bothering me, is there any way to create something like a type synonym for a function so that if I'm writing a function which takes functions as arguments I can write the synonym rather than the whole type signature of the function i.e so that something like the following would work. type someFunc = [Int] -> [Int] -> Int someOtherFunc :: someFunc -> [Int] -> Int Right, hopefully that's a lucid enough explanation of the problem, feel like I've missed the really obvious answer but it hasn't jumped out at me. Cheers

2 1

Re: [Haskell-cafe] ANNOUNCE: hspec-0.1.0 (Behavior Driven Development for Haskell)
by Simon Michael 15 Feb '11

15 Feb '11

On 2/11/11 8:42 PM, trystan.s(a)comcast.net wrote: > Any advice, comments, or questions are welcome. Hi Trystan.. it looks great. I like the rubyish brevity and readability. Please do publish on hackage. What should we read to find out more about this style of tests, http://rspec.info ? When you get a chance, some examples using quickcheck properties would be interesting. I suppose it could also be made to accept hunit tests ? I currently use test-framework partly for it's nice concurrent test runner. I assume hspec tests currently run in sequence ? Any thoughts on how this fits in with the existing haskell test tools, when to use it ? Thanks for working on it. -Simon

2 1

unicode filenames advice
by Joey Hess 15 Feb '11

15 Feb '11

I've been trying to deal with how my haskell program handles unicode filenames. Been dealing with problems like those described here: http://hackage.haskell.org/trac/ghc/ticket/3307 Or, simply demonstrated by feeding unicode to getLine >>= readFile My approach currently is to carefully identify any point where a FilePath is output, and run it through a filePathToString (which varies by OS), as suggested in the above bug report. Is there a less tedious and error-prone way? What is the best approach to use now, assuming that these issues will be dealt with in some way in Haskell, eventually? -- see shy jo

2 1