April 2011 - Haskell-Cafe

HXT and xhtml page encoded in cp1251
by Dmitry V'yal 19 Apr '11

19 Apr '11

Greetings, I'm writing a small webcrawler. Usually I used tagsoup for such tasks but this time I decided to give hxt a try. Unfortunately, I ran into the troubles with character encodings. The site I'm targeting uses cp1251, which is the one of the most popular among sites in Russian. Pages contain the following meta tag <meta http-equiv="content-type" content="text/html; charset=windows-1251" /> The readDocument arrow fails with the following message: fatal error: encoding scheme not supported: "WINDOWS-1251" Can someone suggest a workaround for my use case? Best regards, Dmitry

3 2

Painless parallelization.
by Grigory Sarnitskiy 19 Apr '11

19 Apr '11

Hello, I'm searching a way to benefit from modern hardware in my programs. I consider parallel programing to be actually easier than sequential one. Parallel computation allows to avoid sophisticated algorithms that were developed to gain performance on sequential architecture. It should also allow to stop bothering about using immutable objects --- immutable parallel arrays should be as fast as mutable ones, right? (provided there is enough cores) So what are the options to write a pure functional parallel code with the level of abstraction I used in Haskell? So far I've found Data Parallel Haskell for multicore CPU's and Data.Array.Accelerate for GPU's. It would be nice to have something at the release state, rather than some beta.

3 2

An example of enumerator processing some data between input and output
by Paul Sujkov 19 Apr '11

19 Apr '11

Hi haskellers, I played a bit with the enumerator package, and I'm quite stuck with the question how to duplex data to two (or more) consumers using combinators from xml-enumerator (for example) package. What I mean is: main = withFile "out.xml" WriteMode $ \h -> parseFile "in.xml" decodeEntities $ (joinI $ renderText $$ iterHandle h) >> (force "data required" parseData) where parseData is a simple xml-enumerator parser. Combining consumers in such a way I can get text being output to the file "out.xml" (like in the example given) or parsed with parseData (if I switch the order of the consumers), but not both. Can anybody tell me how to make a pipe (input -> process -> output) to have text both parsed and then put back to the file? While pretty straightforward with the arrow approach, it doesn't seem obvious to me with the iteratees :( -- Regards, Paul Sujkov

1 1

Stack overflow in simple code with getStdRandom / randomR (GHC)
by Volker Stolz 19 Apr '11

19 Apr '11

The following three-liner creates a stack overflow (on my machine, MacOS), and I'm a bit puzzled as to why: > import System.Random > > main = do > mapM (const (getStdRandom (randomR (0, 50000::Int)))) [0..10000000] botanix:~ stolz$ ./a.out Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. Yes, the list is quite long, but somehow I'd expected mapM to chug slowly along...printing "Hello World" doesn't create a stack overflow either, after all. My Haskell-foo has become a bit rusty, but I was wondering where I am missing a point or two here (and I couldn't find the correct profiler incantation that would give me more than a big black blob for the main-CAF). GHC is 6.12.3 on MacOS. Cheers, Volker

2 2

ANNOUNCE: cereal-0.3.1.0
by Trevor Elliott 19 Apr '11

19 Apr '11

Hi Everyone, I'm proud to announce version 0.3.1.0 of the cereal binary-(de)serialization library [1]! This version includes some new functionality contributed by Lemmih, that adds support for partial parses in the Get monad. The changes don't modify the API presented in 0.3.0.0, instead adding a new runPartialGet function for the Get monad when partial parses are desired. [1] http://hackage.haskell.org/package/cereal-0.3.1.0

1 0

Another(!) PhD Position at Strathclyde
by Conor McBride 19 Apr '11

19 Apr '11

Hot on the heels of Patricia Johann's advertisement, here's another PhD Position in the Mathematically Structured Programming Group, Deparment of Computer and Information Sciences at the University of Strathclyde to be supervised by Dr. Conor McBride and Prof. Neil Ghani on something related to Designing Precision with Dependent Types. We invite applications for one PhD position within the Mathematically Structured Programming group at the University of Strathclyde. The group comprises Prof. Neil Ghani, Dr. Patricia Johann, Dr. Conor McBride, Dr. Peter Hancock, Dr. Robert Atkey, and five PhD students. The PhD project involves THEORETICAL and PRACTICAL issues in FUNCTIONAL PROGRAMMING with DEPENDENT TYPES. Dependent type systems allow us to construct precise variations on general-purpose datatypes which address the specific needs of particular programming problems, thus opening a new "precision" axis in the design space of programs and data. We seek equipment to help programmers explore this axis, determining what is needed to shift the level of precision at which existing functions operate and which properties are guaranteed in return. The project thus represents an opportunity to study mathematical abstractions with a concrete engineering motivation. The PhD position is for 3 years, starting in October 2011. The position is a fully-funded post for a UK or EU student, and includes coverage both of fees and an EPSRC-level stipend for each of the three years. More information about the department is available at http://www.strath.ac.uk/cis The University of Strathclyde (http://www.strath.ac.uk) is slap bang in the middle of Glasgow, a thronging metropolis of wit and daring. Scotland is a hive of activity in Computer Science: we have active collaborations with researchers at Edinburgh, Heriot-Watt, Glasgow and St. Andrews. This is the time and the place to make an impact. Requests for further information and other informal enquiries can be sent to: Conor McBride conor at cis.strath.ac.uk Please get in touch as soon as you can. We hope to appoint in early May.

1 0

Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms
by caseyh＠istar.ca 19 Apr '11

19 Apr '11

Just tripped over this: Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms Folds and unfolds are at the heart of the algebra of programming. They allow the cognoscenti to derive and manipulate programs rigorously... Ralf Hinze Lecture Notes in Computer Science, 2010, Volume 6120, Mathematics of Program Construction, Pages 195-228

1 0

Re: [Haskell-cafe] [Haskell] select(2) or poll(2)-like function?
by Henning Thielemann 19 Apr '11

19 Apr '11

On Sun, 17 Apr 2011, Matthias Kilian wrote: > is there something like select(2) or poll(2) available in the > standard (HP) libraries? I hoogled around a little bit but didn't > find anything. (Something like this will be crucial for networking > stuff listening on v4 and v6 sockets at the same time) A very basic thing to start from: http://code.haskell.org/~thielema/poll/ It is still subject to change. We are planning to use this in alsa-seq.

1 0

Errata for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell
by caseyh＠istar.ca 19 Apr '11

19 Apr '11

-- Errata for "Pearls of Functional Algorithm Design" by Richard Bird, -- 2010, page 25 #Haskell -- I don't like this solution it suffers from "indexitis" which -- Bird talks about in the chapter on Sudoku. -- I can see why lists are liked, they avoid "indexitis" at -- the cost of chopping and concatenating them. -- One of the advantages of functional programming is supposed to be less bookkeeping. smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a smallest k (xa,ya) = ~~~~search k (0,m+1) (0,n+1) ~~~~~~~~where ~~~~~~~~(0,m) = bounds xa ~~~~~~~~(0,n) = bounds ya ~~~~~~~~search k (lx,rx) (ly,ry) ~~~~~~~~~~~~| lx == rx = ya ! (k+ly) ~~~~~~~~~~~~| ly == ry = xa ! (k+lx) ~~~~~~~~~~~~| otherwise = case (xa ! mx < ya ! my, k <= mx-lx+my-ly) of ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(True, True) -> search k (lx,rx) (ly,my) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(True, False) -> search (k-(mx-lx)-1) (mx+1,rx) (ly,ry) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(False, True) -> search k (lx,mx) (ly,ry) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(False, False)-> search (k-(my-ly)-1) (lx,rx) (my+1,ry) ~~~~~~~~~~~~~~~~~~~~~~~~~~where ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~mx = (lx+rx) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~my = (ly+ry) `div` 2

1 0

A paper relating to Data.Set and Data.Map
by Kazu Yamamoto 19 Apr '11

19 Apr '11

Hello libraries and cafe, We (Hirai and I) would like to tell you our paper relating to Data.Set and Data.Map. "Balancing Weight-Balanced Trees" is now accepted and will appear in Journal of Functional Programming. The camera-ready version of the paper is available from: http://www.mew.org/~kazu/proj/weight-balanced-tree/ Please recall that Taylor Campbell reported a bug of Data.Map in last Summer. In some cases, the balance of Data.Map is broken after delete operations. This triggered our research. http://article.gmane.org/gmane.comp.lang.haskell.libraries/13444 Though Data.Set/Data.Map are based of a variant Weight-Balanced tree by Adams, we target the original Weight-Balanced tree by Nievergelt and Reingold. They are parameterized algorithms and the difference of two algorithms is quite small. But the original has smaller conditions which are gentle for proof. We identified the valid area of two parameters of the original Weight-Balanced tree and showed <3,2> is only one integer solution. Soundness is proved in Coq and completeness is verified with four algorithms to generate counterexamples for the outside of the valid area. "wttree.scm" of MIT/GNU Scheme and slib have already incorporated our fixes. When I offered our fixes to MIT/GNU Scheme, Taylor Campbell appeared again. I understand that he is an MIT/GNU Scheme guy and found the bug of Data.Map when re-implementing "wttree.scm" consulting Data.Map. :-) We think it's Haskell community turn now. Data.Set/Data.Map are still based on the variant whose soundness is not proved yet. If interested, let's discuss whether or not we should replace the variant with the original in Data.Set/Data.Map. We guess that Milan Straka, a big contributer of the container package, has his opinion. We welcome opinions from other people, two. Regards, --Kazu

2 1