March 2011 - Haskell-Cafe

ANN: cabal-dev-0.7.4.0
by Rogan Creswick 04 Mar '11

04 Mar '11

We're happy to announce that cabal-dev-0.7.4.0 is now on hackage. We strongly suggest that everyone upgrade to this release, since this release specifically addresses changes in Cabal-1.10 and newer, which the latest cabal-install now uses. The ticket for the bug is here, for anyone interested: https://github.com/creswick/cabal-dev/issues/2 --Rogan

1 0

ANN: Version 0.14 of dataenc, version 0.5 of omnicodec
by Magnus Therning 03 Mar '11

03 Mar '11

I've just uploaded a new version of dataenc to hackage[1]. It contains a large change to the API. The old, rather simplistic, lazy API has been removed. It has been replaced by an API based on incremental encoding/decoding. This should make the library easier to use together with left-fold enumerators such as enumerator[2] and iteratee[3]. It's accompanied by a release of omnicodec[4] which makes use of the modified API of dataenc. /M [1] http://hackage.haskell.org/package/dataenc [2] http://hackage.haskell.org/package/enumerator [3] http://hackage.haskell.org/package/iteratee [4] http://hackage.haskell.org/package/omnicodec -- Magnus Therning OpenPGP: 0xAB4DFBA4 email: magnus(a)therning.org jabber: magnus(a)therning.org twitter: magthe http://therning.org/magnus Most software today is very much like an Egyptian pyramid with millions of bricks piled on top of each other, with no structural integrity, but just done by brute force and thousands of slaves. -- Alan Kay

1 0

A simple attoparsec question
by Robert Clausecker 03 Mar '11

03 Mar '11

Hi Haskellers! I'm currently trying to write an assembler for Knuths MMIXAL language. Currently, I'm writing the parser using attoparsec, and have one question: In MMIXAL, a string literal starts with a ", followed by an arbitrary amount of arbitrary characters excluding the newline character and finished with another ". For example: "Hello, World!" is a string, "ſ" is a string too, but "\n" (\n is a newline) isn't. Here's the parser, which parses a s tring and other kinds of constants: parseConstant = Reference <$> try parseLocLabel <|> PlainNum <$> decimal <|> char '#' *> fmap PlainNum hexadecimal <|> char '\'' *> (CharLit <$> notChar '\n') <* char '\'' <|> try $ (char '"' *> (StringLit . B.pack <$> manyTill (notChar '\n') (char '"'))) <?> "constant" The problem is, that attoparsec just silently fails on this kind of strings and tries other parsers afterwards, which leads to strange results. Is there a way to force the whole parser to fail, even if there's an alternative parser afterwards? I hope, you understand my question. Yours, Robert Clausecker

5 4

Re: [Haskell-cafe] Haskell IDE
by Michal Konečný 03 Mar '11

03 Mar '11

On Thu, Mar 3, 2011 at 9:05 AM, Hauschild, Klaus (EXT) <klaus.hauschild.ext(a)siemens.com> wrote: > whats your Haskell IDE of choise? Currently I use leksah. Is the EclipseFP > Plugin for Eclipse a real alternative? I use EclipseFP 2.0.2 on a few fairly large projects and am overall very happy with it despite a few flaws, eg: - it currently signals an error in source code files with non-latin-1 unicode characters - it does not build projects that include C files - I find it fairly slow on very large projects as it continuously rebuilds them as you type, but it is not as slow as this kind of approach may seem to imply I especially appreciate: - how well it highlights compiler errors - the outline of a module I do not use code completion beyond the generic Alt-/, so I do not have an opinion on how well this is supported in eclipsefp. Michal -- |o| Michal Konecny <mikkonecny(a)gmail.com> |o| http://www-users.aston.ac.uk/~konecnym/ |o| office: (+42) (0)121 204 3462 |o| PGP key http://www-users.aston.ac.uk/~konecnym/ki.aow

1 0

Terminal library : which ?
by Permjacov Evgeniy 03 Mar '11

03 Mar '11

What terminal library you will recomedn? Requirements: crossplatform (win/lin), with direct (i.e. with line/column number pair) cursor positioning and possybly direct symbol output. MUST provide function to get terminal dimensions. (could not find one).

2 1

Re: [Haskell-cafe] Project structure
by John Lato 03 Mar '11

03 Mar '11

> > From: "Hauschild, Klaus (EXT)" > > Hi Haskellers, > > is there a recommended structure for Haskell projects. I like the Maven way > ( > http://maven.apache.org/guides/introduction/introduction-to-the-standard-di…) > for Java projects. How to separate productive from test code, how to > separate source code from other resources? > I like the way the Snap-framework is organized: ./ ./src/ ./test/ ./test/data/ ./test/suite/ ./snap-framework.cabal Then if you have e.g. ./src/Snap/Types.hs the tests go in ./tests/suite/Snap/Types/Tests.hs Basically "src" is for all productive code, "test" is for tests of that code. I sometimes add these to the top level: ./tools ./resources "tools" is for code generators or similar tools that auto-generate stuff to go in ./src which cabal doesn't know about. "resources" would be data files, images, or similar resources that get bundled with the distribution. John L.

1 0

Haskell KMP(Knuth-Morris-Pratt) algorithm
by larry.liuxinyu 03 Mar '11

03 Mar '11

Hi, I read about some KMP implementation in Haskell including: [1] Richard Bird. ``Pearls of Functional algorithm design'' [2] http://twan.home.fmf.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell.details [3] http://www.haskell.org/haskellwiki/Runtime_compilation [4] LazyString version [1] builds a infinite lazy state transfer trees, while [3] uses index to build overlap table. I created a version which isn't as efficient as in [1]. Just for fun: failure :: (Eq a)=> ([a], [a]) -> ([a], [a]) failure ([], ys) = ([], ys) failure (xs, ys) = fallback (init xs) (last xs:ys) where fallback as bs | as `isSuffixOf` xs = (as, bs) | otherwise = fallback (init as) (last as:bs) kmpSearch2 :: (Eq a) => [a] -> [a] ->[Int] kmpSearch2 ws txt = snd $ foldl f (([], ws), []) (zip txt [1..]) where f (p@(xs, (y:ys)), ns) (x, n) | x == y = if ys==[] then ((xs++[y], ys), ns++[n]) else ((xs++[y], ys), ns) | xs == [] = (p, ns) | otherwise = f (failure p, ns) (x, n) f (p, ns) e = f (failure p, ns) e The function failure just follows the idea that in case (xs, ys) fails matching some letter c in text, where xs++ys = pattern and c!= head ys, it means we must fallback to (xs', ys') so that xs' = longest { s: s is prefix of xs AND s is suffix of xs } The bad thing is that failure can't memorize what it has compute before, for example, as pattern = "ababc" and we fails at ("abab", "c"), then we call function failure to get the new one as ("ab", "abc"). After several matches, we fails again at ("abab", "c"), failure can't just return ("ab", "abc") what it has been compute already. It has too do the same work again. Function f inside kmpSearch2 is in fact a state-transfer function. If we try to use some data structure (for example tree) to memorize the results which failure function calculated, we can finally reach to the idea in [1]. -- LIU http://sites.google.com/site/algoxy/

1 1

Re: [Haskell-cafe] Rank-2 types in classes
by oleg＠okmij.org 03 Mar '11

03 Mar '11

Yves Pare`s wrote: > I'm working on a library which aims to be a generic interface for 2D > rendering. To do that, one of my goals is to enable each implementation of > this interface to run in its own monad (most of the time an overlay to IO), > thus giving me the following class > > class (Monad (IM i x)) => Impl i x where > data IM i x :: * -> * > > (where IM means Implementation Monad) > > I would like to write something like : > > class (forall x. Monad (IM i x)) => Impl i where > data IM i :: * -> * -> * It is not clear if the class constraint is really needed. As an aside, a class constraint is perhaps a bit of mis-feature of type classes: it sure improves convenience by making signatures shorter. But it isn't really necessary. Perhaps there are other, better ways of achieving the convenience (the constraint alias proposal comes to mind). If we drop the class constraint, we can move Monad (IM i x) as the constraint on specific methods of the Impl class. The implicit uiniversal quantification on x is well allowed then. For example: > class Impl (i :: * -> *) where > data IM i :: * -> * -> * > foo :: Monad (IM i x) => Int -> IM i x Int > bar :: Monad (IM i x) => IM i x Int -> IM i x Bool > cast :: IM i x a -> IM i y a > > data Window > > instance Impl IO where > newtype IM IO x a = IMIO (IO a) > foo = IMIO . return > bar (IMIO x) = IMIO (fmap (> 42) x) > cast (IMIO x) = IMIO x > > test :: (Monad (IM i Window), Impl i) => IM i Window Int -> IM i x Bool > test = cast . bar Perhaps this isn't what you had in mind; I more elaborate example would help then.

2 1

Where to put a library
by Richard Senington 03 Mar '11

03 Mar '11

Hi all, I am working on ways to implement local search meta-heuristics in Haskell. I need various test problems to experiment on, and this has resulted in me building various file parsers and data structures for these. Currently I have versions for SAT, TSP and a couple of more private file formats. The file parsers are designed to process files coming out of the TSPLIB and SATLIB repositories. I also want to extend this to cover scheduling and timetabling example problems. Since these are all related I was going to try to put them together into a single library and post them to Hackage, but I am not sure what to put them under. I assume that Data is for data structures, which is not quite right. I was thinking about something like Problems. as a top level point in a hierarchy. Does anyone have any other suggestions, as this seems a little odd as a name to me? Alternatively, does this already exist and I have just missed it? Cheers RS

3 2

Learning list filtering using puzzles
by Karthick Gururaj 03 Mar '11

03 Mar '11

Hi all, I'm very new to Haskell, having started earlier this week. This is my second attempt after two years :) Currently, I can do simple list processing/recursion/functions. I'm using GHC on Ubuntu. I decided to use puzzles as a way to explore list filtering. For example, while "normal" solution for solving a quadratic is to compute the solution algebraically, I tried: solvequad :: Int -> Int -> Int -> [Int] solvequad a b c = [x | x <- [1..10000], a*x*x + b*x + c == 0] This works well, of course assuming the roots are in the given integer range. Next, to solve the puzzle: "A stone weighing 40 kg falls from a certain height and is split into four pieces. With the help of these four pieces, one can weigh any quantity from one kg to 40 kg by using these in a scale (both plates of the scale can be used for placing any stone pieces at a time). Find the weight of each piece." I tried: solvepuzzle = [(a,b,c,d) | a <- [1..40], b <- [a..40], c <- [b..40], d <- [c..40], a+b+c+d == 40, sort [p*a + q*b + r*c + s*d | p <- [-1,0,1], q <- [-1,0,1], r <- [-1,0,1], s <- [-1,0,1], p*a+q*b+r*c+s*d > 0] == [1..40]] It works, but I'm not too happy with the last constraint.. Is there a better way to express: "..one can weigh any quantity from 1kg to 40 kgs.." ? A more interesting candidate - considering the previous ones can be also solved with a language like C easily: consider the well know honestans/swindle-cats puzzle: "there are two gate keepers guarding two doors - one that leads to hell and the other to heaven. One of these keepers always speaks the truth and the other always lies (and will only answer questions that permit a "yes" or "no" for answer). We don't know who is the honest one. If allowed to ask one question to one of the keepers, what would you ask to find out which is the gate to heaven?" I'm trying to see how to formulate this in a way Haskell can lead me to a solution.. This is where I'm at now (in "psedo" Haskell code). --- Oracle knows answers to all questions and will answer truthfully oracle :: Question -> Bool -- Ignoring the definition for now --- invOracle knows answers to all questions but will always lie invOracle :: Question -> Bool invOracle x = not (oracle x) As far as the answer we are looking for, the truth val of "does the first door lead to heaven?" is what we want. I represent this Question as 'q'. So in my notation: keeper1 q - ask the question to keeper 1 oracle q - ask oracle the question (not . oracle) q - ask oracle the question, and then negate it (keeper1 . keeper2) q - Ask keeper 1, "Suppose I ask keeper 2 the question 'q', what would he say?" .. etc Suppose there is a way to generate "all possible questions" that can be asked to the two gate-keepers.. a generator function (say "gen") that takes three parameters: keeper1, keeper2 and q and returns a list of questions (like the examples above). The solution(s) to the puzzle is then (something like..): [x | keeper1 <- [oracle, invOracle], keeper2 <- [oracle, invOracle], keeper1 /= keeper2, x <- gen keeper1 keeper2 q, x q == oracle q] The answer I know is "not (keeper1 (keeper2 q))". Thinking through the puzzle now, I realized even "keeper1 (keeper1 q)" can be an answer. How would I go about defining such a generator function? I'm not looking for a detailed solution, but hints what I can look up/refer. Any other comments on the approach above would be gratefully received :) Cheers, Karthick

1 0