January 2018 - Haskell-Cafe

ANNOUNCE: servant-pandoc 0.5.0.0
by Ivan Lazar Miljenovic 16 Jan '18

16 Jan '18

I'm pleased to announce the latest release of the servant-pandoc library: https://hackage.haskell.org/package/servant-pandoc-0.5.0.0 servant-pandoc allows you to take the documentation created with servant-docs and use Pandoc to convert it into whichever format you want (rather than the Markdown generated by servant-docs). The main changes in this release are to provide compatibility with servant-docs-0.11.1; specifically, servant-pandoc now emits all the information that servant-docs does with the same configuration options. As such, there are behavioural changes which necessitated the major version bump. -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

1 0

Re: [Haskell-cafe] Non-deterministic function/expression types in Haskell?
by Olaf Klinke 15 Jan '18

15 Jan '18

Long story short: You can stay inside Haskell's type system or extend it, but you end up with monads either way. I'll explain why. > (a) why are monads a perfect solution to my problem? Two reasons. First: Probability distributions do form a monad [Giry,CS,Kock]. It's a mathematical fact. So why not exploit it? It gives you powerful combinators and powerful abstractions. Second: Because the requirements on the type modificators [N] and [D] are describing many features monads have. First observe that you don't really need [D] because any deterministic computation can be embedded into the non-deterministic computations by making the set of possibilities a singleton. That is precisely what 'return' does in the context of monads. (Think of return for the list monad.) > any function that takes a non-deterministic input must have a non-deterministic output. That is common with monads, too: There is no generic function that can extract values out of monads. > we should merge variables with identical values if the types are non-deterministic. That is problematic on several levels. First, is "identical values" decidable by the compiler? Second, equality might depend on the implementation, which might change. For example, (normal 0 1) could contain a random number generator with an intrinsic state. > sample:: (()->a[N]) -> a[N] Observe that, disregarding non-terminating computations, any type t is isomorphic to () -> t. Knowing this, your statement seems to imply that a non-deterministic computation is identified with what you can sample from it. > iid:: Int -> (() -> a[N]) -> [a[N]] The function Control.Monad.sequence plays this role for monads, with a slightly different type signature. Control.Monad.sequence . Data.List.repeat :: Monad m => m a -> m [a] Let the name not deceive you: It is not about sequential computations, rather about ordering the random variables sequentially. > (b) can we extend the HM type system to support non-determinism directly? Yes, you can. But then you have a different language. There many publications describing that [Draheim,Lago,Borgström,RP]. In a nutshell, start with the simply typed lambda calculus and add an operation choose :: I -> a -> a -> a where I is the the type of real numbers 0 <= x <= 1. 'choose' makes a weighted probabilistic choice between its second and third argument. However, in order to describe what programs in (lambda calculus + choose) actually _mean_, you need two things: (1) Define what the compiled program should do at runtime (operational semantics). (2) Define what the program means, mathematically (denotational semantics). For (1), the prevailing approach seems to be to equate a probabilistic term with its behaviour under sampling. Markov Chains are popular [MCMC]. I read it's non-trivial, however, to find a Markov chain that behaves according to a mathematically defined probability distribution. The probability that you know more about that than I do is 1. For (2), the mathematical meaning of ordinary Haskell programs are given via the following mapping. Every Haskell type t is associated with a domain D [DOM] and each Haskell function of type t -> t' is associated with a mathematical function f: D -> D' between the associated domains. Whenever non-determinism is involved, e.g. a probabilistic computation on type t, then instead of D one uses P(D), a suitable "powerdomain". There are various P for various sorts of non-determinism (see the work of Gordon Plotkin), and each of them is a monad on the category of domains. A major problem is whether the P for probabilisitc choice works well with e.g. function types. That is why many papers restrict themselves to first-order functions. Another notoriously hard problem is to combine different sorts of non-determinism. It is like combining monads in Haskell: Some monads have monad transformers associated with them, but some don't. Finally, you might want to play with non-determinism other than the probabilistic one. For example, there is the infinite-search package on hackage, which provides a monad of plain non-deterministic choice beyond finite lists. It is even possible to define a Haskell probability monad in the same spirit. I can provide some code if you wish. Regards, Olaf References [Giry] http://dx.doi.org/10.1007/BFb0092872 [CS] http://dx.doi.org/10.1007/s10485-013-9324-9 [Kock] http://www.tac.mta.ca/tac/volumes/26/4/26-04.pdf [Draheim] http://www.springer.com/de/book/9783642551970 [Lago] https://arxiv.org/abs/1104.0195 [Borgström] https://arxiv.org/abs/1512.08990 [RP] http://www.cs.tufts.edu/~nr/pubs/pmonad.pdf [MCMC] http://okmij.org/ftp/kakuritu/Hakaru10/index.html [DOM] http://www.worldscientific.com/worldscibooks/10.1142/6284

2 2

Non-deterministic function/expression types in Haskell?
by Benjamin Redelings 15 Jan '18

15 Jan '18

Hi, 0. Does anyone know of any simple extensions of the HM type system to non-deterministic functions? The reason that I'm asking is that for probabilistic programming in the lambda calculus, there are two ways of writing expressions: (a) stochastic: let x = sample $ normal 0 1 in x*x or simply (sample $ normal 0 1)^2 (b) "mochastic": do {x <- normal 0 1; return (x*x)} The "mo" in the second one refers to the use of monads. That is the approach taken in the paper "Practical Probabilistic Programming with monads" (http://mlg.eng.cam.ac.uk/pub/pdf/SciGhaGor15.pdf) which I really enjoyed. However, I am interested in the stochastic form here. There are a number of reasons, such as the fact that the monadic representation forces serialization on things that need not be serial. In fact, though, I'm not trying to prove which one is best, I am just interested in exploring the non-monadic approach as well. 1. So, is it possible to do a simple extension to the type system to express non-determinism? I found this paper (Implicit Self-Adjusting Computation for Purely Functional Programs) that uses "level" tags on types to express either (i) security or (ii) changeability. The first idea (for example) is that each type is tagged with one of two "levels", say Public and Secure, so that we actually have Int[Public] or Int[Secure]. Any function that consumes a Secure value must (i) must return a Secure type and (ii) has the arrow in its type labelled with [Secure]. I won't explain the "changeable" idea because its kind of complicated, but I am very interested in it. 2. This is kind of tangential to the point of my question, but to explain the examples below, it might be important to distinguish sampling from a distribution from the distribution itself. So, normal 0 1 won't generate a random sample. Instead, normal 0 1 () will generate a random sample. This allows us to pass (normal 0 1) to another function which applies it multiple times to generate multiple samples from the same distribution. -- sample from a distribution dist sample dist = dist () --- take n samples from a distribution dist iid n dist = take n (map sample $ repeat dist) Here we see some of the value of using the stochastic approach, versus the "mochastic" approach: we can use normal Haskell syntax to handle lists of random values! 3. So, I'm wondering if its possible to extend the HM type system to handle non-determinism in a similar fashion by either (i) having some function types be non-deterministic and/or (ii) having term types be non-deterministic. Taking the second approach, I suggest tagging each type with level [D] (for deterministic) or [N] (for non-deterministic). Notation-wise, if a determinism level is unspecified, then this means (I think) quantifying over determinism levels. A function that samples from the normal distribution we would get a type like: normal:: double -> double -> () -> double[N] Our goal would be that an expression that consumes a non-deterministic expression must itself be non-deterministic, and any function that takes a non-deterministic input must have a non-deterministic output. We could implement that using rules something like this, where {a,b} are type variables and {l1,l2} are level variables. x:a[l1] :: a[l1] \x:a[l1] -> E:b[l2] :: a[l1] -> b[max l1 l2] E[a[l1]->b[l2]] E[a[l]] :: b[l2] The idea is that max l1 l2 would yield N (non-deterministic) if either l1=N or l2=N, because N > D. 4. Putting non-determinism into the type system would affect GHC in a few ways: (a) we shouldn't pull non-deterministic expressions out of lambdas: We should NOT change \x -> let y=sample $ normal 0 1 in y+x into let y = sample $ normal 0 1 in \x -> y+x (b) we should merge variables with identical values if the types are non-deterministic. For example it is OK to change let {x=normal 0 1; y = normal 0 1 in (sample x * sample y)} into let {x=normal 0 1} in sample x However it is NOT OK to change let {x=sample $ normal 0 1; y = sample $ normal 0 1} in x*y into let {x=sample $ normal 0 1} in x*x Perhaps this would be useful in other contexts? 5. If what I've written makes sense, then the types of the functions 'sample' and 'iid' would be: sample:: (()->a[N]) -> a[N] iid:: Int -> (() -> a[N]) -> [a[N]] 6. This is quite a long e-mail, so to summarize, I am interested in whether or not there are any simple systems for putting non-determinism into HM. Is the use of tagged types known NOT to work? Is there are work on this that I should be aware of? Any help much appreciated! :-) take care, -BenRI

9 12

LambdaConf 2018: Call for Proposals
by John A. De Goes 15 Jan '18

15 Jan '18

Dear Haskell Enthusiast: We are pleased to announce the Call for Proposals for LambdaConf 2018 <https://lambdaconf2018.dryfta.com/en/abstract-submission>. LambdaConf is the largest interdisciplinary functional programming conference in the Mountain West, and one of the largest and most well-known functional programming conferences in the world. The conference takes place June 3rd - 5th, in Boulder, Colorado, at the University of Colorado Boulder, and is preceded by commercial training opportunities and followed by a day of third-party mini-conferences on selected topics. If you are an educator, a researcher, a speaker, a speaker coach, or someone aspiring to one of the preceding, then we warmly welcome you to submit a proposal for LambdaConf 2018 <https://lambdaconf2018.dryfta.com/en/abstract-submission>. No prior experience is necessary for most proposals, and we welcome beginner-level content. The Call for Proposals closes at the beginning of February 2018. We recommend submitting as early as you can to ensure sufficient time for editing. LambdaConf attracts everyone from the FP-curious to researchers advancing state-of-the-art; hobbyists, professionals, academics and students. Material at all levels, including beginner content and very advanced content, will find an audience at LambdaConf. Historically, LambdaConf has enjoyed a large selection of sessions on statically-typed functional programming, and a smaller selection of sessions on dynamically-typed functional programming. Some sessions are not tied to specific programming languages, but rather cover topics in abstract algebra, category theory, type theory, programming language theory, functional architecture, and so on, either generally or in a way that applies across many programming languages. LambdaConf looks for sessions in the following areas: Languages. Proposals that overview or dive into specific features of functional, math, or logic programming languages (both new and existing), with the goal of exposing developers to new ideas or helping them master features of languages they already know. Libraries. Proposals that discuss libraries that leverage functional or logic programming to help programmers solve real-world problems. Concepts. Proposals that discuss functional programming idioms, patterns, or abstractions; or concepts from mathematics, logic, and computer science, all directed at helping developers write software that's easier to test, easier to reason about, and easier to change safely. Applications. Proposals that discuss how functional programming can help with specific aspects of modern software development, including scalability, distributed systems, concurrency, data processing, security, performance, correctness, user-interfaces, machine learning, and big data. Use Cases. Proposals that discuss how functional programming enabled a project or team to thrive, or deliver more business value than possible with other approaches. Cherry Picking. Proposals that show how techniques and approaches from functional programming can be adapted and incorporated into mainstream development languages and practices, to the benefit of developers using them. Cautionary Tales. Proposals that call attention to difficulties of functional programming (both as a cautionary tale but also to raise awareness), especially such proposals that suggest alternatives or a path forward. Efficacy. Proposals that present data, measurements, or analysis that suggests different techniques, paradigms, languages, libraries, concepts, or approaches have different efficacies for given specified metrics, which provide actionable takeaways to practicing functional and logic programmers. Off-Topic. Proposals that have appeal to a mainstream developer audience (the number of off-topic proposals we accept is small, but we do accept some, especially for keynotes). LambdaConf accepts proposals for the following types of sessions: Leap Workshops (6h). Leap Workshops are approximately 6 hours in length. They are in-depth, hands-on workshops designed to teach mainstream functional programming topics in enough detail, attendees can immediately apply what they learn in their jobs. We require that speakers follow our recommended format for Leap Workshops, although we allow exceptions for experienced teachers. Hop Workshops (2h). Hop Workshops are 2 hours in length. Like Leap Workshops, these workshops are in-depth and hands-on, but they cover reduced content and may be specialized to topics that may not have mainstream appeal. We require that speakers follow our recommended format for Hop Workshops, although we allow exceptions for experienced teachers. De Novo Sessions (50m). De Novo Sessions are 50 minutes in length. These sessions are designed to present original work from industry and academia. While the requirements for proposals are more rigorous, there is less competition for De Novo slots. Educational Sessions (50m). Educational Sessions are 50 minutes in length. These sessions are designed to clearly and concisely teach one useful concept, skill, aspect, library, or language to attendees. Inspire Talks (5m). Inspire talks are 5 minutes in length and focus on clear communication of a single takeaway. These sessions are intended to inspire attendees to learn more about particular subjects or to try new approaches, and must follow Ignite-style, which consists of 20 slides, each auto-advancing after 15 seconds. Keynotes (40m). Keynotes are 40 minutes in length, and are presented before all attendees (there are no other sessions concurrent with keynotes). Keynotes are designed to offer thought-provoking, opinionated, and insightful commentary on topics of interest to the community. Level of reimbursement varies based on the type of proposal you are selected for: Leap Workshops (6 hours). Speakers for Leap Workshops receive a free ticket, a speaker gift, a speaker dinner, up to 4 days accommodations, full travel reimbursement, and a small honorarium. Hop Workshops (2 hours) / Educational (50m) / De Novo (50m) / Keynote (50m). Speakers for Hop Workshops, Educational, De Novo, and Keynote receive a free ticket, a speaker gift, a speaker dinner, and up to 4 days accommodations. Speakers may also request travel assistance, which is dealt out based on availability and need, and which may cover up to $250 for domestic travel, and $500 for international travel. Inspire (5m). As Inspire talks are only 5 minutes in length, Inspire speakers receive a speaker gift and a speaker dinner, but must purchase a ticket and pay for travel and accommodations on their own. If you are accepted for a specific type of proposal (e.g. Educational), we cannot guarantee that you will get a slot of this type. Based on scheduling requirements, feedback from the committee, or feedback from your speaker coach, we may require you to change the format of your session. You may submit as many proposals as you like, though we recommend spending more time refining fewer proposals, since the quality of your proposals has a significant effect on their chances of acceptance by the blind committee. If you wish to maximize your chances of having a proposal accepted, we also recommend spreading 2-3 proposals across multiple categories, because some categories are fiercely competitive, while others are less competitive. For more information, please see the Call for Proposals website <https://lambdaconf2018.dryfta.com/en/abstract-submission>. Regards, -- John A. De Goes john(a)degoes.net Follow me on Twitter @jdegoes

2 2

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

14 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 14 Jan '18

14 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 11 Jan '18

11 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 10 Jan '18

10 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