- Haskell-Cafe - Haskell.org

How to improve the running time of my algorithm
by Dominik Bollmann 15 Jan '18

15 Jan '18

Hello Haskell-Cafe, While playing with dynamic programming problems, I've been trying to solve the "Abbreviation" problem found on hackerrank.com at https://www.hackerrank.com/challenges/abbr/problem. Briefly, this problem asks to decide whether a source string s can be abbreviated into a target string t by capitalizing some of the characters in s and deleting its afterwards remaining lowercase characters. For example, the string s = "aBbdD" can be abbreviated as target t = "BBD", but target t' = "XYZZ" is not an abbreviation for source s' = "xyz". My solution to this problem is the following memoization-based function `isAbbreviation`: ``` import Control.Monad import Control.Monad.State import Data.Char import Data.Map.Strict (Map) import qualified Data.Map.Strict as Map import Data.Maybe import Data.String import Data.Text (Text) import qualified Data.Text as Text import System.IO type Store = Map (Text, Text) Bool isAbbrMemo :: Text -> Text -> State Store Bool isAbbrMemo s t | Text.null t = extend s t $ return (Text.all isLower s) | Text.null s = extend s t $ return False | otherwise = let (a, as) = fromJust $ Text.uncons s (b, bs) = fromJust $ Text.uncons t in extend s t $ matches a as b bs where matches a as b bs | isLower a && toUpper a /= b = isAbbrMemo as (b `Text.cons` bs) | isLower a && toUpper a == b = (||) <$> isAbbrMemo as bs <*> isAbbrMemo as (b `Text.cons` bs) | isUpper a && a /= b = return False | isUpper a && a == b = isAbbrMemo as bs extend :: Text -> Text -> State Store Bool -> State Store Bool extend s t m = do st <- get case Map.lookup (s,t) st of Just v -> return v Nothing -> do v <- m modify $ Map.insert (s,t) v return v isAbbreviation :: Text -> Text -> Bool isAbbreviation s t = evalState (isAbbrMemo s t) Map.empty main :: IO () main = do queries <- readQueries stdin let answers = map yesNo $ map (uncurry isAbbreviation) queries forM_ answers putStrLn yesNo :: Bool -> String yesNo True = "YES" yesNo False = "NO" readQueries :: IsString a => Handle -> IO [(a, a)] readQueries h = do numQueries <- read <$> hGetLine h :: IO Int forM [1..numQueries] $ \_qid -> do s <- hGetLine h t <- hGetLine h return (fromString s, fromString t) ``` However, running `isAbbreviation` on Hackerrank's input #13 still takes around 38 seconds on my machine and is therefore too slow to be an accepted solution. The input of question is attached as a text file. My question is therefore: Where could I further improve the running time of the function `isAbbreviation`? Is there any low-hanging fruit to improve upon? Or is my dynamic-programming based approach somehow flawed in general? (in which I should rather rethink the problem?) Any observations, remarks, and improvements on the above code snippet are greatly appreciated :-) Thanks, Dominik.

2 1

ANN: shelltestrunner 1.9 - Easy, repeatable testing of CLI programs/commands
by Simon Michael 15 Jan '18

15 Jan '18

I'm pleased to announce a new release of shelltestrunner! shelltestrunner (executable: shelltest) is a portable command-line tool for testing command-line programs, or general shell commands, released under GPLv3+. It reads simple test specifications defining a command to run, some input, and the expected output, stderr, and exit status. It can run tests in parallel, selectively, with a timeout, in color, etc. Projects using it include hledger, Agda, and berp. The last release was 1.3.5, in 2015. The new version is 1.9, which has substantial improvements and is recommended for all users. More real-world testing and contributions will help us deliver 2.0. New in 1.9 (2018/1/14): * two new test file formats, allowing input re-use and lighter syntax * new -l/--list flag lists the tests found * new -D/--defmacro option allows text substitution (Taavi Valjaots) * new --xmlout option saves test results as xml (Taavi Valjaots) * tests with Windows line endings now also work on unix (Taavi Valjaots) * shelltestrunner's tests should now pass on Windows (Taavi Valjaots) * flags formerly passed through to test-framework are now built in * >>>= with nothing after it now matches any exit status * failure messages now show the test command (John Chee) * include shelltestrunner's tests in cabal sdist archive (Iustin Pop) * build with latest deps and stackage resolvers * shelltestrunner's code and home page have moved to github Thanks to release contributors Taavi Valjaots, Andrés Sicard-Ramírez, Iustin Pop and John Chee. Install: $ stack install shelltestrunner-1.9 or: $ cabal update && cabal install shelltestrunner-1.9 Home, docs: https://github.com/simonmichael/shelltestrunner <https://github.com/simonmichael/shelltestrunner>

1 0

Fails to `stack exec` a Yesod app
by Yotam Ohad 13 Jan '18

13 Jan '18

Hi, I have the following project (https://github.com/yohad/TheMafsidan) 'stack build` works with no errors but when I try to run it I get App: static: getDirectoryContents:openDirStream: does not exist (No such file or directory) Anyone has a clue on how to fix this? Yotam

3 2

Internships at Microsoft Research Cambridge
by Simon Peyton Jones 12 Jan '18

12 Jan '18

Happy New Year! Would anyone like to come to Microsoft Research Cambridge for an internship? For the first time, this year we have put together a list of all the open internship slots<https://www.microsoft.com/en-us/research/opportunity/internships-msr-cambri…>, with brief descriptions and closing dates. This is in part due to our efforts to reach more people, and attract a broader, more diverse range of applicants. There are lots of projects on that page, but I'd like to highlight one group in particular. I'm personally involved in a project with four intern slots, in which we are using insights from functional programming got improve the experience of using spreadsheets - the world's most widely used functional programming languages. This focus on end-user programming means that we need interns with wide interests and skills. More details are below (copy/pasted from the web page). The application deadline is 31 January 2018. (NB: other slots have other deadlines.) Thanks Simon Functional programming and spreadsheets Supervisors: Simon Peyton Jones<https://www.microsoft.com/en-us/research/people/simonpj/>, Andy Gordon<https://www.microsoft.com/en-us/research/people/adg/>, Claudio Russo<https://www.microsoft.com/en-us/research/people/crusso/>, Neil Toronto, Advait Sarkar<https://www.microsoft.com/en-us/research/people/advait/> Start Date: June/July 2018 Applications close January 31 2018 Reference #: MSRC226 We hope to hire four interns during 2018 with a focus on using insights from functional programming to improve the experience of using spreadsheets. The exact internship project will be chosen to fit the expertise of successful applicants, but we are interested in a broad range of areas including: * Improving the experience of authoring formulae in a spreadsheet * Compiling spreadsheets for faster execution * Using insights from type systems to catch programming errors sooner * Generalisation and program synthesis * Demonstrating radical improvements in the range of applications that can be tackled with spreadsheets. We are looking for three interns with programming-language expertise, and one with a strong background in HCI and user experience. You would be working with leaders in both functional programming (Andy Gordon, Simon Peyton Jones) and user experience (Advait Sarkar, Kenton O'Hara). There is a genuine possibility that your work could have real-world impact. By way of general background, you may want to read Simon Peyton Jones et al's papers "A user-centred approach to functions in Excel<https://dl.acm.org/citation.cfm?id=944721>" and "Champagne Prototyping: A Research Technique for Early Evaluation of Complex End-User Programming Systems<http://ieeexplore.ieee.org/document/1372297/#full-text-section>".

2 1

ANN: network-2.6.3.3
by evan＠evan-borden.com 11 Jan '18

11 Jan '18

Announcing network-2.6.3.3 * Add a function to show the defaultHints without reading their undefined fields [#291](https://github.com/haskell/network/pull/292) * Improve exception error messages for getAddrInfo and getNameInfo [#289](https://github.com/haskell/network/pull/289) * Deprecating SockAddrCan. As always a huge thank you to the network contributors.

1 0

Re: [Haskell-cafe] Getting some funny brackets in Haddock docs
by Johannes Waldmann 10 Jan '18

10 Jan '18

OverloadedLists solves this, in a way? Prelude> :set -XOverloadedLists Prelude> import qualified Data.Map.Strict as M Prelude M> M.size [(2,3)] 1 because of the IsList instance https://hackage.haskell.org/package/containers-0.5.10.2/docs/src/Data.Map.I… Do we want to use this in code examples in the docs? Equivalently, is it recommended to use this notation in actual code? The problem I see is that this (and similar) extensions will be active for all literals in a module - while we only want it for literals of some specific type. I know this is handled in the parser, and we don't know the types at this point. - J

4 4

Getting some funny brackets in Haddock docs
by David Feuer 10 Jan '18

10 Jan '18

The containers Haddock documentation currently represents sequences, sets, and maps via the relevant `fromList` function. For example, Data.Map gives the example findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x' I find these `fromList` calls exceedingly distracting, and I think they obscure the key ideas. Of course, I *could* just specify at the top that the documentation assumes OverloadedLists, but I think that's likely to be somewhat confusing, especially to beginners. My preference would really be to represent these data structures using funny brackets of some sort. Perhaps ⟦7,34,12⟧ for a sequence, ⦃40,3⦄ for a set, and ⟪(12,"alpha"), (14,"bravo")⟫ for a map. But there are three problems: 1. How can I insert the brackets conveniently? I definitely don't want to fill the module with Unicode. My preference would be to use \{ and \} or \[ and \] and have them get replaced by the left and right brackets appropriate to the module in question. But I don't actually know how to do that. 2. Funny brackets could presumably cause trouble for people who don't have appropriate fonts available. How could I mitigate this? 3. This whole idea could cause trouble for people who want to copy and paste examples from the documentation. Are people likely to want to do that? If so, how might I mitigate that problem? Are there tricks I can play to make copy/paste turn a funny left bracket into `fromList [` and a funny right bracket into `]`, and also not break things for non-HTML backends? Thanks, David

4 3

Re: [Haskell-cafe] Package takeover: re2
by Andrey Sverdlichenko 09 Jan '18

09 Jan '18

Thanks! On Mon, Jan 8, 2018 at 11:20 PM John Millikin <john(a)john-millikin.com> wrote: > Just added you to the maintainer's list. Sorry for the delayed response, > I've been away from reliable internet for a few weeks. > > When you upload the next version, please also update the contact info to > yours. I'll say on my site that you're the new maintainer. > > On Mon, Jan 8, 2018 at 9:54 AM, Andrey Sverdlichenko <blaze(a)ruddy.ru> > wrote: > >> I'd like to take over maintenance of the package re2. It is built >> against old version of re2 library, never updated after 2014 and listed as >> "deprecated" on the author's website. I rather update this one than add >> another package for the same bindings. >> >> I tried to contact owner a week ago, but to no avail. My hackage username >> is blaze. >> > >

1 0

looking for deep learning explanation a la Lämmel's map-reduce paper
by Johannes Waldmann 09 Jan '18

09 Jan '18

Dear Cafe, I like this paper (R. Lämmel in SCP 2008) very much https://userpages.uni-koblenz.de/~laemmel/MapReduce/ both for contents and for style - and I wonder if there's something similar ("Haskell for design recovery", "rigorous description", "executable specification") on deep learning. Mainly for understanding/teaching without all the hype. (But of course, an accelerate-* implementation would be nice.) Yes I know that hyperbole *is* the main thing in this area. Happy New Year - J.

2 2

Package takeover: re2
by Andrey Sverdlichenko 09 Jan '18

09 Jan '18

I'd like to take over maintenance of the package re2. It is built against old version of re2 library, never updated after 2014 and listed as "deprecated" on the author's website. I rather update this one than add another package for the same bindings. I tried to contact owner a week ago, but to no avail. My hackage username is blaze.

1 0