February 2011 - Haskell-Cafe

Haskell function help
by Houdini 02 Feb '11

02 Feb '11

I have a Question about haskell 1. is a something more complicated and I need some help with it if possible.. In order to check the satisfiability of a formula in a given model we propagate the effects of assigning a truth value to an atom in a formula. Assume an atom to which we assign the value True. The following effects can be applied to the formula: - The positive literals have the same True value and, therefore, any clauses that contain them are removed from the formula. This is to indicate that these clauses could be satisfied and hence no longer affect the satisfiability of the formula. - The negated literals have a value of False and are, therefore, removed from any clause they are in. This is to indicate that these clauses are still not satisfied and can only be made true by one of the other literals obtaining a value of True. In the case where False is assigned to the atom, the positive literals will now be false and should be removed from their clauses while the negative literals will become true and have their clauses removed from the formula. For example, in the formula (P _ Q _ R) ^ (:P _ Q _ :R) ^ (P _ :Q), assume we assign True to P. Then the clauses containing P, ie. (P _ Q _ R) and (P _ :Q) are removed from the formula, whereas :P is removed from any clause it is in, ie. (:P _ Q _ :R). This results in the formula (Q _ :R). On the other hand, if we assign False to P, we then remove (:P _ Q _ :R) from the formula and P from its clauses, thus obtaining (Q _ R) ^ (:Q). The overall formula is satisfiable if it can be reduced to the empty list since in this case all the clauses were satisfied. If there is an empty list within the overall formula then that means that a clause was not satisfied and hence the formula can not be satisfied with the assignment that led to this state. -assign :: (Atom,Bool)->Formula->Formula The assign function should take an (Atom,Bool) pair and a formula and propagate the effects of assigning the given truth value to the atom in the formula as described above The code(on which I received help from here also): module Algorithm where import System.Random import Data.Maybe import Data.List type Atom = String type Literal = (Bool,Atom) type Clause = [Literal] t ype Formula = [Clause] type Model = [(Atom, Bool)] t ype Node = (Formula, ([Atom], Model)) atomsClause :: Clause -> [Atom] -This function takess a Clause and return the set of Atoms of that Clause. atomsClause = nub . map snd atoms :: Formula -> [Atom] atoms = nub . map snd -----This function takes a Formula returns the set of Atoms of a Formula isLiteral :: Literal -> Clause -> Bool isLiteral = isLiteral = any . (==)----This function returns True if the given Literal can be found within the Clause. flipSymbol :: Model -> Atom -> Model--- f lipSymbol m a = map f m - where f (atom, value) = if a == atom then (atom, not value) else (atom, value)-this function takes a Model and an Atom and flip the truthvalue of the atom in the model assign :: (Atom,Bool)->Formula->Formula assign = undefined--------any advice here? Thank you -- View this message in context: http://haskell.1045720.n5.nabble.com/Haskell-function-help-tp3365994p336599… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 11

Re: [Haskell-cafe] Instancing "Typeable" for monad transformers?
by oleg＠okmij.org 02 Feb '11

02 Feb '11

One can do something a bit shorter > instance (Typeable a, Typeable1 m) => Typeable1 (Iteratee a m) where > typeOf1 i = mkTyConApp (mkTyCon "Data.Enumerator.Iteratee") > [typeOf a, typeOf1 m] > where > (a,m) = peel i > peel :: Iteratee a m w -> (a, m ()) > peel = undefined still a bother to write every time one needs it, but tolerable. Only the signature of 'peel' matters.

1 0

Haskell Platform 2011.x - planned release date?
by Max Cantor 02 Feb '11

02 Feb '11

January has come and gone and HP 2011 has not come with it. Is there an updated timetable for the next version of the HP? I'm not complaining or upset or whining, just trying to plan. Great work so far, looking forward to HP 2011! mc

4 3

plugins and internal error: stg_ap_v_ret
by Michael Snoyman 01 Feb '11

01 Feb '11

Hi all, I'm trying to convert wai-handler-devel to use plugins instead of hint, but cannot even get some basic usages to work properly. I've put together a minimal example that loads a WAI application from a separate file and runs it, but this immediately causes the program to crash saying: loader: internal error: stg_ap_v_ret (GHC version 6.12.3 for i386_unknown_linux) Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug Is this an actual bug in GHC, or am I misusing the plugins package? The two source files: MyModule.hs {-# LANGUAGE OverloadedStrings #-} module MyModule where import Network.Wai import Data.ByteString.Lazy.Char8 () myapp _ = responseLBS status200 [("Content-Type", "text/plain")] "myapp" loader.hs import System.Plugins.Make import System.Plugins.Load import Network.Wai.Handler.Warp (run) main :: IO () main = do MakeSuccess _ obj <- makeAll "MyModule.hs" [] LoadSuccess _ app <- load_ obj [] "myapp" run 3000 app Thanks, Michael

2 5

Automatically move cursor focus in split window in haskell-mode in emacs on load (C-c C-l) command?
by JETkoten 01 Feb '11

01 Feb '11

With the community server down it looks like I can't join the haskell-mode mailing list, and also I thought someone might have already done this, so I've posted here. I'm new to Haskell and emacs... and don't know any elisp at all! I'm trying to set up my haskell-mode so that when I've finished inputting code in a buffer that's in haskell-mode, and I then do C-c C-l to split the screen and load the code into ghci in the lower buffer, the cursor focus will automatically jump down to the bottom half of the split screen and I can instantly begin to interact with ghci. The way it defaults to now is that the cursor stays in the topmost editing half of the split screen, and I inevitably begin typing and mess up my code and have to do some backspacing and then mouse over to the bottom half. :) I checked on #haskell and #emacs last night, and someone suggested either "doing it with elisp" or keyboard macros, but I'm not sure how to do the first, and I think the second is not what I'm looking for. I'd like for haskell-mode to otherwise remain the same, and to still use the same C-c C-l key sequence, but I'd just like it to always be set up to add the step in the load sequence of jumping the cursor focus down to the lower half of the split for me. Any ideas? (Thanks in advance.)

3 4

Automatically move cursor focus in split window in haskell-mode in emacs on load (C-c C-l) command?
by Steven Collins 01 Feb '11

01 Feb '11

I'm using haskell-mode-2.8.0 and emacs 22.2.1 on Ubuntu 9.10 The following elisp code works for me to change the focus to the GHCi buffer (window) after the C-c C-l command in Haskell Mode. Try this in your .emacs file. (defadvice inferior-haskell-load-file (after change-focus-after-load) "Change focus to GHCi window after C-c C-l command" (other-window 1)) (ad-activate 'inferior-haskell-load-file) I have this after the haskell mode configuration section of my .emacs file. Remeber to go to the Emacs-lisp menu and 'Byte-compile and Load' after adding the above code to your .emacs file. To understand what the elisp code is doing you can go to the help menu in emacs, then drill down via 'Search Documentation ' , then 'Find any object by name'. Which will put you in the mini-buffer. Type in either defadvice or ad-activate to see the documentation for these functions. If you are a little rusty on elisp this documentation may be a little hard to understand. Basically this is what's happening. The function that is bound to the C-c C-l command is inferior-haskell-load-file. Which is an elisp function name and part of the elisp haskell mode code. The defadvice is kind of overloading this function. We are telling emacs that 'after' executing the 'inferior-haskell-load-file' function, execute our new function who's name is 'change-focus-after-load'. The body of our function is just one expression (other-window 1). This is the kind of stuff that makes it easy to modify (hack) the functionality of emacs to do what you want. I hope this helps and enjoy hacking in Haskell Steven

2 1

Timeout exceptions sometimes don't work, even in pure (non FFI) code
by Job Vranish 01 Feb '11

01 Feb '11

I'm trying to test some properties with quickcheck. If these tests fail, they will almost certainly fail by nontermination. I've been using the 'within' function to catch these nontermination cases. However, I was surprised to find that this doesn't always work. 'within' uses the 'timeout' function under the hood. Here is an example that demonstrates the problem: import System.Timeout import Control.Exception works :: Int -> Int works x = sum $ cycle [x] doesntWork :: Int -> Int doesntWork x = last $ cycle [x] test1 = timeout 1 $ evaluate $ works 5 == 5 -- terminates test2 = timeout 1 $ evaluate $ doesntWork 5 == 5 -- never terminates test1 returns Nothing as expected, but test2 never terminates. Why? I thought timeout exceptions are supposed to always work with pure (non FFI) Haskell code. Is there any way I can work around this? I'm using ghc 6.12.2 Thanks, - Job

2 2

Packages all screwed up
by Arnaud Bailly 01 Feb '11

01 Feb '11

Hello, I recently tried to upgrade some package (eg. yesod) and it seems that, in the process, I screwed up my Haskell packages setup. When I am trying to do a simple: > ghc --make Crete1941 It fails with message: Loader\Communication.hs:14:7: Could not find module `System.Process': Use -v to see a list of the files searched for. which is quite annoying ! Is there a way to reconstruct a sane baseline ? Thanks in advance Arnaud PS: In case it might be helpful, here is the output of ghc-pkg check -v There are problems in package pandoc-1.6: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package zip-archive-0.1.1.6: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package url-2.1.2: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package filestore-0.3.4.3: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package happstack-server-0.5.0.2: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package happstack-data-0.5.0.2: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist There are problems in package feed-0.3.7: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package SHA-1.4.1.3: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist There are problems in package hashed-storage-0.5.3: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist There are problems in package yesod-0.6.0.2: dependency "cereal-0.3.0.0-835aef1b61feb29c879c2cdae5c16608" doesn't exist dependency "clientsession-0.4.0.3-83420d6960f048ed87e049bcfa4d3d35" doesn't exist dependency "neither-0.1.0-50e3e802c117062181b91d4cbd45270b" doesn't exist dependency "wai-0.2.2-11adeb24d79e447264a1c6aa73a257e8" doesn't exist There are problems in package xss-sanitize-0.2.2: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package web-routes-0.23.0: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package wai-extra-0.2.4: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist dependency "wai-0.2.2-11adeb24d79e447264a1c6aa73a257e8" doesn't exist dependency "zlib-bindings-0.0.0-c2a6f489bd57d072e884afc1d6466b99" doesn't exist There are problems in package snap-server-0.2.11: dependency "cereal-0.3.0.0-835aef1b61feb29c879c2cdae5c16608" doesn't exist dependency "monads-fd-0.1.0.2-8e71857db7c17ae96ca5bff72f20d9fa" doesn't exist There are problems in package snap-core-0.2.11: dependency "cereal-0.3.0.0-835aef1b61feb29c879c2cdae5c16608" doesn't exist dependency "monads-fd-0.1.0.2-8e71857db7c17ae96ca5bff72f20d9fa" doesn't exist There are problems in package pureMD5-2.1.0.2: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist dependency "cereal-0.3.0.0-835aef1b61feb29c879c2cdae5c16608" doesn't exist There are problems in package persistent-0.3.0.1: dependency "neither-0.1.0-50e3e802c117062181b91d4cbd45270b" doesn't exist There are problems in package hsx-0.7.0: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package HStringTemplate-0.6.5: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package HSlim-0.1: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package hint-0.3.3.0: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package haskeline-0.6.3.1: dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package happstack-state-0.5.0.2: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist dependency "happstack-data-0.5.0.2-80c87686add000961445ac7ad8f41385" doesn't exist dependency "happstack-util-0.5.0.2-781b128492ee5ce69eb3c01f6e6a02bb" doesn't exist There are problems in package happstack-ixset-0.5.0.2: dependency "happstack-data-0.5.0.2-80c87686add000961445ac7ad8f41385" doesn't exist dependency "happstack-util-0.5.0.2-781b128492ee5ce69eb3c01f6e6a02bb" doesn't exist There are problems in package happstack-0.5.0.2: dependency "happstack-data-0.5.0.2-80c87686add000961445ac7ad8f41385" doesn't exist dependency "happstack-server-0.5.0.2-9d48ec66664b8dd67d495020314c5d2b" doesn't exist dependency "happstack-util-0.5.0.2-781b128492ee5ce69eb3c01f6e6a02bb" doesn't exist dependency "utf8-string-0.3.6-02c7018b15768d3d72b99557d0f847ff" doesn't exist There are problems in package crypto-api-0.1.2.4: dependency "cereal-0.3.0.0-835aef1b61feb29c879c2cdae5c16608" doesn't exist There are problems in package bytestring-show-0.3.3: dependency "binary-0.5.0.2-0da250ded3b79a6e76d15de8e7ffc885" doesn't exist There are problems in package attoparsec-iteratee-0.1.1: dependency "monads-fd-0.1.0.2-8e71857db7c17ae96ca5bff72f20d9fa" doesn't exist There are problems in package regex-compat-0.93.1: dependency "regex-posix-0.94.2-0a3c1e41d8c2d26547372e229b3f776c" doesn't exist There are problems in package haskell-platform-2010.2.0.0: dependency "regex-posix-0.94.2-0a3c1e41d8c2d26547372e229b3f776c" doesn't exist The following packages are broken, either because they have a problem listed above, or because they depend on a broken package. pandoc-1.6 zip-archive-0.1.1.6 url-2.1.2 filestore-0.3.4.3 happstack-server-0.5.0.2 happstack-data-0.5.0.2 feed-0.3.7 SHA-1.4.1.3 hashed-storage-0.5.3 yesod-0.6.0.2 xss-sanitize-0.2.2 web-routes-0.23.0 wai-extra-0.2.4 snap-server-0.2.11 snap-core-0.2.11 pureMD5-2.1.0.2 persistent-0.3.0.1 hsx-0.7.0 HStringTemplate-0.6.5 HSlim-0.1 hint-0.3.3.0 haskeline-0.6.3.1 happstack-state-0.5.0.2 happstack-ixset-0.5.0.2 happstack-0.5.0.2 crypto-api-0.1.2.4 bytestring-show-0.3.3 attoparsec-iteratee-0.1.1 regex-compat-0.93.1 haskell-platform-2010.2.0.0 ConfigFile-1.0.6 MissingH-1.1.0.3 hsp-0.5.2 HJScript-0.5.0

5 9

Re: [Haskell-cafe] Haskell function help
by Daniel Fischer 01 Feb '11

01 Feb '11

Just a few further remarks, - partition requires the import of Data.List - with an import of Data.Maybe, assign can be much shorter stated as assign (atom,value) formula = catMaybes (map (assignClause (atom,value)) formula)

1 0

Splittable random numbers
by Simon Peyton-Jones 01 Feb '11

01 Feb '11

Hi Cafe A while back there was a thread<http://www.mail-archive.com/haskell-cafe@haskell.org/msg79633.html> about a good implementation of a (pseudo) random number generator with a good "split" operation. There's lots of material on generators that generate a linear sequence of random numbers, but much less on how to generate a tree of random numbers, which is what Haskell's System.Random API requires. I happened to meet Burton Smith recently, who wrote some early papers about this stuff (eg "Pseudo random trees in Monte-Carlo<http://portal.acm.org/citation.cfm?id=1746034>"), so I asked him. His reply is below, along with some follow-up comments from his colleagues Tolga Acar and Gideon Yuval. The generator uses crypto functions, so it's probably more computationally expensive than common linear-sequence generators, but in exchange you get robust splitting. Does anyone feel like taking the idea and turning it into a Haskell library? (Or even a Haskell Wiki page?) I'm taking the liberty of cross-posting to the libraries list. Simon From: Burton Smith Sent: Tuesday, November 02, 2010 3:58 PM To: Simon Peyton-Jones Cc: Gideon Yuval (Gideon Yuval); Tolga Acar Subject: Random number generation With some help from Gideon and Tolga, I think the solution to the "arbitrary tree of random numbers problem" is as follows: The generator G is a pair comprising a crypto key G.k and an integer counter (the "message") G.c. The (next G) operation returns a pair: 1. a random integer r obtained by encrypting G.c with G.k, and 2. a new generator G' such that G'.k = G.k and G'.c = G.c + 1. The (split G) operation is similar, returning the same G', except that instead of returning a random integer r it returns a third generator G'' such that G''.k = r and G''.c = 0. A suitable block cipher system might be 128-bit AES (Rijndael). Unencumbered implementations exist in a variety of languages, and performance is pretty good and will improve dramatically as hardware support improves. I'd pick both crypto key size and the size of the result r to be 128 bits, and employ a 64 bit counter c. Other crypto options exist. From: Simon Peyton-Jones Sent: Wednesday, November 03, 2010 3:11 AM To: Burton Smith; Gideon Yuval (Gideon Yuval) Cc: Tolga Acar; Simon Peyton-Jones Subject: RE: Random number generation Burton, Gideon, Tolga Aha, that's interesting. I'd never seen a random number generator based on crypto, but it seems like an attractive idea. As I understand it, successive calls to 'next' will give you encrypt(0), encrypt(1), encrypt(2), encrypt(3),.... Is this standard? Does it have provably good randomness properties, (cycle length, what else?) like other RNGs? Or does it simply seem very plausible? Can I send it round to the Haskell mailing list, in the hope that someone will turn the idea into a library? (Ideally I'd like to make claims about the randomness properties in doing so, hence my qns above.) From: Gideon Yuval (Gideon Yuval) Sent: Wednesday, November 03, 2010 7:15 AM To: Simon Peyton-Jones; Burton Smith Cc: Tolga Acar Subject: RE: Random number generation As long as the key, and the non-counting part of the counter, are kept" secret", anyone who can distinguish these pseudorandoms from real random, in less than 2^128 steps, has a nice paper for crypto-2011 (this is known as "provable security") concerning a weakness in AES128. One exception: real randoms have a birthday paradox; the pseudorandoms suggested do not. If you care, you can: (1) Limit the counter to 2^32 steps (paradox has 2^-64 probability) or even 2^16 (2^-96), then rekey; or (2) XOR 2 such encrypted counters, with different keys; or (3) XOR 3 successive values for the same counter (just possibly cheaper; top-of-head idea). More hard-core: swap the position of key & message: encrypting a constant "secret" with 1,2,3,4.... Gives pseudorandoms with no birthday paradox. From: Tolga Acar Sent: 03 November 2010 15:50 To: Gideon Yuval (Gideon Yuval); Simon Peyton-Jones; Burton Smith Subject: RE: Random number generation Simon, The general idea is not really that new in the crypto area with constraints Gideon describes, of course. That is typically called a PRNG - Pseudo Random Number Generator, or in another parlance, Deterministic Random Bit Generators (DRBG). The DRBG constructions based on hash functions and block ciphers are even standardized in NIST publication SP800-90 (even though I may not recommend every one of them). As for the construction below, that is based on the AES block cipher, that essentially takes advantage of the PRP (Pseudo Random Permutation) property of the AES block cipher, as each block cipher ought to be. So, as Gideon outlines below, if you fix the key, the PRP gives you a random-looking (or, in other terms, indistinguishable from random) output that no one without the secret key and the "state" can generate or easily predict. Assuming an ideal cipher (and AES is a close approximation to it), the probability is believed to be the birthday paradox - no counterexample or a proof exists without assumptions; so we stick to the birthday bound. There ought to be papers on this somewhere. If not, that condensed information is spread across many papers and is part of the crypto folklore, I'd say. From: Burton Smith Sent: 03 November 2010 19:03 To: Simon Peyton-Jones Cc: Gideon Yuval (Gideon Yuval); Tolga Acar Subject: RE: Random number generation Just two points of further clarification: 1. All PRNGs used in the technical computing space fail the birthday paradox criterion (i.e. have full period), so we really need not worry about this. Also, there are other mitigating factors, e.g. suppose we are using the PRNG to generate pseudorandom residues mod n << 2^128; the paradox is happily present there. 2. The big innovation in this scheme is that the rekeying operation done by split creates a new generator with independence guaranteed by "provable security" in the sense Gideon mentioned - if someone can find something nonrandom in the correlation between G' and G'', say, then it amounts to a weakness in AES128 and is publishable. So it's yet another example of reducibility, common in our field: "if you can easily transform a known/famous hard problem P into this other problem Q, Q must be hard".

11 19