- Haskell-Cafe - Haskell.org

Parsing a bunch of strings without backtracking
by Javran Cheng 16 Mar '17

16 Mar '17

Hi all, I come across an idea about parsing a bunch of strings, just want to share this idea and looking for some comments and maybe pointing me to some related articles. The idea is when you have: 1 <$ string "aabb" <|> 2 <$ string "aacc" you can rewrite it as: string "aa" >> (1 <$ string "bb" <|> 2 <$ string "cc") so that you don't have to deal with the common prefix "aa" twice. Then I further extend this idea: if we have a set of strings (s1, s2, ...), whose element is not a prefix of any other set member, why don't we turn things like (v1 <$ string s1 <|> v2 <$ string s2 <|> ...) into a "tree-structure" so we don't need to deal with any common prefix more than once? So this motivates my little toy implementation at https://gist.github.com/Javran/1cbfe9897d9a5c8fae5d20a33fd83813 basically given a list [(s1,v1),(s2,v2)...], we want to generate a parser equivalent to (v1 <$ string s1 <|> v2 <$ string s2 <|> ...) but perhaps with less backtracking. My code does this by turning the set of strings into a tree structure (see function "compact") and using this "Compact" representation as a driver to generate the parser. I used ReadP to have a concrete parser for testing, but this should work with any parsing library supporting MonadPlus. I think they are bunch of things that can be improved: - for now every intermediate node of "Compact" contains just a char, so this will end up generating a parser that has branch `char 'f' >> char 'o' >> 'o'` in it instead of the slightly more efficient version `string "foo"` - we could further attach a weight to each string, this allows rearranging (<|>) chains so that a more frequent string parser appears earlier. - if the input [(s1,v1),(s2,v2)...] are all known constants at compile time, probably TemplateHaskell can be used for generating the parser at compile time (as a Haskell expression). I'm not sure how difficult this would be though, as I have very limited understanding of TH. but before I explore further, I want to collect some comments as I said in the beginning. Best, -- Javran (Fang) Cheng

3 4

Re: [Haskell-cafe] Lazy vs Strict ByteStrings
by Dimitri DeFigueiredo 16 Mar '17

16 Mar '17

I think I need to be more specific here. My gripe with ByteString is that there are two distinct ByteString types disguised as one. There are “disguised” simply by having the same name. This leads me to think the use of ByteString will be simpler than it usually turns out to be. I fear Backpack may soon make this worse. Obviously, this is not exclusive to ByteString. Using the same name for strict and lazy versions is all over the place. Here is another example: https://hackage.haskell.org/package/unordered-containers/docs/Data-HashMap-… https://hackage.haskell.org/package/unordered-containers/docs/Data-HashMap-… But the problem is specially insidious with BytStrings because of their usage patterns and also because the process of finding out which version is which through GHC error messages is very inefficient. Here is a very ugly example where I believe I was misled by both ByteString types having the same name. I needed to make a “random looking but secretly not random” number and package it up in a 128-bit UUID. In other words, I wanted to mark the random numbers I create, but in a way that nobody else knows they are mine. The `hash` function from the cryptonite library accepts ByteString and its output can be converted to ByteString. The UUID type also has a function `fromByteString`. What could be easier? Here’s what I ended up with: import System.Random import Data.Maybe import Data.Word import Data.UUID import Crypto.Hash import Crypto.Hash.Algorithms import Data.ByteArray import Data.ByteString.Builder import qualified Data.ByteString as BS import Data.ByteString.Lazy as BSL -- Ugly! Step-by-step markAsSelf :: Word64 -> Word64 -> UUID markAsSelf selfDetectKey rand = let selfKeyAsLazyBS = toLazyByteString (word64BE selfDetectKey) randAsLazyBS = toLazyByteString (word64BE rand) hashInput = BSL.concat [randAsLazyBS, selfKeyAsLazyBS] digest = hash (toStrict hashInput) :: Digest SHA256 hashBitsStrict = BS.take 8 (convert digest) halfAndHalf = BSL.concat [randAsLazyBS, fromStrict hashBitsStrict] in fromJust (fromByteString halfAndHalf) secret :: Word64 secret = 12345 main = do r <- randomIO print (markAsSelf secret r) --------- end --------- in Data.ByteString.Builder toLazyByteString :: Builder -> ByteString -- exists toStrictByteString :: Builder -> ByteString -- was not found Similarly, in Data.UUID fromByteString :: ByteString -> Maybe UUID — only exists for lazy I think this lack of a common interface makes the code above a type conversion disaster and the process of debugging it painfully inefficient. Is there a better approach to go about doing this? Cheers, Dimitri -- 2E45 D376 A744 C671 5100 A261 210B 8461 0FB0 CA1F

2 1

[ANN] Haskell Paris meetup on 2017-03-27
by lucas di cioccio 15 Mar '17

15 Mar '17

Dear cafe readers, The next Haskell Paris Meetup will take place on 2017-03-27 at Murex near Trocadéro in Paris. There will be two entry-level/intermediary-level talks (in French) as well as some time for socializing. You'll find more details about the event as well as a registration form at https://www.meetup.com/haskell-paris/events/238394643/ . Best, -- Lucas DiCioccio

1 0

Re: [Haskell-cafe] To [] Or Not To []
by Olaf Klinke 15 Mar '17

15 Mar '17

Well, Joachim, it certainly can not get easier than that. Thanks a lot! Olaf

1 0

Lazy vs Strict ByteStrings
by Dimitri DeFigueiredo 15 Mar '17

15 Mar '17

I just noticed that I avoid using ByteStrings because I tend to spend a huge amount of time reading GHC output and trying to figure out if I am/should be using the strict or the lazy version. I have to use both lazy/strict because different libraries use different versions. Maybe having different names would have helped. Am I doing something wrong or is the interface to ByteStrings a poor design? Cheers, Dimitri -- 2E45 D376 A744 C671 5100 A261 210B 8461 0FB0 CA1F

1 0

Register for BayHac 2017
by Dan Burton 15 Mar '17

15 Mar '17

Registration form: https://goo.gl/forms/GWShzl5m2icmhf8L2 [image: Inline image 1] <https://goo.gl/forms/GWShzl5m2icmhf8L2> All attendees are requested to register for the event via the registration form. Registration form: https://goo.gl/forms/GWShzl5m2icmhf8L2 More info: https://wiki.haskell.org/BayHac2017 -- Dan Burton

1 0

PLDI ACM Student Research Competition (SRC)
by Tobias Grosser 14 Mar '17

14 Mar '17

The ACM Student Research Competition (SRC), sponsored by Microsoft Research, offers a unique forum for undergraduate and graduate students to present their original research on programming language design, implementation, theory, applications, and performance at PLDI 2017. The goal is to give students a place to discuss their research with experts in their field and to help them sharpen their research and communication skills. Please find more information at http://pldi17.sigplan.org/track/pldi-2017-student-research-competition Deadline for submission of the extended abstracts: Friday April 7th, 2017. ## Rounds Three rounds of competition will take place before and during PLDI 2017. All rounds are held in two categories: Undergraduate Students and Graduate Students (Masters and PhD level). Winners of the third round will be invited to participate in the SRC Grand Finals competition hosted by the ACM. The PLDI rounds are: * Extended abstract round. All students are encouraged to submit an extended abstract outlining their research. * Poster session. Based on the abstracts, a panel of judges will select the most promising authors to participate in the poster session which will take place at PLDI. In the poster session, students will have the opportunity to present their work to the judges, who will select a group of semi-finalists in each category to advance to the next round. * PLDI presentation. The last PLDI round will consist of an oral presentation at the conference to compete for the three top places. ## Prizes Winners of the three top places in each category receive prizes of $500 for the first place winner, $300 for the second place winner and $200 for the third place winner, respectively. The top three undergraduate and graduate winners receive an award medal and a one-year complimentary ACM student membership with a subscription to ACM’s Digital Library. ## ACM SRC Grand Finals First place winners in each category will be invited to participate in the ACM SRC Grand Finals, an on-line round of competition between first-place SRC winners from different ACM conferences held in 2017. Grand Finals will be judged by a different, ACM-appointed panel of judges. Winners of the three top Grand Finals places in each category will receive additional prizes of $500 for the first place winner, $300 for the second place winner and $200 for the third place winner, respectively. They will be also invited to the annual ACM Award Banquet along with prestigious ACM award winners, including the winner of the Turing Award. ## Eligibility criteria Current student status, either graduate or undergraduate, at the time of submission deadline. In order to advance to the poster session round, participants of the SRC must be current ACM (student) members. ## Extended Abstract Submission Details Each submission should include the student author’s name, institutional affiliation, e-mail address, and postal address; research advisor’s name; ACM student member number; category (undergraduate or graduate); research title; and an extended abstract addressing the following: The extended abstract must not exceed 1000 words and must not be longer than 2 pages. Reference lists do not count towards these limits. ## SRC Panel Xavier Martorell, BSC and UPC (chair). Tobias Grosser, ETH Zurich Sandrine Blazy, IRISA Martin Kong, RICE University Timothy Bourke, INRIA Cole Schlesinger, Barefoot Networks, Inc.

1 0

3 Lectureships in Computer Science at University of Bristol
by Nicolas Wu 13 Mar '17

13 Mar '17

Dear all, The University of Bristol is currently advertising three lectureships that you may be interested in: 2 x Lecturer or Senior Lecturer in the Department of Computer Science [1] 1 x Lecturer or Senior Lecturer in Computer Science – Software Engineering [2] These roles would be a good fit for candidates interested in Software Engineering and Programming Languages. The University of Bristol was ranked 5th on research intensity by the Research Excellence Framework (REF 2014) [3], and in Computer Science and Informatics was ranked 4th on research intensity [4]. Bristol has had a long tradition of teaching Haskell to its first year undergraduates in their first term, and attracts strong students. If you're interested, then do consider applying and feel free to get in touch! Best wishes, Nick Links: [1] http://www.bristol.ac.uk/jobs/find/details.html?nPostingID=5674&nPostingTar… [2] http://www.bristol.ac.uk/jobs/find/details.html?nPostingID=5737&nPostingTar… [3] https://www.timeshighereducation.com/sites/default/files/Attachments/2014/1… [4] https://www.timeshighereducation.com/sites/default/files/Attachments/2014/1… Dr Nicolas Wu Department of Computer Science University of Bristol

1 0

What is a good way to test library on several ghc's?
by Anton Kholomiov 13 Mar '17

13 Mar '17

Someone asked to add support in my lib for older version of GHC. I know that there are GHC-version specific pragmas to activate the code on specific version. I'm not quite sure how to setup the environment to use several GHCs. How do you do that kind of thing? Cheers! Anton

5 5

Authenticated APIs in Servant
by Ivan Lazar Miljenovic 13 Mar '17

13 Mar '17

I'm needing to write and deploy a web API with authenticated endpoints. I was planning on using Servant, but it looks like there is still no in-built support for OAuth-style token-based APIs. Is that correct, or did I miss something? (That said, the actual API is of a "submit one POST and get a response back" style rather than continuing to do more requests, so a username/password basic authentication approach may also work if all else fails.) -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

3 3