March 2013 - Haskell-Cafe

Re: [Haskell-cafe] attoparsec and backtracking
by oleg＠okmij.org 19 Mar '13

19 Mar '13

Wren Thornton wrote: > I had some similar issues recently. The trick is figuring out how to > convince attoparsec to commit to a particular alternative. For example, > consider the grammar: A (B A)* C; where if the B succeeds then we want to > commit to parsing an A (and if it fails then return A's error, not C's). Indeed. Consider the following (greatly simplified) fragment from the OCaml grammar | "let"; r = opt_rec; bi = binding; "in"; x = expr LEVEL ";" -> | "function"; a = match_case -> | "if"; e1 = SELF; "then"; e2 = expr LEVEL "top"; "else"; e3 = expr LEVEL "top" -> ... | "false" -> | "true" -> It would be bizarre if the parser -- upon seeing "if" but not finding "then" -- would've reported the error that `found "if" when "true" was expected'. Many people would think that when the parser comes across "if", it should commit to parsing the conditional. And if it fails later, it should report the error with the conditional, rather than trying to test how else the conditional cannot be parsed. This is exactly the intuition of pattern matching. For example, given > foo ("if":t) = case t of > (e:"then":_) -> e > foo _ = "" we expect that foo ["if","false","false"] will throw an exception rather than return the empty string. If the pattern has matched, we are committed to the corresponding branch. Such an intuition ought to apply to parsing -- and indeed it does. The OCaml grammar above was taken from the camlp4 code. Camlp4 parsers http://caml.inria.fr/pub/docs/tutorial-camlp4/tutorial002.html#toc6 do pattern-matching on a stream, for example # let rec expr = parser [< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if" | [< 'Let; 'Ident x; 'Equal; x = expr; 'In; y = expr >] -> "let" and raise two different sort of exceptions. A parser raises Stream.Failure if it failed on the first element of the stream (in the above case, if the stream contains neither If nor Let). If the parser successfully consumed the first element but failed later, a different Stream.Error is thrown. Although Camlp4 has many detractors, even they admit that the parsing technology by itself is surprisingly powerful, and produces error messages that are oftentimes better than those by the yacc-like, native OCaml parser. Camlp4 parsers are used extensively in Coq. The idea of two different failures may help in the case of attoparsec or parsec. Regular parser failure initiates backtracking. If we wish to terminate the parser, we should raise the exception (and cut the rest of the choice points). Perhaps the could be a combinator `commit' that converts a failure to the exception. In the original example A (B A)* C we would use it as A (B (commit A))* C.

1 0

ANNOUNCE: HaTeX-3.5 - New version of the LaTeX library
by Daniel Díaz Casanueva 19 Mar '13

19 Mar '13

Hi readers! A new version of HaTeX has just been released. More math symbols and utilities and a new attoparsec-based parser. This new version also includes a new matrix renderer. A summary of the changes: http://deltadiaz.blogspot.com/2013/03/hatex-35.html The package in Hackage: http://hackage.haskell.org/package/HaTeX-3.5 For those who don't know, HaTeX is a combinator library for LaTeX code. Read more in the manual: https://github.com/downloads/Daniel-Diaz/HaTeX-Guide/HaTeX-Guide.pdf I recommend to HaTeX users to upgrade to this new version. Good luck, Daniel Díaz. -- E-mail sent by Daniel Díaz Casanueva let f x = x in x

2 1

Workshop on Generic Programming
by Jacques Carette 18 Mar '13

18 Mar '13

Dear list subscribers, apologies if you receive multiple copies of this CFP. ====================================================================== CALL FOR PAPERS WGP 2013 9th ACM SIGPLAN Workshop on Generic Programming Boston, Massachusetts, USA Saturday, September 29th, 2013 http://www.wgp-sigplan.org/2013 Co-located with the International Conference on Functional Programming (ICFP 2013) ====================================================================== Goals of the workshop --------------------- Generic programming is about making programs more adaptable by making them more general. Generic programs often embody non-traditional kinds of polymorphism; ordinary programs are obtained from them by suitably instantiating their parameters. In contrast with normal programs, the parameters of a generic program are often quite rich in structure; for example they may be other programs, types or type constructors, class hierarchies, or even programming paradigms. Generic programming techniques have always been of interest, both to practitioners and to theoreticians, and, for at least 20 years, generic programming techniques have been a specific focus of research in the functional and object-oriented programming communities. Generic programming has gradually spread to more and more mainstream languages, and today is widely used in industry. This workshop brings together leading researchers and practitioners in generic programming from around the world, and features papers capturing the state of the art in this important area. We welcome contributions on all aspects, theoretical as well as practical, of * generic programming, * programming with (C++) concepts, * meta-programming, * programming with type classes, * programming with modules, * programming with dependent types, * type systems for generic programming, * polytypic programming, * adaptive object-oriented programming, * component-based programming, * strategic programming, * aspect-oriented programming, * family polymorphism, * object-oriented generic programming, * implementation of generic programming languages, * static and dynamic analyses of generic programs, * and so on. Program Committee ----------------- Jeremiah Willcock (co-chair), Indiana University Jacques Carette (co-chair), McMaster University Florian Rabe, Jacobs University Bremen Emilie Balland, INRIA Bordeaux Jeremy Siek, University of Colorado, Boulder Gabriel Dos Reis, Texas A&M University Christophe Raffalli, Savoie University Anya Helene Bagge, Universitetet i Bergen Tiark Rompf, Ecole Polytechnique Federale de Lausanne Andreas Abel, Ludwig-Maximilians-Universitat Munchen Edward Kmett, S&P Capital IQ William Cook, University of Texas, Austin Proceedings and Copyright ------------------------- We plan to have formal proceedings, published by the ACM. Authors must transfer copyright to ACM upon acceptance (for government work, to the extent transferable), but retain various rights (http://www.acm.org/publications/policies/copyright_policy) Authors are encouraged to publish auxiliary material with their paper (source code, test data, etc.); they retain copyright of auxiliary material. Submission details ------------------ Deadline for submission: Friday 2013-06-14 Notification of acceptance: Wednesday 2013-07-11 Final submission due: Tuesday 2013-07-25 Workshop: Sunday 2013-09-28 Papers should be submitted via EasyChair at https://www.easychair.org/conferences/?conf=wgp2013 Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines (two-column, 9pt). The length is restricted to 12 pages. Travel Support -------------- Student attendees with accepted papers can apply for a SIGPLAN PAC grant to help cover travel expenses. PAC also offers other support, such as for child-care expenses during the meeting or for travel costs for companions of SIGPLAN members with physical disabilities, as well as for travel from locations outside of North America and Europe. For details on the PAC program, see its web page (http://www.sigplan.org/PAC.htm) History of the Workshop on Generic Programming ---------------------------------------------- Earlier Workshops on Generic Programming have been held in * Copenhagen, Denmark 2012 (affiliated with ICFP12), * Tokyo, Japan 2011 (affiliated with ICFP11), * Baltimore, Maryland, US 2010 (affiliated with ICFP10), * Edinburgh, UK 2009 (affiliated with ICFP09), * Victoria, BC, Canada 2008 (affiliated with ICFP), * Portland 2006 (affiliated with ICFP), * Ponte de Lima 2000 (affiliated with MPC), * Marstrand 1998 (affiliated with MPC). Furthermore, there were a few informal workshops * Utrecht 2005 (informal workshop), * Dagstuhl 2002 (IFIP WG2.1 Working Conference), * Nottingham 2001 (informal workshop). There were also (closely related) DGP workshops in Oxford (June 3-4 2004), and a Spring School on DGP in Nottingham (April 24-27 2006, which had a half-day workshop attached). WGP Steering Committee ---------------------- Marcin Zalewski (chair) Bruno Oliveira Jaako Järvi Shin-Cheng Mu Andres Löh Ronald Garcia Magne Haveraaen Tim Sheard Stephanie Weirich

1 0

Improving my implementation of "The Lady Tasting Tea"
by Mark Fredrickson 18 Mar '13

18 Mar '13

Hello, For my first project in Haskell, I thought I would re-implement a statistical problem that I have previously done in R. In his 1925 book, Fisher tells of an experiment in which a lady claims she can tell the difference in cups of tea that have the milk or the tea/water added first (I'm a coffee drinker, so I'm unclear on the actual physical interpretation). To test this claim, Fisher proposes an experiment in which 8 cups are created, with 4 having milk first and 4 having tea first. If the lady can properly label 3 of the 4 milk first cups correctly, should we be suprised? What is the probability that she would get 3 or 4 of the milk first cups correct just due to chance (that is, independently of the actual allocation of milk and tea first)? Fisher shows that these questions can be answered by writing out all the possible ways the 4 milk cups could be allocated (there are 70 such possibilities) and then counting the subset that have 3 or 4 correct according to the lady's guess (there are 17). Therefore the probability of getting 3 or 4 correct just by guessing would occur about 24% of the time. I've implemented this algorithm for problems of arbitrary size, and I'd like some feedback on improving the efficiency of my code: https://gist.github.com/markmfredrickson/5190212 The problem is basically a map-reduce: 1. Create the C(N,K) possible ways the cups could be set up (where N is the total number of cups, and K is the number with milk first) 2. Map a function across them that scores the lady's guess 3. Reduce the set of scores to a p-value (a value between 0 and 1) that indicates what percentage of all possible allocations of milk first would have a score equal to or greater than the lady's guess. My first attempt at profiling indicates that most time is spent in the scoring function, unsurprising as this is in the inner most loop of the algorithm. The generation of all possible combinations is also time consuming. From what I can tell, this implementation is not very efficient from a space perspective. In the long term, I'm interested in using this same basic procedure to solve more interesting statistical problems, so I'm particulary interested in getting feed back on: 1. A good data type for storing the list of treatment allocations (i.e. milk first cups). The current problem calls for binary treatment with no extra data. In the future, my N units may be partitioned into K groups (here K=2), and the score function will require additional data (e.g. each unit will have an outcome measure on a continuous or ordinal scale). In a sense, I'd like to use tuples to hold index values from 1 to N, but I wouldn't necessarily know the tuple size at compile time. The index values would point to an array or similar structure holding the additional data. Some other properties of allocations: - They are always the same size - Order is not important - All values are unique Any standard types fit this description? 2. A better algorithm and perhaps data type for the combinations. The current implementation uses a tree recursion to get the set of all possible combinations. In the future, this set will be too large to enumerate entirely, so I'll need to sample from it. It would be desirable to be able to write `take samples (permute $ combinations total treated)` where the `permute` function (perhaps with a random seed) properly re-orders the combinations. If these goals are supported by a data structure better than a list, I'm very open to using other types to hold the combinations. I would also appreciate any suggestions on making the code more idiomatic or readable. Thanks, -Mark

1 0

How to use the nice test output spit out by test-framework with "cabal test"?
by Alfredo Di Napoli 18 Mar '13

18 Mar '13

Hi guys, I've been wondering for a long time about how to use the nice terminal-base report spit out from test-framework when I type "cabal test". Atm this is my run-of-the-mill cabal setting: test-suite test-all type: exitcode-stdio-1.0 main-is: Main.hs ghc-options: -w -threaded -rtsopts -with-rtsopts=-N hs-source-dirs: tests [...] but this runs tests using the default cabal interface: Linking dist/build/test-all/test-all ... Running 1 test suites... Test suite test-all: RUNNING... Test suite test-all: PASS Test suite logged to: dist/test/opencv-simple-0.1.0.0-test-all.log 1 of 1 test suites (1 of 1 test cases) passed. This is, instead, what I wanted when I type "cabal test" and "cabal install --enable-tests": http://batterseapower.github.com/test-framework/images/example.png is it possible? Thanks in advance, A.

2 1

Some aggregation of Haskell content
by Christopher Done 18 Mar '13

18 Mar '13

Is there a page somewhere that aggregates all of Haskell's community output into one place? As a consumer of Haskell content I neither have the time nor inclination to follow haskell-cafe and other various mailing lists, the reddits, the google+ community, planet haskell, hackage releases, twitter, youtube and whatever other submission places I haven't heard of. I made this page for the Lojban community some years ago: http://jbotcan.org/hub/ Lojban doesn't have much community activity (tho this doesn't include mailing list posts), but Haskell's community is much larger and more active, it would be far more useful. I may write such a page for Haskell content, if not for the community then at least for myself, as I keep missing out on cool things because I didn't happen to check out that particular medium of exchange. For example, even this message will be lost on a thousand people who doesn't follow the mailing list but maybe follows G+ or reddit. Kind of like a Haskell Weekly news, except more like "Haskell news right now or in some adjustable time frame." And the option to toggle between chronological order or categorized. Ciao!

3 3

haskell infrastruture poll
by Alexander V Vershilov 18 Mar '13

18 Mar '13

Ladies and gentlemen! If you happen to be involved in using/developing haskell-powered software you might like to answer our poll on that matter [1]. Thanks in advance! [1] https://docs.google.com/forms/d/1y5WtrCB7O9-jb-2Mzo1MtkToh4O6oY2oBXGkc_Q-cy… -- Alexander

1 0

MVar which can not be null ?
by s9gf4ult 18 Mar '13

18 Mar '13

Hello, I am looking for MVar which can not be null. I need some kind of thread save atomic IO operation like I can do with modifyMVar, but I want this variable always contain some value and never be null. Thanks.

5 5

Optimization flag changing result of code execution
by Azeem -ul-Hasan 18 Mar '13

18 Mar '13

I was trying to solve a computational problem form James P Sethna's book Statistical Mechanics: Entropy, Order Parameters, and Complexity[1]. The problem is on page 19 of the pdf linked and is titled Six degrees of separation. For it I came up with this code: http://hpaste.org/84114 It runs fine when compiled with -O0 and consistently yields an answer around 10, but with -O1 and -O2 it consistently gives an answer around 25. Can somebody explain what is happening here? [1] http://pages.physics.cornell.edu/~sethna/StatMech/EntropyOrderParametersCom… Azeem

5 7

attoparsec and backtracking
by Evan Laforge 16 Mar '13

16 Mar '13

I have a couple of problems with attoparsec which I think are related to its always backtrack nature, but maybe there's some other way to solve the same problems. The first is that it's hard to get the right error msg out. For instance, I have a parser that tries to parse a number with an optional type suffix. It's an error if the suffix is unrecognized: p_num :: A.Parser Score.TypedVal p_num = do num <- p_untyped_num suffix <- A.option "" ((:"") <$> A.letter_ascii) case Score.code_to_type suffix of Nothing -> fail $ "p_num expected suffix in [cdsr]: " ++ show suffix Just typ -> return $ Score.Typed typ num However, which error msg shows up depends on the order of the (<|>) alternatives, and in general the global structure of the entire parser, because I think it just backtracks and then picks the last failing backtrack. Even after carefully rearranging all the parsers it seems impossible to get this particular error to bubble up to the top. The thing is, as soon as I see an unexpected suffix I know I can fail entirely right there, with exactly that error msg, but since there's no way to turn off backtracking I think there's no way to do that. The second thing is that I want to lex a single token. I thought I could just parse a term and then see how far I got and then use that index to splitAt the input. But attoparsec doesn't keep track of the current index, so I wrote ((,) <$> p_term <*> A.takeByteString), and then I can use the length of the left over bytestring. But due to backtracking, that changes what p_term will parse. Since takeByteString always succeeds, it will cause p_term to backtrack until it finds some prefix that will match. The result is that instead of failing to parse, "1." will lex as ("1", "."). Since I integrate lexing and parsing (as is common with combinator parsers), and since it seems I can't keep track of byte position with attoparsec, I think I'm out of luck trying to do this the easy way. I think I have to write a separate lexer that tries to have the same behaviour as the parser, but is all separate code. I know attoparsec was designed for speed, and error reporting and source positions are secondary. Am I simply asking too much of it? I originally used parsec, but parsing speed is my main bottleneck, so I don't want to give ground there. Is there a clever way to get attoparsec to do what I want? Or a ByteString or Text parser out there which is fast, but can not backtrack, or keep track of input position? I've heard some good things about traditional alex+happy... of course it would mean a complete rewrite but might be interesting. Has anyone compared the performance of attoparsec vs. alex+happy?

5 7